OPENHARDgraph theoryextremal graph theory
Let $c>0$ and $f_c(n)$ be the maximal $m$ such that every graph with $n$ vertices and $\geq cn^2$ edges, where each edge is in at least one triangle, contains a book of size $m$. Is $f_c(n)>n^{\epsilon}$ for some $\epsilon>0$? Or $f_c(n)\gg \log n$?
Notes: Fox and Loh proved f_c(n) <= n^{O(1/log log n)} for c < 1/4, disproving the polynomial conjecture. Edwards and Nikiforov proved f_c(n) >= n/6 when c > 1/4.
AI Status: NONE · 0 total attempts