The edge-deletion conjecture for upper thresholds

Let HH be a graph with at least three edges. For an edge ee of HH, let HeH-e be the graph obtained by deleting ee, together with a vertex of degree one if that vertex is an endpoint of ee. Let fH+(n)f^+_H(n) and fHe(n)f^-_{H-e}(n) denote the upper and lower thresholds of the strict (1 ⁣:b)(1\colon b) Avoider–Enforcer games. Edge-deletion conjecture. For every graph HH with at least three edges, one has

fH+(n)=Θ(maxeHfHe(n)).f^+_H(n)=\Theta\big(\max\limits_{e\in H} f^-_{H-e}(n)\big).

The conjecture proposes that the upper threshold is governed by the largest lower threshold among the edge-deleted graphs; the source presents it as an open problem for general graphs.

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.