McKinley–Spiro random Turán conjecture for bipartite graphs

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 nn\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α),n21/d2(F)(logn)Θ(1)}pn1/d2(F),(1+o(1))p(n2)n2pn1/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.

Sources & referencesView supporting material

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.