Erdős Problem #128

Erdős Problem 128: a sparse half in a triangle-free graph

Statement and scope

We retain the valid averaging framework of the earlier GPT-5.2 attempts, supply a complete minimization for the balanced five-cycle example, and prove a restricted affirmative case. The minimization explicitly permits redistribution between nonadjacent fractional coordinates, a step missing from the earlier rounding argument. These are known elementary bounds and examples, not a new solution.

A universal bound with denominator 16

For $n\ge2$, a uniformly random $q$-set, $q=\lfloor n/2\rfloor$, has expected induced edge count \[ m\frac{q(q-1)}{n(n-1)}\le\frac m4. \] Some such set therefore has at most $n^2/16$ edges. The case $n=1$ is immediate. In particular the desired denominator-50 conclusion holds whenever $m\le2n^2/25$. It also holds with zero edges whenever the graph has an independent set of size $q$, for example if some vertex has degree at least $q$, since a triangle-free neighbourhood is independent.

Exact minimization in a five-cycle blow-up

Scale to $u_i=x_i/t$. The objective $\Phi(u)=\sum u_i u_{i+1}$ is coordinatewise nondecreasing, so it suffices to minimize it on $[0,1]^5$ with $\sum u_i=5/2$. A minimizer exists by compactness. If two coordinates $u_i,u_j$ are fractional, replace them by $u_i+s,u_j-s$, keeping all others fixed. On the feasible interval of $s$, the objective is linear when $i,j$ are nonadjacent and a concave quadratic with coefficient $-1$ on $s^2$ when they are adjacent. Its minimum on that interval is attained at an endpoint. Thus at least one of the two coordinates can be made zero or one without increasing the objective.

Repeating leaves at most one fractional coordinate. The sum constraint then forces two coordinates equal to one, one equal to $1/2$, and the others zero. If the two ones are adjacent, they contribute one. If they are nonadjacent, the half-coordinate must be adjacent to at least one of them, since the five-cycle has no independent three-set. Its contribution is at least $1/2$. Therefore $\Phi\ge1/2$ in all cases.

For even $t$, equality occurs at \[ (x_0,x_1,x_2,x_3,x_4)=(t,0,t,0,t/2). \] The selected set has exactly $n/2$ vertices and exactly $t^2/2=n^2/50$ edges; every set with at least $n/2$ vertices has at least this many. Taking arbitrarily large even $t$ proves that a universal upper bound strictly smaller than $n^2/50$ is impossible.

Remaining gap

COMPLETION ESTIMATE

1) FORMAL RESTATEMENT

Let $G$ be a (simple) graph on $n$ vertices. Assume that every induced subgraph of $G$ on at least $\lfloor n/2\rfloor$ vertices has more than $n^2/50$ edges.

Question. Must $G$ contain a triangle (a copy of $K_3$)?

The text notes that if true, the constant 50 would be best possible, witnessed by a blow-up of $C_5$ or by the Petersen graph. It also notes (as a known result) that the statement is true with 50 replaced by 16 (EFRS94).

2) QUICK LITERATURE/CONTEXT CHECK

(Restricted to statements explicitly present in 123-137.tex.) - The theorem is known to hold with 50 replaced by 16. - The constant 50, if achievable, is best possible (blow-up of $C_5$ or Petersen graph).

3) ATTACK PLAN

- Verify the extremal example: balanced blow-up of $C_5$ is triangle-free and has a half-sized induced subgraph with exactly $n^2/50$ edges. - Prove general necessary conditions from averaging (random half-subset). - The main triangle-forcing statement at 50 appears open here; provide partial bounds and the tightness construction.

4) WORK

Definition (balanced blow-up of $C_5$). Let $t\ge 1$ and let $V_1,\dots,V_5$ be disjoint independent sets of size $t$. Connect every vertex of $V_i$ to every vertex of $V_{i\pm 1}$ (indices modulo 5), and add no other edges. Call the resulting graph $G_{5,t}$. It has $n=5t$ vertices.

Lemma 4.1 (Triangle-free). $G_{5,t}$ contains no triangle.

Proof. Any edge in $G_{5,t}$ goes between two parts $V_i$ and $V_{i\pm 1}$. A triangle would use three parts $V_{i_1},V_{i_2},V_{i_3}$ with all three pairwise adjacent in the underlying 5-cycle. But $C_5$ has no triangle, so among three vertices of the cycle, at least one pair is nonadjacent; correspondingly, the blow-up has no edge between those two parts. Hence no triangle exists. $\square$

Lemma 4.2 (A half-subgraph with exactly $n^2/50$ edges). Assume $t$ is even so that $n/2=5t/2$ is an integer. Then $G_{5,t}$ has an induced subgraph on exactly $n/2$ vertices with exactly $n^2/50$ edges.

