Erdős Problem #80

Erdős Problem 80: books in graphs whose edges all lie in triangles

1. Statement and scope

2. Two counts and an elementary linear bound

3. Qualitative divergence via triangle removal

4. A check on the density bound

5. Assessment and attribution

Completion rate estimate: 25%.

1) FORMAL RESTATEMENT.

Fix a constant $c>0$. For $n\in\mathbb{N}$, define $f_c(n)$ to be the largest integer $m$ with the property:

For every graph $G$ on $n$ vertices with at least $c n^2$ edges, such that every edge of $G$ lies in at least one triangle, there exists an edge of $G$ contained in at least $m$ distinct triangles.

Equivalently, for such a graph $G$ define its book size \[ \mathrm{bk}(G):=\max_{uv\in E(G)}\left|N(u)\cap N(v)\right|, \] (the maximum number of triangles sharing a common edge), and then \[ f_c(n)=\min\{\mathrm{bk}(G):\ |V(G)|=n,\ |E(G)|\ge c n^2,\ \forall e\in E(G)\ \exists\text{ triangle containing }e\}. \] The task is to estimate $f_c(n)$ as a function of $n$ (for fixed $c$), and in particular to decide whether $f_c(n)>n^{\varepsilon}$ for some $\varepsilon>0$ or whether $f_c(n)\gg \log n$.

2) QUICK LITERATURE/CONTEXT CHECK.

Per the integrity rule I only use results stated in the problem text: it records that for $c<1/4$ the conjecture $f_c(n)>n^{\varepsilon}$ is false, and that for $c>1/4$ one has $f_c(n)\ge n/6$ (with cited references). It also notes the existence of very poor lower bounds from the regularity lemma. I do not reproduce those deeper results here.

3) ATTACK PLAN.

Proof-track:

• Relate $\mathrm{bk}(G)$ to degrees and triangle counts via averaging and inequalities.
• For $c>1/4$, exploit density to force large common neighbourhoods on some edge.

• Exhibit dense triangle-rich graphs where every edge lies in triangles but no single edge has too many triangles (to show $f_c(n)$ cannot exceed some function).

Here I give two elementary lemmas that produce explicit (but not sharp) lower bounds, and an explicit tripartite construction giving a linear upper bound. I also include a small-$n$ exhaustive search sanity check.

4) WORK.

Fast reality check (small $n$ computation). For $n=7$ and $c=1/3$ (so the condition is $|E(G)|\ge \lceil \tfrac{1}{3}n^2\rceil=17$), an exhaustive enumeration over all $2^{\binom{7}{2}}=2^{21}$ graphs shows:

