Bednarska-Bzdęga–Hefetz–Łuczak conjecture for Waiter–Client subgraph counts

Let HH be a graph with e(H)1e(H)\ge 1, and let m(H)m(H) denote its maximum density over nonempty subgraphs, namely

m(H)=max{e(H)v(H):HH, v(H)1}.m(H)=\max\left\{\frac{e(H')}{v(H')}:H'\subseteq H,\ v(H')\ge 1\right\}.

Consider the bb-Waiter–Client game on the edges of KnK_n, where Waiter offers bb previously unchosen edges in each round and Client chooses one, which is added to the resulting graph. Bednarska-Bzdęga–Hefetz–Łuczak's Waiter–Client conjecture. For every graph HH with e(H)1e(H)\ge 1, there exist c,γ>0c,\gamma>0 such that, for nn sufficiently large and bcn1/m(H)b\le c n^{1/m(H)}, Waiter can ensure that the resulting graph contains at least

γnv(H)be(H)\frac{\gamma n^{v(H)}}{b^{e(H)}}

copies of HH. This conjecture asserts the direction complementary to the already proved regime bn1/m(H)b\gg n^{1/m(H)}, and formalizes the claim that the game follows the probabilistic intuition of a random graph with the same density.

Sources & referencesView supporting material

Primary source

Rajko Nenadov, “Probabilistic intuition holds for a class of small subgraph games”, arXiv:2207.02772 (2022).

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.