Hypergraph logarithm-free inducibility bound conjecture

About 8 years old · traced to

For an nn-vertex rr-uniform hypergraph GG, let XG,kX_{G,k} be the number of hyperedges induced by a uniformly random kk-vertex subset, and let ind⁡r(k,ℓ)\operatorname{ind}_r(k,\ell) denote the corresponding asymptotic maximum point probability. For 0≤ℓ≤(kr)0\le\ell\le\binom{k}{r}, define

ℓ∗=min⁡\originalleft{ℓ,(kr)−ℓ\aftergroup\originalright}.\ell^*=\min\mathopen{}\mathclose\bgroup\originalleft\{\ell,\binom{k}{r}-\ell\aftergroup\egroup\originalright\}.

Hypergraph logarithm-free inducibility bound conjecture. For any r,kr,k and any 0≤ℓ≤(kr)0\le\ell\le\binom{k}{r}, we have

ind⁡r(k,ℓ)=O\originalleft(kr−1/ℓ∗\aftergroup\originalright).\operatorname{ind}_r(k,\ell)=O\mathopen{}\mathclose\bgroup\originalleft(\sqrt{k^{r-1}/\ell^*}\aftergroup\egroup\originalright).

This is presented as the natural hypergraph generalisation of the graph conjecture. The supplied text does not resolve it; it notes additional difficulties in the sparse case.

References

Primary source

Matthew Kwan, Benny Sudakov and Tuan Tran, “Anticoncentration for subgraph statistics”, arXiv:1807.05202 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.