• among graphs with at least $17$ edges and with every edge in at least one triangle, the minimum possible book size is $4$;
• one witness graph achieving book size $4$ has $17$ edges: \[(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(4,5).\]

Lemma 80.1 (Book size as common neighbourhood; averaging identity). Let $G$ be a graph. For an edge $uv\in E(G)$, the number of triangles containing $uv$ equals $|N(u)\cap N(v)|$. Moreover, if $T(G)$ denotes the number of (unordered) triangles of $G$ and $m=|E(G)|$, then \[ \sum_{uv\in E(G)} |N(u)\cap N(v)| = 3T(G), \] and hence \[ \mathrm{bk}(G)\ge \frac{3T(G)}{m}. \]

Proof. A vertex $w$ forms a triangle with edge $uv$ iff $w$ is adjacent to both $u$ and $v$, i.e. $w\in N(u)\cap N(v)$. Thus the triangle count on $uv$ is $|N(u)\cap N(v)|$.

Each triangle $\{u,v,w\}$ contributes exactly $1$ to $|N(u)\cap N(v)|$, $|N(u)\cap N(w)|$, and $|N(v)\cap N(w)|$, i.e. it is counted exactly three times in the sum over edges. Therefore the sum equals $3T(G)$. The inequality for $\mathrm{bk}(G)$ follows because the maximum over edges is at least the average over edges. $\square$

Lemma 80.2 (Elementary density $\Rightarrow$ a linear-size book when $c>1/4$). Let $G$ be a graph on $n$ vertices with $m$ edges and degree sequence $(d_1,\dots,d_n)$. Then there exists an edge $uv\in E(G)$ with \[ |N(u)\cap N(v)|\ge \frac{4m-n^2}{n}. \] In particular, if $m\ge c n^2$ with $c>1/4$, then $\mathrm{bk}(G)\ge (4c-1)n$.

Proof. For an edge $uv\in E(G)$, let $s(uv):=d(u)+d(v)$.

Step 1: some edge has large endpoint-degree-sum. We compute the average of $s(uv)$ over edges: \[ \frac{1}{m}\sum_{uv\in E(G)} (d(u)+d(v)). \] Each vertex $x$ contributes $d(x)$ to the sum once for each incident edge, i.e. $d(x)$ is added $d(x)$ times. Hence \[ \sum_{uv\in E(G)} (d(u)+d(v)) = \sum_{x\in V(G)} d(x)^2. \] By Cauchy--Schwarz, \[ \sum_{x} d(x)^2 \ge \frac{\left(\sum_x d(x)\right)^2}{n} = \frac{(2m)^2}{n} = \frac{4m^2}{n}. \] Therefore the average endpoint-degree-sum satisfies \[ \frac{1}{m}\sum_{uv\in E(G)} (d(u)+d(v)) \ge \frac{4m}{n}. \] Hence there exists some edge $uv\in E(G)$ with \begin{equation}\label{wsref-0-65-71-3a-64-65-67-2d-73-75-6d} d(u)+d(v)\ge \frac{4m}{n}. \end{equation}

Step 2: degree-sum forces a large common neighbourhood. For this edge $uv$, \[ |N(u)\cap N(v)| = |N(u)|+|N(v)|-|N(u)\cup N(v)| \ge d(u)+d(v)-n, \] because $N(u)\cup N(v)\subseteq V(G)$ has size at most $n$. Combining with (eq:deg-sum) gives \[ |N(u)\cap N(v)|\ge \frac{4m}{n}-n = \frac{4m-n^2}{n}. \] If $m\ge c n^2$, this yields $|N(u)\cap N(v)|\ge (4c-1)n$. Since $\mathrm{bk}(G)$ is the maximum such common-neighbourhood size over edges, the same lower bound holds for $\mathrm{bk}(G)$. $\square$

Lemma 80.3 (Simple explicit upper bound via complete tripartite graphs). Let $n$ be divisible by $3$ and let $G$ be the complete tripartite graph with parts of size $n/3,n/3,n/3$. Then:

• $|E(G)|=\frac{1}{3}n^2$;
• every edge lies in exactly $n/3$ triangles;
• therefore $\mathrm{bk}(G)=n/3$.

Proof. Let the parts be $A,B,C$ with $|A|=|B|=|C|=n/3$. Edges are exactly the cross edges between distinct parts. The total number of edges is \[ |A||B|+|A||C|+|B||C| = 3\cdot \frac{n}{3}\cdot \frac{n}{3}=\frac{1}{3}n^2. \] An edge between (say) $A$ and $B$ forms a triangle with any choice of a vertex in $C$, and with no other vertices. Thus every $A$--$B$ edge lies in exactly $|C|=n/3$ triangles, and similarly for the other cross edges. Therefore the maximum number of triangles sharing a common edge is $n/3$.

If $c\le 1/3$, then $|E(G)|=n^2/3\ge c n^2$, so $G$ is an admissible example for the minimisation defining $f_c(n)$, giving $f_c(n)\le \mathrm{bk}(G)=n/3$. $\square$

5) VERIFICATION.

• Lemma 80.1 is a direct double count and matches the book definition.
• Lemma 80.2: the only nontrivial ingredients are the identity $\sum_{uv\in E}(d(u)+d(v))=\sum_v d(v)^2$, Cauchy--Schwarz, and inclusion--exclusion with the bound $|N(u)\cup N(v)|\le n$.
• The $n=7$, $c=1/3$ exhaustive computation yields a minimum book size $4$, which is consistent with Lemma 80.2's lower bound $(4c-1)n=(1/3)\cdot 7\approx 2.33$ (i.e. at least $3$ as an integer bound).

6) FINAL.

UNRESOLVED

(i) Strongest proved partial result: For any graph with $m\ge c n^2$ edges, there is an edge in at least $(4c-1)n$ triangles (Lemma 80.2), giving $f_c(n)\ge (4c-1)n$ for $c>1/4$. Also, for $c\le 1/3$ there are explicit examples with $\mathrm{bk}(G)=n/3$, so $f_c(n)\le n/3$ (Lemma 80.3). Exhaustive search shows for $(n,c)=(7,1/3)$ one can achieve book size $4$.