Proof. Take all $t$ vertices from $V_1$ and all $t$ vertices from $V_3$ (these parts are nonadjacent in the 5-cycle, so there are no edges between them), and take $t/2$ vertices from $V_5$. This gives a vertex set $S$ of size $t+t+t/2=5t/2=n/2$. Edges inside $S$ occur only between $V_5$ and $V_1$ (since $V_5$ is adjacent to $V_1$, and $V_5$ is not adjacent to $V_3$). Thus \[ e(G[S]) = |S\cap V_5|\cdot |S\cap V_1| = (t/2)\cdot t = t^2/2. \] Since $n=5t$, we have $n^2/50 = 25t^2/50 = t^2/2$, so indeed $e(G[S])=n^2/50$. $\square$

Lemma 4.3 (Averaging over random half-subsets). Let $G$ be any graph on $n$ vertices with $m$ edges. Then there exists an induced subgraph on $\lfloor n/2\rfloor$ vertices with at most $m/4$ edges.

Proof. Choose a uniformly random subset $S$ of vertices of size $\lfloor n/2\rfloor$. Each edge of $G$ is present in $G[S]$ exactly when both endpoints are chosen. The probability a fixed edge survives is \[ \frac{\binom{\lfloor n/2\rfloor}{2}}{\binom{n}{2}} \le \frac{(n/2)(n/2-1)}{n(n-1)} < \frac14. \] By linearity of expectation, $\mathbb{E}[e(G[S])] < m/4$, so some choice of $S$ has $e(G[S])\le m/4$. $\square$

FAST REALITY CHECK (computation). For $G_{5,t}$, I brute-forced the minimum number of edges in an induced subgraph on $n/2$ vertices for small $t$: - $t=2$ ($n=10$): minimum is 2, and $n^2/50=2$. - $t=4$ ($n=20$): minimum is 8, and $n^2/50=8$. This matches Lemma 4.2 and supports the claim that 50 is the correct tight constant for this construction.

5) VERIFICATION

- Lemma 4.1 is immediate from the projection-to-$C_5$ argument. - Lemma 4.2 is an explicit construction and the edge count is exact. - Lemma 4.3 is a standard expectation argument; the inequality giving $<1/4$ is correct for $n\ge 2$.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result: - The balanced blow-up of $C_5$ is triangle-free (Lemma 4.1) and has a half-sized induced subgraph with exactly $n^2/50$ edges (Lemma 4.2), showing the constant 50 is tight for this example. - Any graph with total edge count $m$ always has a half-subset with at most $m/4$ edges (Lemma 4.3), giving a necessary constraint relating the hypothesis to the global density.

(ii) Exact first gap: - Prove or disprove the main statement: does the local condition "every induced subgraph on at least $n/2$ vertices has $>n^2/50$ edges" force a triangle?

(iii) Top 3 next moves: 1. Attempt to sharpen Lemma 4.3 using triangle-free constraints (e.g. apply Mantel-type bounds to induced subgraphs and optimize). 2. Analyze extremal triangle-free graphs with constrained "sparse halves"; show that any triangle-free graph must contain a half-subset with at most $n^2/50$ edges. 3. Compare with the known 16-result: identify which steps lose constant factors and whether they can be pushed to 50.

(iv) What a minimal counterexample would likely look like: - A triangle-free graph that is highly pseudorandom at the half-subgraph scale, preventing the selection of a sparse half, and whose structure resembles a blow-up of a small triangle-free graph (like $C_5$) but with all halves slightly denser than $n^2/50$.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. - Graphs are finite, simple, undirected. - For a graph $G$ and $S\subseteq V(G)$, write $G[S]$ for the induced subgraph and $e(G[S])$ for its number of edges.

Question. If $G$ has $n$ vertices and satisfies \[\forall S\subseteq V(G)\ \big(|S|\ge \lfloor n/2\rfloor \implies e(G[S])> n^2/50\big),\] must $G$ contain a triangle (a $K_3$ subgraph)?

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. From the statement only: - The claim is known with $50$ replaced by $16$. - The constant $50$ is claimed to be best possible (blow-up of $C_5$ / Petersen). I will not use external results beyond standard inequalities I explicitly prove below.

3) ATTACK PLAN Proof track ideas: 1. Work by contrapositive: assume $G$ is triangle-free, and try to find a subset $S$ of size $\ge n/2$ with few edges. 2. Use averaging over random subsets to guarantee an $S$ with edge count near the mean, then combine with global bounds on $e(G)$ (e.g. Turán) to get explicit constants. 3. To approach the sharp constant $50$, exploit specific structure of near-extremal triangle-free graphs (non-bipartite, like blow-ups of $C_5$).

