Existence of extremal graphs for every degeneracy

About 7 years old · traced to

Let dd be an integer with d≥2d\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 d≥2d\geq 2, there exists a dd-degenerate graph HH such that

f(H,p)=bd−o(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 d≥3d\geq 3 remains open.

References

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.