Kang–Kim–Liu conjecture on single-graph extremal exponents

About 7 years old · traced to

Let rr be a rational number in [1,2][1,2]. For a graph HH, let ex(n,H)ex(n,H) denote the maximum number of edges in an nn-vertex graph containing no copy of HH.

Kang–Kim–Liu conjecture. For every rational number r∈[1,2]r\in[1,2], there exists a graph HH such that

ex(n,H)=Θ(nr).ex(n,H)=\Theta(n^r).

Kang, Kim and Liu stated this as a slightly weaker version of Erdős's single-graph conjecture, replacing an asymptotic equivalent by a matching order of growth. The source gives no evidence that this weaker conjecture has been resolved.

References

Primary source

Weilun Xu, Guorong Gao and An Chang, “Almost regular subgraphs under spectral radius constrains”, arXiv:2409.10853 (2024).

Additional references

2 papers in this index state this conjecture (2019–2024). The statement above is taken from the most recent of them; the others are arXiv:1903.10631.

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.