Problem 80

Let $c>0$ and let $f_c(n)$ be the maximal $m$ such that every graph $G$ with $n$ vertices and at least $cn^2$ edges, where each edge is contained in at least one triangle, must contain a book of size $m$ , that is, an edge shared by at least $m$ different triangles.

Estimate $f_c(n)$ . In particular, is it true that $f_c(n)>n^{\epsilon}$ for some $\epsilon>0$ ? Or $f_c(n)\gg \log n$ ?

Source: erdosproblems.com/80

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open. The page-level question, to estimate $f_c(n)$ , is open: for fixed $c<1/4$ the known bounds are $2^{\Omega(\log^*n)}\le f_c(n)\le n^{14/\log\log n}$ , and for $c\ge1/4$ they are $n/6\le f_c(n)\le n-2$ . The first "in particular" question is answered no, since it fails for every fixed $c<1/4$ , by Theorem 1.1 of Fox and Loh (Combinatorica 32 (2012), refereed), which the site records as the disproof of Erdős's first conjecture; the property it asks for holds for $c>1/4$ by the bound $f_c(n)\ge n/6$ of Edwards and of Khadzhiivanov and Nikiforov, proved in full as Corollary 3 of Khadzhiivanov's 1988 account [Kh88], and at $c=1/4$ by that account's Corollary 4. The second, whether $f_c(n)\gg\log n$ for every $c$ , is open: it holds for $c\ge1/4$ by the same bounds and is open for every fixed $c<1/4$ , the lower bound Fox and Loh derive being exponential in the iterated logarithm. No source answering the estimate or the logarithmic question was found in the search whose scope the Current assessment records; this is a bounded negative finding, not a certificate of openness. The frontmatter standing derives from the claim pages Fox and Loh 2012, an accepted partial claim answering the first closing question no, and Khadzhiivanov and Nikiforov 1979, a claimed partial claim covering the range $c>1/4$ (neither its venues' refereeing nor an acceptance of it under this problem is documented); no claim settles the whole problem, so the derived standing is open with no settling claim.

Er87: Erdős, P., Some problems on finite and infinite graphs. Logic and combinatorics (Arcata, 1985), Contemp. Math. 65, Amer. Math. Soc. (1987), 223--228; Problem 11, printed pp. 226--227. Library home: Erdos 1987.
Er88: Erdős, P., Problems and results in combinatorial analysis and graph theory. Discrete Math. 72 (1988), 81--92; Section 10, printed pp. 90--91. Not a source key on the site; named in the thread. Library home: Erdős 1988.
Er92: Erdős, P., Some of my favourite problems in various branches of combinatorics. Matematiche (Catania) 47 (1992), 231--240; Problem 14, printed pp. 234--236. Not a source key on the site; named in the thread. Library home: Erdős 1992.
FoLo12: Fox, J. and Loh, P.-S., On a problem of Erdős and Rothschild on edges in triangles. Combinatorica 32 (2012), no. 6, 619--628, doi:10.1007/s00493-012-2844-3; arXiv:1106.0290 (v2 5 June 2011, the version cited, 8 pages). Theorem 1.1 and the surrounding paragraphs, p. 2 of the preprint. Library home: Fox and Loh 2012.
KhNi79: Khadzhiivanov, N. G. and Nikiforov, S. V., Solution of a problem of P. Erdős about the maximum number of triangles with a common edge in a graph. C. R. Acad. Bulgare Sci. 32 (1979), 1315--1318. Not held; the bound $n/6$ is cited by [FoLo12] p. 2 and Potechin p. 2 and proved in full in the first author's 1988 account [Kh88].
Kh88: Khadzhiivanov, N., On the maximal number of triangles with a common edge (in Russian). Annuaire Univ. Sofia, Fac. Math. Inform. 82 (1988), 37--49; Corollary 3, p. 45, with Theorem 1, p. 40, Theorem 2, p. 43, Lemma 4, pp. 44--45, and Corollary 5, p. 45. Library home: Khadzhiivanov 1988; result page Corollary 3.
Ed77: Edwards, C. S., A lower bound for the largest number of triangles with a common edge (1977), listed by [FoLo12] as an unpublished manuscript; the independent source of the $n/6$ bound, quoted second-hand.
Po14: Potechin, A., A note on a problem of Erdős and Rothschild. arXiv:1412.1838v1 (4 December 2014; title page typeset 5 November 2018), 7 pages; Theorem 1.3 and Corollaries 1.4--1.5, p. 2. The thread cites it as [Po18]. Library home: Potechin 2014.
BoNi05: Bollobás, B. and Nikiforov, V., Books in graphs. European J. Combin. 26 (2005), 259--270. The near-threshold asymptotics, quoted second-hand from [FoLo12] p. 2 and [Po14] p. 2; not held.
AlTr: Alon, N. and Trotter, W. T., the bound $f_c(n)<c'\sqrt n$ for $c<1/4$ , unpublished; cited by [FoLo12] and [Po14] through [Er92], and by [Er87] as Alon's.

Problem 80

Status

Proof claims

Discussion