(ii) First gap (crisp): Determine the correct order of growth of $f_c(n)$ for $c<1/4$ and obtain a meaningful (non-regularity) lower bound tending to infinity (e.g. prove $f_c(n)\gg \log n$) under the "every edge lies in a triangle" constraint.

(iii) Top 3 next moves (concrete):

1. Strengthen Lemma 80.2 by incorporating the hypothesis "every edge is in a triangle" to obtain a lower bound independent of $(4c-1)$ when $c>1/4$ (target: prove $\mathrm{bk}(G)\ge \gamma n$ for an absolute $\gamma>0$).
2. For $c<1/4$, attempt explicit constructions (or computational searches for moderate $n$) that minimise $\mathrm{bk}(G)$ while keeping all edges in triangles; identify candidate extremal families.
3. Derive a lower bound on the triangle count $T(G)$ in terms of $m$ under the additional constraint that every edge lies in a triangle, then combine with Lemma 80.1 to force a large average common neighbourhood.

(iv) Minimal counterexample structure (to $f_c(n)\gg \log n$): a sequence of graphs $G_n$ with $|E(G_n)|\ge c n^2$, every edge in a triangle, but with $\mathrm{bk}(G_n)=O(\log n)$ (or $n^{o(1)}$). Such graphs would have triangles "spread out" so that no single edge has many common neighbours, suggesting a highly pseudorandom local common-neighbour structure together with a global density constraint.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. - For a finite simple graph $G=(V,E)$, write $n:=|V|$ and $m:=|E|$. - For an edge $e=uv\in E$, define the book-size at $e$ as \[b_G(uv):=\big|\{w\in V\setminus\{u,v\}: uw\in E,\ vw\in E\}\big|,\] the number of triangles containing the edge $uv$. - The book size of $G$ is \[B(G):=\max_{uv\in E} b_G(uv).\]

For a fixed constant $c>0$, define $f_c(n)$ to be the largest integer $m$ such that every $n$-vertex graph $G$ with 1. $|E(G)|\ge c n^2$, and 2. every edge of $G$ lies in at least one triangle (equivalently $b_G(uv)\ge 1$ for all $uv\in E$), satisfies $B(G)\ge m$. Equivalently, $f_c(n)=\min\{B(G): G \text{ satisfies (1) and (2)}\}$.

Question. Estimate the growth of $f_c(n)$ as $n\to\infty$ (for fixed $c$). In particular, for $c<1/4$ must $f_c(n)$ still grow (e.g. $\gg\log n$)?

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. From the problem text only: - For $c<1/4$, Alon--Trotter gave an upper bound $f_c(n)\ll_c n^{1/2}$. - Szemerédi observed $f_c(n)\to\infty$ via regularity lemma. - For $c>1/4$, a linear lower bound $f_c(n)\ge n/6$ is stated. - For $c<1/4$, Fox--Loh proved a subpolynomial upper bound $f_c(n)\le n^{O(1/\log\log n)}$. I do not re-prove these results here.

3) ATTACK PLAN Proof track ideas: 1. Relate $B(G)$ to degree information via common-neighbor counts. For $c>1/4$ one expects linear books from "supersaturation" of triangles. 2. For $c<1/4$, leverage the extra hypothesis that every edge lies in a triangle (a global covering constraint) to force some growth of $B(G)$.

Disproof track ideas: 1. For $c<1/4$, try to build dense graphs where edges lie in triangles but each edge is in very few triangles, i.e. $B(G)$ grows slowly.

Chosen path in this attempt: derive two elementary lemmas that already imply a linear lower bound when $c>1/4$, and give the basic book/common-neighbor identities.

4) WORK Lemma 1 (Book size equals maximum edge codegree). For an edge $uv\in E(G)$, \[b_G(uv)=|N(u)\cap N(v)|,\] where $N(u)$ is the neighbor set of $u$. In particular, $B(G)=\max_{uv\in E(G)} |N(u)\cap N(v)|$.

Proof. A vertex $w$ forms a triangle $u-v-w-u$ with edge $uv$ iff $w$ is adjacent to both $u$ and $v$, i.e. $w\in N(u)\cap N(v)$. Counting such $w$ gives the identity. $\square$

Lemma 2 (Degree-sum averaging over edges). Let $G$ be a graph with degrees $d(v)$ and $m$ edges. Then \[\frac{1}{m}\sum_{uv\in E(G)}\big(d(u)+d(v)\big) = \frac{1}{m}\sum_{v\in V(G)} d(v)^2 \ \ge\ \frac{4m}{n}.\] Consequently there exists an edge $uv\in E(G)$ with \[d(u)+d(v)\ge \frac{4m}{n}.\]

