Bednarska-Bzdęga–Hefetz–Łuczak conjecture for Waiter–Client subgraph counts
Bednarska-Bzdęga–Hefetz–Łuczak conjecture for Waiter–Client subgraph counts
Let be a graph with , and let denote its maximum density over nonempty subgraphs, namely
Consider the -Waiter–Client game on the edges of , where Waiter offers 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 with , there exist such that, for sufficiently large and , Waiter can ensure that the resulting graph contains at least
copies of . This conjecture asserts the direction complementary to the already proved regime , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.