Disproof track ideas: 1. Try to construct triangle-free graphs where every half-subset induces many edges, pushing the constant downward; the statement suggests $C_5$ blow-ups reach the threshold $50$.

Chosen path in this attempt: prove (i) the easy constant $16$ via averaging and Turán, and (ii) verify sharpness of $50$ for the balanced blow-up of $C_5$ by an explicit minimization over half-subsets.

4) WORK Lemma 1 (Averaging over half-subsets). Let $G$ be a graph on $n$ vertices with $m$ edges, and let $S$ be a uniformly random subset of $V(G)$ of size $\lfloor n/2\rfloor$. Then \[\mathbb E[e(G[S])] = m\cdot \frac{\binom{\lfloor n/2\rfloor}{2}}{\binom{n}{2}} \le \frac{m}{4}.\] In particular, there exists some $S$ with $|S|=\lfloor n/2\rfloor$ such that $e(G[S])\le m/4$.

Proof. Each edge $uv\in E(G)$ contributes $1$ to $e(G[S])$ exactly when both endpoints are chosen in $S$. For a fixed edge, the probability that both endpoints lie in a uniform $t$-subset is $\binom{t}{2}/\binom{n}{2}$ where $t=\lfloor n/2\rfloor$. By linearity of expectation, \[\mathbb E[e(G[S])] = m\cdot \frac{\binom{t}{2}}{\binom{n}{2}}.\] Since $t\le n/2$, we have $\binom{t}{2}/\binom{n}{2}\le (t/n)^2\le 1/4$, giving the inequality. The existence of some $S$ with $e(G[S])\le \mathbb E[e(G[S])]$ follows because the average of $e(G[S])$ over all such $S$ equals the expectation. $\square$

Lemma 2 (Easy "16" version via Turán + averaging). If $G$ is triangle-free on $n$ vertices, then there exists $S\subseteq V(G)$ with $|S|=\lfloor n/2\rfloor$ and \[e(G[S])\le \frac{n^2}{16}.\] Consequently, if every induced subgraph on $\ge \lfloor n/2\rfloor$ vertices has $>n^2/16$ edges, then $G$ must contain a triangle.

Proof. If $G$ is triangle-free, then by Turán's theorem (forbidding $K_3$) one has $m=e(G)\le n^2/4$. Apply Lemma 1 to obtain a set $S$ of size $\lfloor n/2\rfloor$ with $e(G[S])\le m/4 \le (n^2/4)/4=n^2/16$. The final contrapositive statement is immediate. $\square$

Lemma 3 (Balanced $C_5$ blow-up achieves the $1/50$ half-density threshold). Let $n=5m$ with $m\ge 1$. Partition the vertex set into five parts $V_0,\dots,V_4$ each of size $m$, and form the balanced blow-up of $C_5$: add all edges between $V_i$ and $V_{i+1}$ (indices mod $5$), and no other edges. Call this graph $H_{m}$. Then: 1. $H_m$ is triangle-free. 2. Every subset $S\subseteq V(H_m)$ with $|S|\ge \lceil n/2\rceil=\lceil 5m/2\rceil$ satisfies \[e(H_m[S])\ge \frac{n^2}{50}=\frac{m^2}{2}.\] 3. If $m$ is even, there exists $S$ with $|S|=n/2$ and $e(H_m[S])=n^2/50$.

Proof. $1$ Any edge of $H_m$ joins two consecutive parts. A triangle would require three pairwise adjacent vertices, hence would require edges between three parts. But in $C_5$, no three distinct vertices are pairwise adjacent, so $H_m$ has no triangle.

$2$ Let $x_i:=|S\cap V_i|$ for $i\in\{0,1,2,3,4\}$. Then $0\le x_i\le m$ and $\sum_{i=0}^4 x_i = |S|\ge \lceil 5m/2\rceil$. Since edges exist only between consecutive parts, the induced edge count is \[e(H_m[S]) = \sum_{i=0}^4 x_i x_{i+1}\qquad(\text{indices mod }5).\tag{*}\]

We claim that under the constraints $0\le x_i\le m$ and $\sum x_i\ge 5m/2$, one has $\sum x_i x_{i+1}\ge m^2/2$. To see this, scale $y_i:=x_i/m\in[0,1]$ and note $\sum y_i\ge 5/2$. The function $F(y):=\sum y_i y_{i+1}$ is nondecreasing in each coordinate (all coefficients are nonnegative), so its minimum under $\sum y_i\ge 5/2$ occurs when $\sum y_i=5/2$.