Proof. For the first identity, each vertex $v$ contributes $d(v)$ to the sum $\sum_{uv\in E}(d(u)+d(v))$ for each incident edge, i.e. $d(v)$ times, so the total contribution is $d(v)^2$. Summing over vertices gives $\sum_{uv\in E}(d(u)+d(v))=\sum_v d(v)^2$.

For the inequality, apply Cauchy--Schwarz: \[\sum_v d(v)^2 \ge \frac{1}{n}\left(\sum_v d(v)\right)^2=\frac{(2m)^2}{n}=\frac{4m^2}{n}.\] Divide by $m$ to obtain the displayed bound. The existence of an edge with degree-sum at least the average is immediate. $\square$

Lemma 3 (From large degree-sum to a large book). For any edge $uv\in E(G)$, \[|N(u)\cap N(v)| \ge d(u)+d(v)-(n-2).\] In particular, if $d(u)+d(v)\ge n-1$ then $uv$ lies in at least one triangle.

Proof. We have \[|N(u)\cap N(v)| = |N(u)|+|N(v)|-|N(u)\cup N(v)|=d(u)+d(v)-|N(u)\cup N(v)|.\] Since $N(u)\cup N(v)\subseteq V\setminus\{u,v\}$, its size is at most $n-2$. Substituting gives the lower bound. $\square$

Corollary 4 (A clean linear lower bound when $m>n^2/4$). If $G$ has $n$ vertices and $m$ edges, then \[B(G)\ge \max\!\left(0,\frac{4m}{n}-(n-2)\right).\] In particular, if $m\ge c n^2$ with $c>1/4$, then for all sufficiently large $n$, \[B(G)\ge (4c-1)n.\]

Proof. By Lemma 2, there exists an edge $uv$ with $d(u)+d(v)\ge 4m/n$. Then Lemma 3 gives \[b_G(uv)=|N(u)\cap N(v)|\ge \frac{4m}{n}-(n-2).\] Taking the maximum over edges yields the first inequality, and the second follows by substituting $m\ge c n^2$ and absorbing the $+2$ into $(4c-1)n$ for $n$ large. $\square$

FAST REALITY CHECK - Corollary 4 shows that for $c>1/4$ one gets an elementary linear book-size lower bound (without using the extra hypothesis that every edge lies in a triangle). - For $c<1/4$, Corollary 4 becomes vacuous, so the real difficulty is to use the hypothesis that every edge lies in a triangle to force $B(G)\to\infty$.

5) VERIFICATION - Lemma 2 identity $\sum_{uv\in E}(d(u)+d(v))=\sum_v d(v)^2$ holds by grouping contributions by endpoint. - Lemma 3 is a union bound on neighborhoods, with the only subtlety being $|N(u)\cup N(v)|\le n-2$. - Corollary 4 is a clean pipeline: average degree-sum $\Rightarrow$ large degree-sum edge $\Rightarrow$ large intersection.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: An elementary argument shows that any graph with $m$ edges satisfies \[B(G)\ge \max\!\left(0,\frac{4m}{n}-(n-2)\right)\] and hence if $m\ge c n^2$ with $c>1/4$ then $B(G)\ge (4c-1)n$ for large $n$ (Corollary 4).

(ii) First gap: Use the additional constraint "every edge lies in a triangle" to prove any meaningful lower bound on $B(G)$ when $c<1/4$ (e.g. $B(G)\to\infty$ or $B(G)\gg\log n$).

(iii) Top 3 next moves (concrete): 1. Translate the constraint "every edge lies in a triangle" into a lower bound on the average edge-codegree $\frac{1}{m}\sum_{uv\in E}|N(u)\cap N(v)|$ that is stronger than $1$ when $m=cn^2$. 2. Try to prove that if all edge-codegrees are $\le B$, then the edge set must be close to bipartite (few triangles), contradicting that every edge is in a triangle. 3. Implement a small optimization search (for fixed $n$ and edge density $c$) to minimize $B(G)$ under the "all edges in triangles" constraint, to guess the true growth for representative $c<1/4$.

(iv) What a minimal counterexample would likely look like (structure/parameters): For some fixed $c<1/4$, a family of graphs $G_n$ with $|E|=\Theta(n^2)$ where every edge lies in at least one triangle, but every edge lies in at most $n^{o(1)}$ triangles, i.e. the graph locally has triangles everywhere but no edge participates in many.