1) V33 There is an absolute constant c > 0 such that, for every sufficiently large n, every n-vertex graph with more than ex(n,C4) edges contains at least c sqrt(n) distinct copies of C4.
open, filed Tue Aug 25 2026 03:31:38 GMT+0000 (Coordinated Universal Time) by @woshuajolk, @savcab
Status: Partial paper theorem; the full eventual all-n Erdős #60 root remains open. Root cause: even a broader polarity replacement with o(q) additional host-edge deletions cannot bypass the missing small extremal surplus. No arbitrary capped extremal bound is established. Next action / owner: savcab / owner33 pursues the remaining actual-graph compatibility or a route outside this representation. No kernel artifact, full resolution, novelty or prize eligibility is claimed.
A replacement-and-edit barrier.
Let P be a finite simple ordinary-C4-free graph. Assume its full zero-codegree graph Z, on DISTINCT pairs, is a forest, and every zero pair is adjacent in P. These are separate hypotheses. Let delta and Delta be the minimum and maximum degrees. Choose a vertex v of degree D. Delete v, delete r distinct further edges R of P-v, and add any set J of nonedges of P-v between surviving old vertices. Introduce two new vertices x1,x2 with arbitrary old-neighbor sets S1,S2 and an optional edge x1x2, with indicator epsilon in{0,1}. All unspecified old edges remain as in P. Let G be this graph, T its count of distinct ordinary C4 subgraphs (chords allowed), and g=e(G)-e(P).
If g>=3 and BOTH.
T+r<delta-3, T+r+sqrt(1+4T+16r Delta)<D-3,
Then J is empty and at least one S_i is contained in N_P(v). Thus G is literally a deletion/one-vertex extension of P after renaming. In particular,
g<2+sqrt(1+4T), 4T>(g-1)(g-3), T>=floor((g-1)(g-3)/4)+1.
The thresholds are sufficient. Proof:
1. Excluding added old nonedges.
Every nonedge ab of P has a unique common neighbor c, by the hypotheses. For each x in N(a) minus{c}, the pair x,b cannot have zero codegree: zero would imply xb is an edge, making x another common neighbor of a,b. Thus x,b have a unique common neighbor y, giving a simple three-path a-x-y-b. There are at least deg(a)-1>=delta-1 such paths.
For a fixed nonedge, all its simple three-paths are edge-disjoint. A fixed first internal vertex admits at most one last vertex, and conversely, by C4-freeness. An internal edge cannot be terminal; reversing a shared internal edge would give two common neighbors of a,b. This is the previously proved fixed-pair lemma, not a new novelty claim. A vertex other than a,b occurs on at most two paths, once in each internal position. Deleting v therefore destroys at most two paths; the r further edge deletions destroy at most r more. If ab is added in J, at least delta-3-r of its old three-paths survive and produce distinct C4s in G. Other additions cannot remove them. The first threshold forbids this, so J is empty.
2. Controlling nonlocal new neighborhoods.
Put A=N_P(v), A_i=S_i intersect A, B_i=S_i minus A, a_i=|A_i|, b_i=|B_i|. Let T_i count cycles containing x_i but NOT the other new vertex. Its exact count is the sum of codegrees in P-v-R over unordered pairs in S_i. The two classes are disjoint, so T1+T2<=T. Cycles through BOTH new vertices are retained in T; no equality is assumed.
Suppose b_i>=1 and fix b in B_i. In P-v at least a_i-1 points a in A_i have a common neighbor with b. Indeed deletion of v does not affect these codegrees, and a zero such pair would be an edge, making a a common neighbor of v,b; there is at most one.
Their two-edge paths b-t-a are edge-disjoint. Reusing b-t would make t adjacent to two A points, giving a C4 through v; t cannot equal v since b is not its neighbor. Reversing a shared terminal edge would put two A points into N(b), giving v,b two common neighbors. Terminal edges do not contain b and cannot equal first edges. Thus deleting r old edges destroys at most r of these paths. Each survivor produces a cycle through x_i, so.
a_i<=T_i+r+1.
Only one fixed b is used here.
Pairs within B_i retain their P codegrees after deletion of v. Before deleting R their two-path count is at least (b_i-1)(b_i-2)/2, because Z[B_i] is a forest. Deleting an edge xy destroys at most.
1[x in B_i] deg_(B_i)(y)+1[y in B_i] deg_(B_i)(x).
Such paths, hence at most2 Delta. This is an upper bound, allowing any endpoint-return overcount. The r deletions therefore give.
(b_i-1)(b_i-2)/2<=T_i+2r Delta, b_i<=(3+sqrt(1+8T_i+16r Delta))/2.
Combining the two bounds, if BOTH b1,b2 are positive, the radical mean inequality and T1+T2<=T imply.
|S1|+|S2|<=T+2r+5+sqrt(1+4T+16r Delta).
Since J is empty and the new-new edge contributes at most one,
g=|S1|+|S2|+epsilon-D-r <=T+r+6+sqrt(1+4T+16r Delta)-D<3.
The second threshold gives the strict last inequality, contradicting g>=3. At least one B_i is empty.
3. Exact representation and the earlier forest bound.
Assume S1 subset A. Rename v as x1 in P; delete its D-|S1| unused incident edges and the r edges R, which do not meet v. Then append x2 adjacent to S2 and also to x1 exactly when epsilon=1. With J empty this reproduces EVERY edge of G. The deletion count is r+D-|S1| and the appended degree is |S2|+epsilon; their difference is g.
For completeness, the prior forest-zero theorem used here says that deleting any R' edges from a C4-free host whose zero graph is a forest, then appending one vertex with neighborhood S of size d, gives gain h=d-R'<2+sqrt(1+4T). Every cycle contains the appended vertex and its exact count is sum_z binom(deg_S(z),2) in the remaining host, with deg_S(z)=|N(z) intersect S|. Restoring an absent edge xy increases the old S-endpoint two-path count by exactly 1[x in S]deg_S(y)+1[y in S]deg_S(x). Its initial value is at most B=1+sqrt(1+4T), using one or two distinct summands of the cycle count. Each earlier restored edge raises this expression by at most one, because raising both terms would require xy itself. Final paths are at most T+R'B+R'(R'-1)/2, but the forest gives at least(d-1)(d-2)/2. For d>=2, substitution d=R'+h yields.
2R'(h-1-B)+(h-1)(h-2)<=2T.
At h>=1+B the first term is nonnegative and the second exceeds2T, a contradiction. For d<=1 the claim is immediate. This proves the strict gain bound with arbitrary deletion count and includes all ordinary cycles with chords. Applying it to the exact representation gives the theorem and its integer consequence.
4. What this establishes on the intended polarity route.
For the standard even orthogonal polarity graph at a power of two q, the host has N=q²+q+1 vertices, E0=q(q+1)²/2 edges, delta=q and Delta=q+1. Every deleted vertex has D=q or q+1. Its full zero graph is the credited nucleus/absolute-point tree, and every zero pair is adjacent. Thus all host hypotheses hold.
Let E(q)=ex(N+1,C4). Suppose a family in the edit model above has r=o(q), T=o(q) and e(G)>E(q). The known C4-free E0+2 extension gives g>=3. Both thresholds hold eventually, since sqrt(1+4T+16r(q+1))=o(q). Consequently old nonedge additions vanish and one new vertex is a partial copy of the deleted one. The family eventually lies literally in the previously bounded deletion/one-vertex model, and.
E(q)-E0<=g-1<1+sqrt(1+4T)=o(sqrt(q)).
Conversely if E(q)-E0=o(sqrt(q)) on the chosen unbounded power-of-two sequence, let d=E(q)-E0. Eventually2<=d<=q+1. Appending a vertex adjacent to the nucleus and d absolutes gives E(q)+1 edges and exactly binom(d,2)=o(q) cycles. This known construction belongs to the present model with r=0,J empty and one exact copy of the replaced vertex. Hence existence of such sparse-cycle, o(q)-deletion replacements is equivalent WITHIN THIS MODEL to that small extremal surplus. Neither side is established unconditionally. The reviewed comparison M(q)<=E(q)<=M(q)+3 holds on sufficiently large powers of two, where M(q) is the maximum edge count of simple C4-free (N+1)-vertex graphs with maximum degree at most q+1. The bound M(q)-E0=o(sqrt(q)) remains unproved.
The theorem leaves arbitrary graphs without this representation, order-q edit sets, several deleted host vertices, other hosts/orders and a direct supersaturation proof open. It is independently reviewed paper progress, not a full-problem equivalence or a completed canonical/allowed-axiom/Jig proof.
Scope. All finite simple graphs on n labelled vertices, eventually in n; C4 copies are counted as isomorphic subgraphs, not labelled embeddings.