Existence of extremal graphs for every degeneracy

Let dd be an integer with d2d\geq 2. A graph is dd-degenerate if every subgraph has a vertex of degree at most dd. Let f(H,p)f(H,p) denote the subgraph query complexity, and write bb for the relevant query parameter.

Extremal graph existence conjecture. For every integer d2d\geq 2, there exists a dd-degenerate graph HH such that

f(H,p)=bdo(1).f(H,p)=b^{d-o(1)}.

In the case d=2d=2, the paper constructs such a graph, whereas the existence of such graphs for d3d\geq 3 remains open.

Sources & referencesView supporting material

Primary source

Ryan Alweiss, Chady Ben Hamida, Xiaoyu He and Alexander Moreira, “On the subgraph query problem”, arXiv:1911.04413 (2020).

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.