So assume $\sum y_i=5/2$. Consider minimizing $F(y)$ over the polytope $\{y\in[0,1]^5:\sum y_i=5/2\}$. Fix an index $i$ and write $a=y_i$, $b=y_{i+1}$, $u=y_{i-1}$, $v=y_{i+2}$. Holding $u,v$ and the sum $a+b=s$ fixed, the part of $F$ involving $a,b$ is \[T(a,b)=au+ab+bv = a(u+s-a) + (s-a)v = -a^2 + a(u+s-v) + sv,\] which is a concave quadratic in $a$ (coefficient $-1$). Therefore, for fixed $s$ and fixed other coordinates, $T(a,s-a)$ is minimized at an endpoint of the allowed interval for $a$. Thus we may adjust $(a,b)$ while keeping $a+b$ fixed to reach a boundary point (one of $a,b$ in $\{0,1\}$) without increasing $F$. Iterating over pairs shows there is a minimizer of $F$ with at most one coordinate not in $\{0,1\}$.

But with $\sum y_i=5/2$, any point with at most one fractional coordinate must have exactly two coordinates equal to $1$, two equal to $0$, and one equal to $1/2$. A direct check of the cyclic product sum in this case shows: - If the two $1$'s are adjacent, then $F\ge 1$. - If the $1/2$ is adjacent to both $1$'s, then $F\ge 1$ (two edges each contributing $1/2$). - The minimal configuration is when the two $1$'s are at distance $2$ on the cycle and the $1/2$ is adjacent to exactly one of them (e.g. $(1,0,1,0,1/2)$ up to rotation), in which case exactly one edge contributes $1\cdot(1/2)$ and all other edges touch a $0$, so $F=1/2$. Hence the minimum of $F$ is $1/2$, proving $\sum y_i y_{i+1}\ge 1/2$ and therefore $\sum x_i x_{i+1}\ge (m^2)(1/2)=m^2/2$. Combining with $*$ gives $e(H_m[S])\ge m^2/2=n^2/50$.

$3$ If $m$ is even, take $x_0=x_2=m$ and $x_4=m/2$ with $x_1=x_3=0$ (i.e. $S$ consists of all vertices in $V_0$ and $V_2$, and half of $V_4$). Then $|S|=m+m+m/2=5m/2=n/2$ and $*$ gives \[e(H_m[S])=x_4x_0=\frac{m}{2}\cdot m=\frac{m^2}{2}=\frac{n^2}{50}.\] This shows the lower bound in $2$ is tight (at least when $m$ is even). $\square$

FAST REALITY CHECK (local computation for small $m$). I brute-forced the minimization of $\sum x_i x_{i+1}$ over integer vectors $0\le x_i\le m$ with $\sum x_i\ge \lceil 5m/2\rceil$ for $m\le 6$. The minimum achieved equals $m^2/2$ for even $m$ and is larger for odd $m$, consistent with Lemma 3$2$--$3$.

5) VERIFICATION - Lemma 1 is a standard linearity-of-expectation argument for induced edge counts in uniform random subsets. - Lemma 2 uses only Turán's theorem for triangle-free graphs and the averaging lemma. - Lemma 3$2$ reduces the extremal half-subset question in the $C_5$ blow-up to a 5-variable minimization problem and shows the minimum occurs at a boundary configuration; the explicit configuration in $3$ achieves equality for even $m$.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: I proved an elementary version of the statement with constant $16$ (Lemma 2) and verified that the balanced blow-up of $C_5$ is triangle-free yet forces every half-subset to span at least $n^2/50$ edges (Lemma 3), showing $50$ is the natural sharp threshold.

(ii) First gap: Close the gap between $1/16$ and $1/50$: show that every triangle-free graph has some induced subgraph on $\ge n/2$ vertices with at most $n^2/50$ edges, or construct a counterexample.

(iii) Top 3 next moves (concrete): 1. Refine Lemma 1 by choosing non-uniform distributions for $S$ (biased toward low-degree vertices) to push the guaranteed sparse-half edge count below $n^2/16$ for triangle-free graphs. 2. Analyze near-extremal triangle-free graphs (close to the Turán bound $n^2/4$) and try to prove they must have particularly sparse halves unless they resemble $C_5$-type blow-ups. 3. Try to prove a stability statement: if every half-subset has many edges, then $G$ must be structurally close to a blow-up of $C_5$ (or Petersen), which is the claimed extremal configuration.

(iv) What a minimal counterexample would likely look like (structure/parameters): A triangle-free graph $G$ on $n$ vertices such that every induced subgraph on $\ge n/2$ vertices spans strictly more than $n^2/50$ edges, yet $G$ is not close in structure to a $C_5$ blow-up; such a graph would disprove the conjectured sharp constant.