McKinley–Spiro random Turán conjecture for bipartite graphs

About 2 years old · traced to

Let FF be a graph with

ex(n,F)=Θ(nα)\mathrm{ex}(n,F)=\Theta(n^\alpha)

for some α∈(1,2]\alpha\in(1,2]. Write Gn,pG_{n,p} for the random graph with edge probability pp, and let d2(F)d_2(F) denote the 2-density parameter appearing in the conjecture. A sequence of events holds asymptotically almost surely if its probability tends to 11 as n→∞n\to\infty, and f(n)≪g(n)f(n)\ll g(n) means f(n)/g(n)→0f(n)/g(n)\to0. McKinley–Spiro's conjecture. Asymptotically almost surely,

ex(Gn,p,F)={max⁡{Θ(pα−1nα), n2−1/d2(F)(log⁡n)Θ(1)}p≫n−1/d2(F),(1+o(1))p(n2)n−2≪p≪n−1/d2(F).\mathrm{ex}(G_{n,p},F)=\begin{cases}\max\{\Theta(p^{\alpha-1}n^\alpha),\,n^{2-1/d_2(F)}(\log n)^{\Theta(1)}\}&p\gg n^{-1/d_2(F)},\\(1+o(1))p\binom{n}{2}&n^{-2}\ll p\ll n^{-1/d_2(F)}. \end{cases}

The conjecture predicts three regimes for the random Turán number, including a middle regime that is essentially independent of pp. It generalizes the behavior known in several bipartite graph cases, but the general statement remains open.

References

Primary source

Jiaxi Nie and Sam Spiro, “Random Turán Problems for Hypergraph Expansions”, arXiv:2408.03406 (2024).

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.