The lower-threshold conjecture for Avoider–Enforcer games

For a non-empty graph HH, define

m(H)=maxFH:v(F)1e(F)v(F),m(H)=\max\limits_{F\subseteq H:\,v(F)\ge 1}\frac{e(F)}{v(F)},

where v(F)v(F) and e(F)e(F) are the numbers of vertices and edges of FF, respectively. Let fH(n)f^-_H(n) be the lower threshold of the strict (1 ⁣:b)(1\colon b) Avoider–Enforcer HH-game on KnK_n. Lower-threshold conjecture. For every graph HH with at least two edges, one has

fH(n)=Θ(n1m(H)).f^-_H(n)=\Theta\big(n^{\frac{1}{m(H)}}\big).

The paper proves this order when m(H)1m(H)\leq 1 and conjectures it for all graphs with at least two edges; the missing part is a suitable winning strategy for Enforcer.

Sources & referencesView supporting material

Primary source

Małgorzata Bednarska-Bzdȩga, Omri Ben-Eliezer, Lior Gishboliner and Tuan Tran, “On the separation conjecture in Avoider-Enforcer games”, arXiv:1709.09065 (2019).

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.