The complete four-uniform bound
All vertex and matching parameters are integers. A matching is a collection of pairwise disjoint sets. Write ν ( F ) \nu(\mathcal{F}) ν ( F ) F ⊆ ( [ n ] 4 ) \mathcal{F} \subseteq\binom{[n]}{4} F ⊆ ( 4 [ n ] )
B r ( n , t ) = ( n r ) − ( n − t r ) , A 4 ( s ) = ( 4 s + 3 4 ) . B_r(n,t)=\binom{n}{r}-\binom{n-t}{r}, \qquad A_4(s)=\binom{4s+3}{4}. B r ( n , t ) = ( r n ) − ( r n − t ) , A 4 ( s ) = ( 4 4 s + 3 ) . For a t t t T ⊆ [ n ] T \subseteq[n] T ⊆ [ n ]
C T ( n ) = { E ∈ ( [ n ] 4 ) : E ∩ T ≠ ∅ } \mathcal{C}_T(n)=\left\{E\in\binom{[n]}{4}: E\cap T\ne\varnothing\right\} C T ( n ) = { E ∈ ( 4 [ n ] ) : E ∩ T = ∅ } has B 4 ( n , t ) B_4(n,t) B 4 ( n , t ) t t t C t = C [ t ] ( n ) \mathcal{C}_t=\mathcal{C}_{[t]}(n) C t = C [ t ] ( n ) 4 s + 3 4s+3 4 s + 3
Theorem 1.1 (Four-uniform matching bound). Let s ≥ 1 s\ge1 s ≥ 1 n ≥ 4 s + 4 n\ge4s+4 n ≥ 4 s + 4 F ⊆ ( [ n ] 4 ) \mathcal{F}\subseteq\binom{[n]}{4} F ⊆ ( 4 [ n ] ) ν ( F ) ≤ s \nu(\mathcal{F})\le s ν ( F ) ≤ s
∣ F ∣ ≤ M ( n , s ) : = max { A 4 ( s ) , B 4 ( n , s ) } . |\mathcal{F}|\le M(n,s):=\max\{A_4(s),B_4(n,s)\}. ∣ F ∣ ≤ M ( n , s ) := max { A 4 ( s ) , B 4 ( n , s )} . For s ≤ 4 s\le4 s ≤ 4 § 2 and the small full-carrier certificates suffice.
The clique on 4 s + 3 4s+3 4 s + 3 s s s n < 4 s + 4 n<4s+4 n < 4 s + 4 ( n 4 ) \binom{n}{4} ( 4 n ) § 5 identifies the exact extremizers in explicit cover and clique domains and gives quantitative clique stability for shifted ONE families. It does not classify every crossing case or prove arbitrary-family stability.
Contribution and antecedents. Erdős formulated the matching problem in [1 equation (9)] . Frankl [13 ] settled uniformity three; the short proof of Frankl–Rödl–Ruciński [4 ] covers matching number at least 33. Hou–Hu–Liu [12 Theorem 1.1] prove the four-uniform bound for s ≥ 6961 s \ge6961 s ≥ 6961 s s s [13 Proposition 5.1 and Corollary 5.1] .
Notation and proof route. A family is shifted if every four-set coordinatewise below one of its members also belongs to it. It has Property ONE if a maximum matching avoids its first vertex. Put
a s = n 4 ( s ) = min { n ≥ 4 s + 4 : B 4 ( n , s ) ≥ A 4 ( s ) } . a_s = n_4(s) = \min\{n \ge4s + 4 : B_4(n,s) \ge A_4(s)\}. a s = n 4 ( s ) = min { n ≥ 4 s + 4 : B 4 ( n , s ) ≥ A 4 ( s )} . For s ≥ 2 s \ge2 s ≥ 2 a s − 1 , a s a_s - 1, a_s a s − 1 , a s § 2 proves that these inputs suffice, before the finite configurations are analysed. § 3 gives the trace reduction, an ordered board and the certificates for the small and intermediate parameters. § 4 proves the necessary layer inequalities and covers the infinite tail. The division of the critical inputs is
Theorem 1.1 is a cardinality statement. Table 1 distinguishes it from the structural consequences.
Table 1. Domains of the global and structural results. The constants 71 and 143 control respectively the number of edges outside the canonical clique and the symmetric difference. The precise statements are in § 5 .
Dependence on mathematical and computational inputs. The global cardinality proof imports Frankl’s shadow inequality [3 Theorem 1.2] ; it does not import the complete three-uniform matching theorem. The necessary finite HHL statements are reconstructed with explicit searches and certificate checks. The cover-uniqueness consequence also uses [3 Theorem 1.1] at s = 4 s = 4 s = 4 n ≥ 32 n \ge32 n ≥ 32 § 9 have their additional imports listed there. Exact equality can be transferred through shifts by the two inverse lemmas in § 5 ; quantitative stability for arbitrary families is not established. § 7 compares the precise statements with earlier work, including the clique-side results of Guo–Lu. § 8 separates the global computations from the additional checks required by the appendices.
From the critical bounds to the global theorem
Write ∂ H \partial\mathcal{H} ∂ H K j ( A ) K_j(\mathcal{A}) K j ( A ) j j j A \mathcal{A} A
We use shifting, which preserves cardinality and does not increase the matching number, and the following classical quantitative input.
Shadow. Frankl [3 Theorem 1.2] gives ∣ H ∣ ≤ u ∣ ∂ H ∣ |\mathcal{H}| \leq u|\partial\mathcal{H}| ∣ H ∣ ≤ u ∣ ∂ H ∣ ν ( H ) = u \nu(\mathcal{H}) = u ν ( H ) = u ν ( H ) ≤ c \nu(\mathcal{H}) \leq c ν ( H ) ≤ c ∣ H ∣ ≤ c ∣ ∂ H ∣ |\mathcal{H}| \leq c|\partial\mathcal{H}| ∣ H ∣ ≤ c ∣ ∂ H ∣
Lemma 2.1 (Shifted completion). Let n ≥ 4 t n \geq4t n ≥ 4 t F ⊆ ( [ n ] 4 ) \mathcal{F} \subseteq\binom{[n]}{4} F ⊆ ( 4 [ n ] ) ν ( F ) ≤ t \nu(\mathcal{F}) \leq t ν ( F ) ≤ t G ⊇ F \mathcal{G} \supseteq\mathcal{F} G ⊇ F ν ( G ) = t \nu(\mathcal{G}) = t ν ( G ) = t K ≥ 0 K \geq0 K ≥ 0
∣ G ∖ C t ∣ ≤ K ( B 4 ( n , t ) − ∣ G ∣ ) |\mathcal{G} \setminus\mathcal{C}_t| \leq K\bigl(B_4(n,t)-|\mathcal{G}|\bigr) ∣ G ∖ C t ∣ ≤ K ( B 4 ( n , t ) − ∣ G ∣ ) for every shifted G \mathcal{G} G t t t F \mathcal{F} F t t t
Proof. While the matching number is below t t t t t t ⌊ n / 4 ⌋ ≥ t \lfloor n/4\rfloor\geq t ⌊ n /4 ⌋ ≥ t
∣ F ∖ C t ∣ ≤ ∣ G ∖ C t ∣ ≤ K ( B 4 ( n , t ) − ∣ G ∣ ) ≤ K ( B 4 ( n , t ) − ∣ F ∣ ) . |\mathcal{F} \setminus\mathcal{C}_t| \leq|\mathcal{G} \setminus\mathcal{C}_t| \leq K\bigl(B_4(n,t)-|\mathcal{G}|\bigr) \leq K\bigl(B_4(n,t)-|\mathcal{F}|\bigr). ∣ F ∖ C t ∣ ≤ ∣ G ∖ C t ∣ ≤ K ( B 4 ( n , t ) − ∣ G ∣ ) ≤ K ( B 4 ( n , t ) − ∣ F ∣ ) . A section bound already sufficient for the links
Lemma 2.2 (A consequence of Frankl’s section method). For r ≥ 2 r \geq2 r ≥ 2 t ≥ 1 t \geq1 t ≥ 1
D r ( t ) = ( 2 r − 1 ) t + r − ( r − 1 ) ⌈ t + 1 r ⌉ . D_r(t)=(2r-1)t+r-(r-1)\left\lceil\frac{t+1}{r}\right\rceil. D r ( t ) = ( 2 r − 1 ) t + r − ( r − 1 ) ⌈ r t + 1 ⌉ . Every r r r t t t n ≥ D r ( t ) n \geq D_r(t) n ≥ D r ( t ) B r ( n , t ) B_r(n,t) B r ( n , t ) D 4 ( 3 ) = 22 D_4(3)=22 D 4 ( 3 ) = 22 D 3 ( t ) ≤ n 4 ( t ) D_3(t) \leq n_4(t) D 3 ( t ) ≤ n 4 ( t ) t ≥ 1 t \geq1 t ≥ 1
Proof. Shift and complete to matching number exactly t t t Lemma 2.1 in uniformity r r r [ t − 1 ] [t-1] [ t − 1 ] r r r [ t + r − 1 ] [t+r-1] [ t + r − 1 ] X = [ t + 1 ] X=[t+1] X = [ t + 1 ] Y = [ n ] ∖ X Y=[n]\setminus X Y = [ n ] ∖ X q 0 = ⌊ ( t + 1 ) / r ⌋ q_0=\lfloor(t+1)/r\rfloor q 0 = ⌊( t + 1 ) / r ⌋ c = t − q 0 c=t-q_0 c = t − q 0 H \mathcal{H} H X X X c c c q 0 q_0 q 0 X X X A 1 , … , A t + 1 \mathcal{A}_1,\ldots,\mathcal{A}_{t+1} A 1 , … , A t + 1 Y Y Y ∣ H ∣ ≤ c ∣ A t + 1 ∣ |\mathcal{H}| \leq c|\mathcal{A}_{t+1}| ∣ H ∣ ≤ c ∣ A t + 1 ∣
For a matching of v = 2 t − q 0 + 1 = t + c + 1 v=2t-q_0+1=t+c+1 v = 2 t − q 0 + 1 = t + c + 1 r − 1 r-1 r − 1 Y Y Y d i d_i d i x ∈ [ 0 , t ] x\in[0,t] x ∈ [ 0 , t ] t − x t-x t − x v v v x + 1 x+1 x + 1 x x x
∑ i = 1 t d i + ( c + 1 ) d t + 1 ≤ ( t − x ) v + x 2 + ( c + 1 ) x = t v + x ( x + c + 1 − v ) ≤ t v . \sum_{i=1}^{t}d_i+(c+1)d_{t+1}\leq(t-x)v+x^2+(c+1)x=tv+x(x+c+1-v)\leq tv. i = 1 ∑ t d i + ( c + 1 ) d t + 1 ≤ ( t − x ) v + x 2 + ( c + 1 ) x = t v + x ( x + c + 1 − v ) ≤ t v . Such a matching exists because n ≥ D r ( t ) n\geq D_r(t) n ≥ D r ( t ) ∣ Y ∣ ≥ ( r − 1 ) v |Y|\geq(r-1)v ∣ Y ∣ ≥ ( r − 1 ) v
∣ H ∣ + ∑ i = 1 t + 1 ∣ A i ∣ ≤ t ( ∣ Y ∣ r − 1 ) . |\mathcal{H}|+\sum_{i=1}^{t+1}|\mathcal{A}_i|\leq t\binom{|Y|}{r-1}. ∣ H ∣ + i = 1 ∑ t + 1 ∣ A i ∣ ≤ t ( r − 1 ∣ Y ∣ ) . Every section using at least two vertices of X X X [ t ] [t] [ t ] [3 Sections 3–5] .
For the last assertion, write t = 3 a + b t=3a+b t = 3 a + b b = 0 , 1 , 2 b=0,1,2 b = 0 , 1 , 2 D 3 ( t ) = 13 a + 3 , 13 a + 8 , 13 a + 11 D_3(t)=13a+3,13a+8,13a+11 D 3 ( t ) = 13 a + 3 , 13 a + 8 , 13 a + 11 a a a
Table 4.
The polynomial is 24 [ A 4 ( t ) − B 4 ( D 3 ( t ) − 1 , t ) ] 24[A_4(t)-B_4(D_3(t)-1,t)] 24 [ A 4 ( t ) − B 4 ( D 3 ( t ) − 1 , t )] B 4 ( n , t ) B_4(n,t) B 4 ( n , t ) n n n D 3 ( t ) ≤ n 4 ( t ) D_3(t)\le n_4(t) D 3 ( t ) ≤ n 4 ( t )
This consequence supplies every triple link in the global proof. The complete three-uniform EMC is not an additional premise.
The critical statement that remains to be checked
For every s ≥ 2 s\ge2 s ≥ 2
∣ F ∣ ≤ M ( n , s ) at n ∈ { a s − 1 , a s } , F shifted and ONE , ν ( F ) = s . (1) |\mathcal{F}| \le M(n,s) \text{ at } n\in\{a_s-1,a_s\},\qquad\mathcal{F}\text{ shifted and ONE},\quad\nu(\mathcal{F})=s. \tag*{(1)} ∣ F ∣ ≤ M ( n , s ) at n ∈ { a s − 1 , a s } , F shifted and ONE , ν ( F ) = s . (1) It is enough to check saturated families: enlargement under ν ≤ s \nu\le s ν ≤ s § 3.1 . The partition argument below and Proposition 3.6 treat s = 2 , 3 , 4 s=2,3,4 s = 2 , 3 , 4 § 3 supplies the retained finite records; Corollary 4.29 supplies the propagated critical inputs. Proposition 4.1 also gives the stronger ONE-clique bound for all s ≥ 73 s\ge73 s ≥ 73
Crossings, deletion and propagation
First note that for s ≥ 2 s\ge2 s ≥ 2
24 [ A 4 ( s ) − B 4 ( 4 s + 4 , s ) ] = s ( s − 1 ) ( 81 s 2 + 95 s + 26 ) > 0. (2) 24[A_4(s)-B_4(4s+4,s)]=s(s-1)(81s^2+95s+26)>0. \tag*{(2)} 24 [ A 4 ( s ) − B 4 ( 4 s + 4 , s )] = s ( s − 1 ) ( 81 s 2 + 95 s + 26 ) > 0. (2) Thus a s − 1 ≥ 4 s + 4 a_s-1\ge4s+4 a s − 1 ≥ 4 s + 4 a t ≤ 5 t + 4 a_t\le5t+4 a t ≤ 5 t + 4
24 [ B 4 ( 5 t + 4 , t ) − A 4 ( t ) ] = 113 t 4 + 226 t 3 + 139 t 2 + 26 t > 0 ( t ≥ 1 ) . (3) 24[B_4(5t+4,t)-A_4(t)]=113t^4+226t^3+139t^2+26t>0\qquad(t\ge1). \tag*{(3)} 24 [ B 4 ( 5 t + 4 , t ) − A 4 ( t )] = 113 t 4 + 226 t 3 + 139 t 2 + 26 t > 0 ( t ≥ 1 ) . (3) The following inequality is the four-uniform specialization of [13 Proposition 5.1, equation (5.1)] . We retain the elementary proof because its strict clique branch is used in the equality argument.
Lemma 2.3 (Direct deletion). For s ≥ 2 s\ge2 s ≥ 2 n ≥ 4 s + 4 n\ge4s+4 n ≥ 4 s + 4
M ( n − 1 , s − 1 ) + ( n − 1 3 ) ≤ M ( n , s ) . M(n-1,s-1)+\binom{n-1}{3}\le M(n,s). M ( n − 1 , s − 1 ) + ( 3 n − 1 ) ≤ M ( n , s ) . Proof. If the preceding maximum is the cover, Pascal’s identity gives B 4 ( n − 1 , s − 1 ) + ( n − 1 3 ) = B 4 ( n , s ) B_4(n-1,s-1)+\binom{n-1}{3}=B_4(n,s) B 4 ( n − 1 , s − 1 ) + ( 3 n − 1 ) = B 4 ( n , s ) B 4 ( n − 1 , s − 1 ) < A 4 ( s − 1 ) B_4(n-1,s-1)<A_4(s-1) B 4 ( n − 1 , s − 1 ) < A 4 ( s − 1 ) n − 1 < a s − 1 ≤ 5 s − 1 n-1<a_{s-1}\le5s-1 n − 1 < a s − 1 ≤ 5 s − 1 n − 1 ≤ 5 s − 2 n-1\le5s-2 n − 1 ≤ 5 s − 2 u = s − 2 ≥ 0 u=s-2\ge0 u = s − 2 ≥ 0
24 [ A 4 ( s ) − A 4 ( s − 1 ) − ( 5 s − 2 3 ) ] = 5736 + 8056 u + 3660 u 2 + 524 u 3 > 0. 24\left[A_4(s)-A_4(s-1)-\binom{5s-2}{3}\right]=5736+8056u+3660u^2+524u^3>0. 24 [ A 4 ( s ) − A 4 ( s − 1 ) − ( 3 5 s − 2 ) ] = 5736 + 8056 u + 3660 u 2 + 524 u 3 > 0. Monotonicity of the binomial coefficient proves the remaining case. A tie in the preceding maximum belongs to the cover case.
Lemma 2.4 (Propagation using the classical link range). If the cover bound holds for all families at ( n , t ) = ( a , t ) (n,t)=(a,t) ( n , t ) = ( a , t ) a ≥ n 4 ( t ) a\ge n_4(t) a ≥ n 4 ( t ) n ≥ a n\ge a n ≥ a
Proof. For the step from n n n n + 1 n+1 n + 1 t t t t + 1 t+1 t + 1 t + 1 t+1 t + 1 n ≥ a ≥ 4 t + 4 n\ge a\ge4t+4 n ≥ a ≥ 4 t + 4 Lemma 2.2 , since n ≥ n 4 ( t ) ≥ D 3 ( t ) n\ge n_4(t)\ge D_3(t) n ≥ n 4 ( t ) ≥ D 3 ( t ) B 3 ( n , t ) B_3(n,t) B 3 ( n , t ) n n n B 4 ( n , t ) + B 3 ( n , t ) = B 4 ( n + 1 , t ) B_4(n,t)+B_3(n,t)=B_4(n+1,t) B 4 ( n , t ) + B 3 ( n , t ) = B 4 ( n + 1 , t )
Proof of Theorem 1.1. Induct on s s s n = 4 ( s + 1 ) n=4(s+1) n = 4 ( s + 1 ) s + 1 s+1 s + 1 s s s
∣ F ∣ ≤ s s + 1 ( 4 s + 4 4 ) = ( 4 s + 3 4 ) . |\mathcal{F}| \le\frac{s}{s+1}\binom{4s+4}{4}=\binom{4s+3}{4}. ∣ F ∣ ≤ s + 1 s ( 4 4 s + 4 ) = ( 4 4 s + 3 ) . For s = 1 s=1 s = 1 a 1 = 8 a_1=8 a 1 = 8 Lemma 2.4 propagates it to every n ≥ 8 n\ge8 n ≥ 8
Let s ≥ 2 s\ge2 s ≥ 2 s − 1 s-1 s − 1 n = a s − 1 , a s n=a_s-1,a_s n = a s − 1 , a s s s s 1 1 1 1 1 1 n − 1 ≥ 4 ( s − 1 ) + 4 n-1\ge4(s-1)+4 n − 1 ≥ 4 ( s − 1 ) + 4 ( n − 1 3 ) \binom{n-1}{3} ( 3 n − 1 ) Lemma 2.3 prove the target.
If ONE holds, use the following exhaustive list of critical inputs. For s = 2 , 3 s=2,3 s = 2 , 3 ( 2 , 12 ) , ( 3 , 16 ) (2,12),(3,16) ( 2 , 12 ) , ( 3 , 16 ) Proposition 3.6 . For s = 4 s=4 s = 4 s ≥ 5 s\ge5 s ≥ 5 § 3 selected in Corollary 4.29, the two fixed inequalities of Lemma 4.25 , and the propagation proved there. This covers every critical input. Proposition 4.1 also gives the stronger ONE-clique bound for s ≥ 73 s\ge73 s ≥ 73
Adding isolated vertices to a s − 1 a_s-1 a s − 1 n n n Lemma 2.4 propagates the upper cover bound to every larger n n n s ≤ 4 s\le4 s ≤ 4 Lemma 2.2 have been used. □
Trace reduction and critical certificates
We verify the critical input (1) for the finite range. Exact traces turn a global family into finite configurations; the ordered board retains comparisons that would be lost by a larger symmetry quotient. The necessary layer inequalities are proved in § 4 . The four small points are checked directly on the full carrier without those layer inequalities.
Full-carrier traces and elementary completion
Shifting preserves size and does not increase matching number. A shifted family can be enlarged to a shifted family maximal under v ≤ s v\le s v ≤ s n ≥ 4 s + 4 n\ge4s+4 n ≥ 4 s + 4 s s s 1 1 1
Lemma 3.1 (Exact traces on the full carrier). *Let F \mathcal{F} F v ≤ s v\le s v ≤ s ν ( F ) = s \nu(\mathcal{F})=s ν ( F ) = s n ≥ 4 s + 4 n\ge4s+4 n ≥ 4 s + 4 K = [ 4 s + 3 ] K=[4s+3] K = [ 4 s + 3 ] q = n − 4 s − 3 q=n-4s-3 q = n − 4 s − 3 s s s K K K 1 1 1 D = { 1 , δ 1 , δ 2 } D=\{1,\delta_1,\delta_2\} D = { 1 , δ 1 , δ 2 } δ 1 < δ 2 \delta_1<\delta_2 δ 1 < δ 2 1 1 1 G = { E ∩ K : E ∈ F } \mathcal{G}=\{E\cap K:E\in\mathcal{F}\} G = { E ∩ K : E ∈ F }
every trace has size 2, 3 or 4; no small trace lies inside D D D
ν ( G ) = s \nu(\mathcal{G})=s ν ( G ) = s
every four-set containing a trace of G \mathcal{G} G F \mathcal{F} F
∣ F ∣ = ∑ H ∈ G ( q 4 − ∣ H ∣ ) |\mathcal{F}|=\sum_{H\in\mathcal{G}}\binom{q}{4-|H|} ∣ F ∣ = ∑ H ∈ G ( 4 − ∣ H ∣ q )
Proof. A matching avoiding a set R R R [ n ] ∖ R [n]\setminus R [ n ] ∖ R R = { 1 } R=\{1\} R = { 1 }
An empty trace, or a small trace in D D D 1 1 1
If s + 1 s+1 s + 1 s + 1 s+1 s + 1 u ∉ K u\notin K u ∈ / K ν ( F ) = s \nu(\mathcal{F})=s ν ( F ) = s v ∈ K v\in K v ∈ K 4 s + 3 4s+3 4 s + 3 K K K 4 ( s + 1 ) 4(s+1) 4 ( s + 1 ) K K K u u u v v v v < u v<u v < u u u u s s s G \mathcal{G} G
If a four-set Q Q Q H H H s s s Q Q Q H H H s + 1 s+1 s + 1 4 − ∣ H ∣ 4-|H| 4 − ∣ H ∣ H H H
Internal enlargements of a trace to size j ′ ≤ 4 j'\leq4 j ′ ≤ 4 q ≥ 4 − j ′ q\geq4-j' q ≥ 4 − j ′ [12 Section 2] ; those mechanisms remain attributed even though their proofs are included here. No four-column denominator is used on the full carrier.
The complete weighted board
For a saturated shifted ONE family, the selected matching consists of s s s [ 4 s + 3 ] [4s+3] [ 4 s + 3 ] 1 1 1 D D D τ \tau τ H H H j ∈ { 2 , 3 , 4 } j\in\{2,3,4\} j ∈ { 2 , 3 , 4 } z z z
w s , n ( H ) = ( q 4 − j ) ( s − z 4 − z ) , q = n − 4 s − 3. w_{s,n}(H)=\frac{\binom{q}{4-j}}{\binom{s-z}{4-z}},\qquad q=n-4s-3. w s , n ( H ) = ( 4 − z s − z ) ( 4 − j q ) , q = n − 4 s − 3. There are exactly ( s − z 4 − z ) \binom{s-z}{4-z} ( 4 − z s − z )
∣ F ∣ − A 4 ( s ) = ∑ τ Φ s , n ( τ ) , Φ s , n = ∑ ∣ H ∣ = 2 , 3 H p r e s e n t w s , n ( H ) − ∑ ∣ H ∣ = 4 H m i s s i n g w s , n ( H ) . (4) |\mathcal{F}|-A_4(s)=\sum_{\tau}\Phi_{s,n}(\tau),\qquad
\Phi_{s,n}=\sum_{\substack{|H|=2,3\\H\ \mathrm{present}}}w_{s,n}(H)-\sum_{\substack{|H|=4\\H\ \mathrm{missing}}}w_{s,n}(H). \tag*{(4)} ∣ F ∣ − A 4 ( s ) = τ ∑ Φ s , n ( τ ) , Φ s , n = ∣ H ∣ = 2 , 3 H present ∑ w s , n ( H ) − ∣ H ∣ = 4 H missing ∑ w s , n ( H ) . (4) All quadruple layers are retained, including spread one.
For example, a present pair H = { x a 0 , x b 1 } H=\{x_{a0},x_{b1}\} H = { x a 0 , x b 1 } q ≥ 2 q\geq2 q ≥ 2 ( q 2 ) \binom{q}{2} ( 2 q ) ( s − 2 4 − 2 ) \binom{s-2}{4-2} ( 4 − 2 s − 2 ) ( q 2 ) / ( s − 2 4 − 2 ) \binom{q}{2}/\binom{s-2}{4-2} ( 2 q ) / ( 4 − 2 s − 2 ) Figure 1 displays the local order without imposing global symmetry.
Figure 1. A 19-vertex board: four matching edges and the three residual vertices. Each column is ordered from level 0 to level 3; 1 < δ 1 < δ 2 1 < \delta_1 < \delta_2 1 < δ 1 < δ 2 q q q [ 4 s + 3 ] [4s+3] [ 4 s + 3 ]
The 5016 labelled subsets of sizes 2, 3 and 4 form 291 orbits under column permutations and residual permutations. Average the presence indicator over this group. Its orbit coordinates x i x_i x i [ 0 , 1 ] [0,1] [ 0 , 1 ] D D D
The inequalities used by the certificate are all necessary:
lowering inside a column preserves presence;
a present trace forces a containing trace of the next size; for sizes 2 to 3, use q ≥ 1 q \ge1 q ≥ 1
five pairwise disjoint present traces are impossible, giving ∑ ℓ = 1 5 x H ℓ ≤ 4 \sum_{\ell=1}^{5} x_{H_\ell} \le4 ∑ ℓ = 1 5 x H ℓ ≤ 4
with T z T_z T z P z P_z P z M z M_z M z z z z § 4 proves
18 35 T 3 + 18 71 P 2 ≤ M 4 , 9 8 T 2 + 27 32 P 1 ≤ M 3 , 2 T 1 + 2 P 0 ≤ M 2 ; \frac{18}{35}T_3+\frac{18}{71}P_2 \le M_4,\qquad\frac{9}{8}T_2+\frac{27}{32}P_1 \le M_3,\qquad2T_1+2P_0 \le M_2; 35 18 T 3 + 71 18 P 2 ≤ M 4 , 8 9 T 2 + 32 27 P 1 ≤ M 3 , 2 T 1 + 2 P 0 ≤ M 2 ; the full finite support profiles give additional linear inequalities, as specified next.
A triple support is a down-set of { 0 , 1 , 2 , 3 } 3 \{0,1,2,3\}^3 { 0 , 1 , 2 , 3 } 3 h h h p p p β ( h ) = max p h ⋅ p \beta(h)=\max_p h\cdot p β ( h ) = max p h ⋅ p h ⋅ p ≤ β ( h ) h\cdot p\le\beta(h) h ⋅ p ≤ β ( h ) h h h
For three further points, keep D = { 1 , δ 1 , δ 2 } D=\{1,\delta_1,\delta_2\} D = { 1 , δ 1 , δ 2 } δ 1 < δ 2 \delta_1<\delta_2 δ 1 < δ 2 δ 2 \delta_2 δ 2 δ 1 \delta_1 δ 1 δ 1 \delta_1 δ 1
Local order and traces forced by the minimal residual
We refine the ordered-residual model while keeping the same authentic board. Write D = { 1 , δ 1 , δ 2 } D = \{1,\delta_1,\delta_2\} D = { 1 , δ 1 , δ 2 } δ 1 < δ 2 \delta_1 < \delta_2 δ 1 < δ 2 ( δ 1 , δ 2 ) (\delta_1,\delta_2) ( δ 1 , δ 2 ) c c c 4 c , … , 4 c + 3 4c,\ldots,4c+3 4 c , … , 4 c + 3 16 , 17 , 18 16,17,18 16 , 17 , 18 1 , δ 1 , δ 2 1,\delta_1,\delta_2 1 , δ 1 , δ 2
Lemma 3.2 (Exhaustive order prefixes). Restrict the global order to a carrier with b b b 0 , 1 , … 0,1,\ldots 0 , 1 , … p p p k k k k k k k < b k < b k < b p p p
Proof. Each residual or column is an increasing chain. The next vertex of any interleaving must be the unused head of one of these chains. Unseen columns differ only by names; naming the chosen one k k k
For a four-column board the root is p = ( 16 ) p=(16) p = ( 16 ) ( 16 , 17 ) (16,17) ( 16 , 17 ) ( 16 , 0 ) (16,0) ( 16 , 0 ) 2 2 2 a < b a < b a < b
1 H ≤ 1 ( H ∖ { b } ) ∪ { a } ( b ∈ H , a ∉ H ) . \mathbf{1}_{H} \le\mathbf{1}_{(H\setminus\{b\})\cup\{a\}} \qquad(b \in H,\ a \notin H). 1 H ≤ 1 ( H ∖ { b }) ∪ { a } ( b ∈ H , a ∈ / H ) . Indeed replacing b b b a a a H H H [ 4 s + 3 ] [4s+3] [ 4 s + 3 ]
Only the group S 4 − k S_{4-k} S 4 − k k = 0 , 1 , 2 , 3 , 4 k=0,1,2,3,4 k = 0 , 1 , 2 , 3 , 4
469 , 1289 , 2920 , 5016 , 5016. 469,\qquad1289,\qquad2920,\qquad5016,\qquad5016. 469 , 1289 , 2920 , 5016 , 5016. They always represent the same 5016 labelled subsets. Every transported row is a necessary inequality before it is averaged; the original family is not assumed symmetric.
Lemma 3.3 (Lexicographically forced traces). Let K = [ 4 s + 3 ] K=[4s+3] K = [ 4 s + 3 ] q = n − 4 s − 3 q=n-4s-3 q = n − 4 s − 3 x , y ∈ K ∖ { 1 } x,y\in K\setminus\{1\} x , y ∈ K ∖ { 1 } { x , y } \{x,y\} { x , y } ( δ 1 , δ 2 ) (\delta_1,\delta_2) ( δ 1 , δ 2 ) q ≥ 1 q\ge1 q ≥ 1 { 1 , x , y } \{1,x,y\} { 1 , x , y } x ∈ K ∖ { 1 } x\in K\setminus\{1\} x ∈ K ∖ { 1 } x < δ 1 x<\delta_1 x < δ 1 q ≥ 2 q\ge2 q ≥ 2 { 1 , x } \{1,x\} { 1 , x }
Proof. If the triple trace is absent, choose u ∉ K u\notin K u ∈ / K Q = { 1 , x , y , u } Q=\{1,x,y,u\} Q = { 1 , x , y , u } s s s Q Q Q R = { 1 , x , y } R=\{1,x,y\} R = { 1 , x , y } 4 s 4s 4 s R R R ∣ K ∖ R ∣ = 4 s |K\setminus R|=4s ∣ K ∖ R ∣ = 4 s R R R
For the pair choose distinct u , v ∉ K u,v\notin K u , v ∈ / K q ≥ 2 q\ge2 q ≥ 2 Q = { 1 , x , u , v } Q=\{1,x,u,v\} Q = { 1 , x , u , v } s s s Q Q Q K ∖ { 1 , x } K\setminus\{1,x\} K ∖ { 1 , x } 4 s + 1 4s+1 4 s + 1 y y y { 1 , x , y } \{1,x,y\} { 1 , x , y } x < δ 1 x<\delta_1 x < δ 1
The low seeds. For a column E = { a < b < c < d } E=\{a<b<c<d\} E = { a < b < c < d } D ∪ { a } D\cup\{a\} D ∪ { a } D ∪ { b } D\cup\{b\} D ∪ { b } b > δ 2 b>\delta_2 b > δ 2 D ∪ { b } D\cup\{b\} D ∪ { b } E E E b < δ 2 b<\delta_2 b < δ 2 { δ 1 , b } \{\delta_1,b\} { δ 1 , b } ( δ 1 , δ 2 ) (\delta_1,\delta_2) ( δ 1 , δ 2 ) Lemma 3.3 , with q ≥ 1 q\geq1 q ≥ 1 b b b a a a s ≥ 1 s\geq1 s ≥ 1
This is the saturation/compression mechanism of [12 Lemma 2.5 and Section 4, especially Lemma 4.1] , applied with the additional comparisons displayed above. For partial orders, a triple is forced only when a guaranteed comparison shows x < δ 1 x<\delta_1 x < δ 1 y < δ 1 y<\delta_1 y < δ 1 δ 1 \delta_1 δ 1 δ 2 \delta_2 δ 2 − x H ≤ − 1 -x_H\leq-1 − x H ≤ − 1 S 4 − k S_{4-k} S 4 − k q = 1 q=1 q = 1
The preceding support-profile inequalities also remain available. In this refinement each is applied to its specified two- or three-column support before averaging over the stabilizer. Its right side is still the exact maximum over all legal profiles, including for signed functionals. The support census is inherited; the refinement couples it to the local order and the forced presences.
Dual arithmetic and global integer rounding
For necessary rows A x ≤ b Ax\leq b A x ≤ b l i ≤ x i ≤ u i l_i\leq x_i\leq u_i l i ≤ x i ≤ u i Φ = c ⋅ x − c 0 \Phi=c\cdot x-c_0 Φ = c ⋅ x − c 0 y ≥ 0 y\geq0 y ≥ 0
Φ ≤ y ⋅ b + ∑ i max { ( c − A T y ) i l i , ( c − A T y ) i u i } − c 0 = : U . (5) \Phi\leq y\cdot b+\sum_i\max\{(c-A^{\mathsf T}y)_il_i,(c-A^{\mathsf T}y)_iu_i\}-c_0=:U. \tag*{(5)} Φ ≤ y ⋅ b + i ∑ max {( c − A T y ) i l i , ( c − A T y ) i u i } − c 0 =: U . (5) Indeed sum y y y
There are ( s 4 ) \binom{s}{4} ( 4 s ) Δ ∗ = max { 0 , B 4 ( n , s ) − A 4 ( s ) } \Delta_*=\max\{0,B_4(n,s)-A_4(s)\} Δ ∗ = max { 0 , B 4 ( n , s ) − A 4 ( s )}
( s 4 ) U < Δ ∗ + 1. (6) \binom{s}{4}U<\Delta_*+1. \tag*{(6)} ( 4 s ) U < Δ ∗ + 1. (6) By (3.1), ∣ F ∣ − A 4 ( s ) |\mathcal{F}|-A_4(s) ∣ F ∣ − A 4 ( s ) Δ ∗ \Delta_* Δ ∗ U U U Lemma 3.2 makes this a bound for every board. This rounds the global cardinality, not each board or each orbit mean separately; the means remain real variables.
Table 1 (PDF p. 9).
All 88 distributed endpoint bounds satisfy (6) . The main cardinality proof uses the 51 records selected in Corollary 4.29, together with its two fixed inequalities. The other 37 ordinary upper records are retained for the structural gap bounds. The 48 lower records at s ≥ 25 s\geq25 s ≥ 25 ( 22 , 103 ) (22,103) ( 22 , 103 ) ( 27 , 125 ) (27,125) ( 27 , 125 ) ( 34 , 156 ) (34,156) ( 34 , 156 )
717402531195218849 20000000000000 , 115229982289222811 20000000000000 , 740832624886150683 625000000000000 . \frac{717402531195218849}{20000000000000},\qquad
\frac{115229982289222811}{20000000000000},\qquad
\frac{740832624886150683}{625000000000000}. 20000000000000 717402531195218849 , 20000000000000 115229982289222811 , 625000000000000 740832624886150683 . The archive records each row with its literal witness and each bound with its multipliers; the checker recomputes the coefficients and signs.
The larger target at an upper crossing is essential. For s = 6 , n = 31 s = 6, n = 31 s = 6 , n = 31 s = 8 , n = 40 s = 8, n = 40 s = 8 , n = 40 [ 2 s + 1 ] [2s + 1] [ 2 s + 1 ] A 4 ( s ) = 17550 , 52360 A_4(s) = 17550, 52360 A 4 ( s ) = 17550 , 52360 B 4 ( n , s ) = 18815 , 55430 B_4(n,s) = 18815, 55430 B 4 ( n , s ) = 18815 , 55430 s s s s s s 2 s 2s 2 s 2 s 2s 2 s
The 33 order trees and strict ONE separation
Proposition 3.4 (The remaining finite endpoints). Under the declared board premises, the following 33 points satisfy ∣ F ∣ ≤ max { A 4 ( s ) , B 4 ( n , s ) } |\mathcal{F}| \le\max\{A_4(s), B_4(n,s)\} ∣ F ∣ ≤ max { A 4 ( s ) , B 4 ( n , s )} for every shifted saturated ONE family with matching number s s s
n = n 4 ( s ) − 1 s = 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 , 22 , 24 , n = n 4 ( s ) s = 5 , … , 21 , 23 , 25 , 26 , 28 , 30 , 32. \begin{aligned}
n &= n_4(s) - 1 && s = 6,8,10,12,14,16,18,20,22,24,\\
n &= n_4(s) && s = 5,\ldots,21,23,25,26,28,30,32.
\end{aligned} n n = n 4 ( s ) − 1 = n 4 ( s ) s = 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 , 22 , 24 , s = 5 , … , 21 , 23 , 25 , 26 , 28 , 30 , 32. Proof using the exact finite records. For each point the original archive supplies one tree. The complete forest has 413 nodes: 115 splits, 295 rational dual leaves and three analytic leaves; the maximum prefix length is 7. Every split keeps exactly the children in Lemma 3.2 . At a dual leaf the checker reconstructs its stabilizer, all necessary rows and the rational bound (5) , including every residual coefficient. The global bound satisfies (6) .
An analytic leaf has precisely the prefix (16, 17, 18). Any present pair or triple would shift into D D D Φ ≤ 0 \Phi\le0 Φ ≤ 0
All 711130 row and multiplier occurrences are accounted for: 69937 completions, 391523 order rows, 237183 matching rows, 6321 support rows, 638 pair forcings, 5243 triple forcings and 285 wide inequalities. The ordered-tree leaves use no middle or lower inequalities. The distributed checker reconstructs every leaf and computes its exact bound. The exhaustive maximum and (3.1) then prove the stated integer target. Section 8 identifies the original records and executable checks.
There is a separate arithmetic check of order coverage. If r r r r i r_i r i i i i p p p k k k
N ( p ) = ( 19 − ∣ p ∣ ) ! r ! ∏ i = 0 3 r i ! ( 4 − k ) ! (7) \mathcal{N}(p) = \frac{(19-|p|)!}{r!\prod_{i=0}^{3}r_i!(4-k)!} \tag*{(7)} N ( p ) = r ! ∏ i = 0 3 r i ! ( 4 − k )! ( 19 − ∣ p ∣ )! (7) Interleave the remaining labelled chains and divide by the free renaming action on unseen columns. At the root this is 18 ! / [ 2 ! ( 4 ! ) 5 ] = 402026625 18!/[2!(4!)^5] = 402026625 18 ! / [ 2 ! ( 4 ! ) 5 ] = 402026625
Corollary 3.5 (Strict ONE gaps at the new upper points). At each upper point in Proposition 3.4 , let
g s , n = ( s 4 ) max l e a v e s U , h s , n = B 4 ( n , s ) − A 4 ( s ) − ⌊ g s , n ⌋ . g_{s,n} = \binom{s}{4}\max_{\mathrm{leaves}} U,\qquad h_{s,n} = B_4(n,s)-A_4(s)-\lfloor g_{s,n}\rfloor. g s , n = ( 4 s ) leaves max U , h s , n = B 4 ( n , s ) − A 4 ( s ) − ⌊ g s , n ⌋ . Under the same premises, every shifted ONE family of matching number exactly s s s has size at
most B 4 ( n , s ) − h s , n B_4(n,s)-h_{s,n} B 4 ( n , s ) − h s , n h s , n h_{s,n} h s , n
In particular a shifted family attaining B 4 ( n , s ) B_4(n,s) B 4 ( n , s )
Proof. Enlarge the shifted ONE family to a saturated shifted family of the same matching number by the enlargement in § 3.1 . Its matching avoiding 1 persists. The forest bounds its cardinality by A 4 ( s ) + ⌊ g s , n ⌋ A_4(s)+\lfloor g_{s,n}\rfloor A 4 ( s ) + ⌊ g s , n ⌋ □ \square □
For example, at ( s , n ) = ( 5 , 26 ) (s,n)=(5,26) ( s , n ) = ( 5 , 26 )
g 5 , 26 = 65774380902950387 600000000000000 < 110 , A 4 ( 5 ) = 8855 , B 4 ( 26 , 5 ) = 8965 , g_{5,26}=\frac{65774380902950387}{600000000000000}<110,\qquad A_4(5)=8855,\qquad B_4(26,5)=8965, g 5 , 26 = 600000000000000 65774380902950387 < 110 , A 4 ( 5 ) = 8855 , B 4 ( 26 , 5 ) = 8965 , and the positive rounding margin is
111 − g 5 , 26 = 825619097049613 600000000000000 . 111-g_{5,26}=\frac{825619097049613}{600000000000000}. 111 − g 5 , 26 = 600000000000000 825619097049613 . Consequently ONE families have at most 8964 edges there. At s = 28 , 30 , 32 s=28,30,32 s = 28 , 30 , 32 A 4 ( s ) A_4(s) A 4 ( s )
The four small points on the full carrier
For s = 2 , 3 , 4 s=2,3,4 s = 2 , 3 , 4 K = [ 4 s + 3 ] K=[4s+3] K = [ 4 s + 3 ] s s s D D D q = 2 , 2 , 2 , 3 q=2,2,2,3 q = 2 , 2 , 2 , 3 ( 1 , 2 , 1 ) (1,2,1) ( 1 , 2 , 1 ) ( 3 , 3 , 1 ) (3,3,1) ( 3 , 3 , 1 ) s + 1 s+1 s + 1
Proposition 3.6 (Full-carrier small certificates). For shifted ONE families with matching exactly s s s U s , n U_{s,n} U s , n ⌊ U s , n ⌋ \lfloor U_{s,n}\rfloor ⌊ U s , n ⌋
No finite HHL inequality or support classification is an input.
Proof. Enlarge while preserving ONE as in § 3.1 . Lemmas 3.1 , 3.2 and 3.3 give all required semantics. In the records the residual labels 4 s 4s 4 s 4 s + 1 4s+1 4 s + 1 4 s + 2 4s+2 4 s + 2 1 1 1 δ 1 \delta_1 δ 1 δ 2 \delta_2 δ 2 k k k S s − k S_{s-k} S s − k [ 0 , 1 ] [0,1] [ 0 , 1 ] D D D ( s + 1 ) (s+1) ( s + 1 )
For a leaf, put c H = ( 4 4 − ∣ H ∣ ) c_H=\binom{4}{4-|H|} c H = ( 4 − ∣ H ∣ 4 ) A x ≤ b Ax\le b A x ≤ b ℓ ≤ x ≤ u \ell\le x\le u ℓ ≤ x ≤ u y y y
∣ F ∣ ≤ y ⋅ b + ∑ i max { ( c − A T y ) i ℓ i , ( c − A T y ) i u i } . |\mathcal{F}| \le y\cdot b+\sum_i\max\{(c-A^{\mathsf T}y)_i\ell_i,(c-A^{\mathsf T}y)_iu_i\}. ∣ F ∣ ≤ y ⋅ b + i ∑ max {( c − A T y ) i ℓ i , ( c − A T y ) i u i } . This is the complete cardinality, not a local excess multiplied by ( s 4 ) \binom{s}{4} ( 4 s )
The four trees have 129 nodes: 34 splits, 94 dual leaves and one analytic leaf, with 213845 selected row/multiplier occurrences. The per-point dual counts are 4, 35, 4, 51. A leaf beginning with all three residual vertices has no small trace, since any such trace would shift into D D D A 4 ( s ) A_4(s) A 4 ( s ) Lemma 3.2 . With r , r i r,r_i r , r i
( 4 s + 3 − ∣ p ∣ ) ! r ! ∏ i = 0 s − 1 r i ! ( s − k ) ! . \frac{(4s+3-|p|)!}{r!\prod_{i=0}^{s-1}r_i!(s-k)!}. r ! ∏ i = 0 s − 1 r i ! ( s − k )! ( 4 s + 3 − ∣ p ∣ )! . At the four roots these counts are 1575, 525525, 402026625, 402026625. They add at every split. The maximum over all leaves gives the four displayed U s , n < M ( n , s ) + 1 U_{s,n}<M(n,s)+1 U s , n < M ( n , s ) + 1 § 8 . □
At ( 2 , 13 ) (2,13) ( 2 , 13 )
Finite board inequalities and the weight tail
This section gives critical ONE bounds for the global induction. It reconstructs the finite ingredients of Hou–Hu–Liu (HHL) [12 ] that the present certificates actually use. These are not inputs to the local stability theorems. An actual selected board consists of four columns of a selected maximum matching and the lexicographically minimal residual three-set. Lemmas 3.1 and 3.3 prove the trace, completion and seed constructions used here. The next two lemmas prove the support and upper-cube statements, C1, and only the seven trace thresholds needed from C2. The top-star row families are justified explicitly below. The residual-row mechanism of HHL Section 6.1 follows from disjoint traces and present columns or seeds. The old numerical 15- and 11-vertex bounds, the old numerical top-star bound and C3 are not imported. This assembly uses neither HHL Lemma 3.1 nor its generic localization theorem or deletion-chain criterion.
Proposition 4.1 (Critical ONE bounds from 73). Let s ≥ 73 s\ge73 s ≥ 73 n ∈ { a s − 1 , a s } n\in\{a_s-1,a_s\} n ∈ { a s − 1 , a s } shifted saturated ONE family F ⊆ ( [ n ] 4 ) \mathcal{F}\subseteq\binom{[n]}{4} F ⊆ ( 4 [ n ] ) ν ( F ) = s \nu(\mathcal{F})=s ν ( F ) = s
∣ F ∣ ≤ A 4 ( s ) . |\mathcal{F}|\le A_4(s). ∣ F ∣ ≤ A 4 ( s ) . Its proof uses the layer inequalities and the elementary weight bounds at the end of this section; it makes no assertion about non-ONE families before the induction in § 2.3 .
Support costs and rectangle persistence
An actual 19-vertex board consists of a residual three-set D D D 0 , 1 , 2 , 3 0,1,2,3 0 , 1 , 2 , 3 Q = { 0 , 1 , 2 , 3 } 4 Q=\{0,1,2,3\}^{4} Q = { 0 , 1 , 2 , 3 } 4 M ⊆ Q \mathcal{M}\subseteq Q M ⊆ Q M = ∣ M ∣ M=|\mathcal{M}| M = ∣ M ∣ T , P T,P T , P M \mathcal{M} M D ∪ { ( j , ℓ ) } D\cup\{(j,\ell)\} D ∪ {( j , ℓ )} ℓ ∈ { 0 , 1 } \ell\in\{0,1\} ℓ ∈ { 0 , 1 } seed clause that must meet M \mathcal{M} M
Call { 1 , 2 , 3 } 4 \{1,2,3\}^{4} { 1 , 2 , 3 } 4 { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } ( 3 , 1 , 1 , 1 ) (3,1,1,1) ( 3 , 1 , 1 , 1 ) { 2 , 3 } \{2,3\} { 2 , 3 }
Lemma 4.2 (Support obstructions and the upper cube). On an actual selected board a pair support has at most four traces and a triple support at most 32. The pair down-set avoids any two disjoint values whose levels in some coordinate are not exactly { 0 , 1 } \{0,1\} { 0 , 1 }
Proof. A forbidden pair configuration leaves a low level unused in one support column. Add its low seed and the two outside full columns. A forbidden triple configuration similarly admits a disjoint low seed and the outside full column. Either construction gives five disjoint traces, contradicting Lemma 3.1. This proves the support obstructions on the actual board.
For pairs, if a down-set contains a value at least 2 in one coordinate, it contains ( 2 , 0 ) (2,0) ( 2 , 0 ) ( 0 , 1 ) (0,1) ( 0 , 1 ) { 0 , 1 } 2 \{0,1\}^{2} { 0 , 1 } 2
For triples Lemma 4.4 below gives the bound 32 by complementary binary blocks. This value and its equality diagrams are due to [12 Lemma 5.2] . The support census is still used to check signed facets and the size-24 cost; the scalar cap and the size-28 cost have direct proofs.
For the last assertion take three disjoint present upper quadruples and a proposed wide trace H H H H H H f f f f f f f f f H H H H H H [12 Lemma 5.3] , now using the proved trace and seed lemmas.
Direct proofs for dense triple supports
Call a down-set T ⊆ { 0 , 1 , 2 , 3 } 3 T\subseteq\{0,1,2,3\}^{3} T ⊆ { 0 , 1 , 2 , 3 } 3 L = { 0 , 1 } L=\{0,1\} L = { 0 , 1 } H = { 2 , 3 } H=\{2,3\} H = { 2 , 3 } 0 , 1 , 2 0,1,2 0 , 1 , 2 [ x ] [x] [ x ] x x x ( x , t ) (x,t) ( x , t ) t t t
Lemma 4.3 (Complementary binary blocks). Let C S C_S C S ∅ ≠ S ⊂ { 0 , 1 , 2 } \varnothing\ne S\subset\{0,1,2\} ∅ = S ⊂ { 0 , 1 , 2 } T T T a = ∣ T ∩ C S ∣ a=|T\cap C_S| a = ∣ T ∩ C S ∣ b = ∣ T ∩ C S c ∣ b=|T\cap C_{S^c}| b = ∣ T ∩ C S c ∣ a , b ≤ 4 a,b\leq4 a , b ≤ 4 a + b ≤ 8 a+b\leq8 a + b ≤ 8
Proof. Antipodes in C S C_S C S C S c C_{S^c} C S c S S S b > 0 b>0 b > 0
to T T T
Lemma 4.4 (The triple cap). A legal down-set in { 0 , 1 , 2 , 3 } 3 \{0,1,2,3\}^{3} { 0 , 1 , 2 , 3 } 3 32 32 32
Proof. If it meets H 3 H^3 H 3 222 222 222 3 3 3 i i i w = 3 e i w=3e_i w = 3 e i u u u 2 2 2 i i i 1 1 1 v v v 0 0 0 i i i 2 2 2 3 3 3 { 0 , 1 , 2 } 3 \{0,1,2\}^{3} { 0 , 1 , 2 } 3 27 27 27
The value 32 32 32 [12 Lemma 5.2 and Section 9.3] . The arguments here give a direct proof and the following denser-support description. The signed facets used elsewhere still require their own exact checks.
The dense support theorem in dimension three
Define three slabs and a majority-low container by
S i = { x ∈ { 0 , 1 , 2 , 3 } 3 : x i ≤ 1 } ( i = 0 , 1 , 2 ) , J = { x : # { i : x i ≥ 2 } ≤ 1 } . S_i = \{x \in\{0,1,2,3\}^{3} : x_i \le1\} \quad(i = 0,1,2), \qquad J = \{x : \#\{i : x_i \ge2\} \le1\}. S i = { x ∈ { 0 , 1 , 2 , 3 } 3 : x i ≤ 1 } ( i = 0 , 1 , 2 ) , J = { x : # { i : x i ≥ 2 } ≤ 1 } . Each has size 32 32 32 C = L 3 C=L^3 C = L 3 H 3 H^3 H 3
A i = { x : x i ∈ H , x j ∈ L ( j ≠ i ) } , B i = { x : x i ∈ L , x j ∈ H ( j ≠ i ) } . A_i = \{x : x_i \in H,\ x_j \in L\ (j \ne i)\}, \qquad B_i = \{x : x_i \in L,\ x_j \in H\ (j \ne i)\}. A i = { x : x i ∈ H , x j ∈ L ( j = i )} , B i = { x : x i ∈ L , x j ∈ H ( j = i )} . Thus J = C ∪ A 0 ∪ A 1 ∪ A 2 J=C\cup A_0\cup A_1\cup A_2 J = C ∪ A 0 ∪ A 1 ∪ A 2 c , a i , b i c,a_i,b_i c , a i , b i T T T
Lemma 4.5 (Three local restrictions). Assume T T T a i > 0 a_i>0 a i > 0
If b i > 0 b_i>0 b i > 0 a a a 7 7 7
If b i ≥ 3 b_i\ge3 b i ≥ 3 T ∩ B i T\cap B_i T ∩ B i 0 0 0 a a a 6 6 6
If b i ≥ 3 b_i\ge3 b i ≥ 3 b j > 0 b_j>0 b j > 0 i ≠ j i\ne j i = j 1 1 1 i , j i,j i , j 0 0 0 c ≤ 6 c\le6 c ≤ 6 b i b_i b i 3 3 3 c ≤ 4 c\le4 c ≤ 4
Proof. Coordinate permutation reduces all checks to explicit triples. For (i), a 0 , b 0 > 0 a_0,b_0>0 a 0 , b 0 > 0 200 , 022 ∈ T 200,022\in T 200 , 022 ∈ T 200 , 022 , 131 200,022,131 200 , 022 , 131 3 3 3 131 131 131 a 1 ≤ 7 a_1\le7 a 1 ≤ 7 a 2 ≤ 7 a_2\le7 a 2 ≤ 7
For (ii), if 122 ∈ T 122\in T 122 ∈ T b 0 ≥ 3 b_0\ge3 b 0 ≥ 3 T ∩ B 0 T\cap B_0 T ∩ B 0 023 023 023 032 032 032 200 , 112 , 023 200,112,023 200 , 112 , 023 112 ≤ 122 112\le122 112 ≤ 122 200 , 121 , 032 200,121,032 200 , 121 , 032 121 ≤ 122 121\le122 121 ≤ 122 122 ∉ T 122\notin T 122 ∈ / T B 0 B_0 B 0 1 1 1 { 0 } × H × H \{0\}\times H\times H { 0 } × H × H 023 023 023 032 032 032 200 , 032 , 121 200,032,121 200 , 032 , 121 121 121 121 131 131 131 a 1 ≤ 6 a_1\le6 a 1 ≤ 6 200 , 023 , 112 200,023,112 200 , 023 , 112 112 112 112 113 113 113 a 2 ≤ 6 a_2\le6 a 2 ≤ 6
For (iii), b 0 ≥ 3 b_0\ge3 b 0 ≥ 3 023 023 023 b 1 > 0 b_1>0 b 1 > 0 202 202 202 023 , 202 , 110 023,202,110 023 , 202 , 110 110 110 110 111 111 111 c ≤ 6 c\le6 c ≤ 6 b b b 110 , 101 , 011 , 111 110,101,011,111 110 , 101 , 011 , 111 C C C
Theorem 4.6 (Unique dense container and sharp threshold). If a legal down-set T ⊂ { 0 , 1 , 2 , 3 } 3 T \subset\{0,1,2,3\}^{3} T ⊂ { 0 , 1 , 2 , 3 } 3 ∣ T ∣ ≥ 29 |T| \ge29 ∣ T ∣ ≥ 29 T T T S 0 , S 1 , S 2 , J S_0,S_1,S_2,J S 0 , S 1 , S 2 , J 32 32 32 29 29 29 28 28 28
Proof. The all-high case in Lemma 4.4 has size 27 27 27 T T T T T T S i S_i S i 2 e i ∈ T 2e_i \in T 2 e i ∈ T a i > 0 a_i > 0 a i > 0 J J J b i > 0 b_i > 0 b i > 0 b i > 0 b_i > 0 b i > 0 Lemma 4.3 gives a i , b i ≤ 4 a_i,b_i \le4 a i , b i ≤ 4 r = # { i : b i > 0 } r = \#\{i : b_i > 0\} r = # { i : b i > 0 } h = # { i : b i ≥ 3 } h = \#\{i : b_i \ge3\} h = # { i : b i ≥ 3 } Lemma 4.5 and c ≤ 8 c \le8 c ≤ 8
Table 1 (PDF p. 15).
For example a positive b i ≤ 2 b_i \le2 b i ≤ 2 4 + 2 = 6 4+2=6 4 + 2 = 6 b i b_i b i 4 + 4 = 8 4+4=8 4 + 4 = 8 b i b_i b i a i a_i a i 7 7 7 6 6 6 b b b ∣ T ∣ ≥ 29 |T| \ge29 ∣ T ∣ ≥ 29
The containers have pairwise intersections at most 24 24 24 ∣ S i ∩ S j ∣ = 16 |S_i \cap S_j| = 16 ∣ S i ∩ S j ∣ = 16 i ≠ j i \ne j i = j ∣ S i ∩ J ∣ = 24 |S_i \cap J| = 24 ∣ S i ∩ J ∣ = 24 J J J J J J
Finally W = { x : x 0 = 0 or x 1 = 0 } W = \{x : x_0 = 0 \text{ or } x_1 = 0\} W = { x : x 0 = 0 or x 1 = 0 } 16 + 16 − 4 = 28 16+16-4=28 16 + 16 − 4 = 28 W W W
A dense slab forces the missing rectangle
Theorem 4.7 (Slab-to-rectangle). Under the board interface and absence of a missing top-star, suppose a triple support T ⊆ S i T \subseteq S_i T ⊆ S i ∣ T ∣ ≥ 29 |T| \ge29 ∣ T ∣ ≥ 29
R i 3 = { q ∈ Q : q i , q 3 ≥ 2 } ⊆ M , ∣ R i 3 ∣ = 64. R_{i3} = \{q \in Q : q_i,q_3 \ge2\} \subseteq M,\qquad|R_{i3}| = 64. R i 3 = { q ∈ Q : q i , q 3 ≥ 2 } ⊆ M , ∣ R i 3 ∣ = 64. No hypothesis about present upper-cube 3-matchings is needed.
Proof. The binary block with coordinate i i i T T T t , t ′ t,t' t , t ′ i i i
Let q i = q 3 = 2 q_i=q_3=2 q i = q 3 = 2 q q q p = p ( i ) p=p^{(i)} p = p ( i ) i i i
[ t ] , [ t ′ ] , [ q ] , [ p ] , D ∪ { ( 3 , 0 ) } [t],\ [t'],\ [q],\ [p],\ D \cup\{(3,0)\} [ t ] , [ t ′ ] , [ q ] , [ p ] , D ∪ {( 3 , 0 )} are pairwise disjoint. Therefore q q q Q Q Q R i 3 R_{i3} R i 3 2 ⋅ 2 ⋅ 4 ⋅ 4 = 64 2\cdot2\cdot4\cdot4=64 2 ⋅ 2 ⋅ 4 ⋅ 4 = 64
A dense majority support forces 80 missing quadruples
Throughout this section T ⊆ J T \subseteq J T ⊆ J ∣ T ∣ ≥ 29 |T| \ge29 ∣ T ∣ ≥ 29 J ∖ T J \setminus T J ∖ T not needed in this section.
Lemma 4.8 (Thirty-two forced points). Under the board interface , F = H 3 × { 0 , 1 , 2 , 3 } ⊆ M F = H^3 \times\{0,1,2,3\} \subseteq M F = H 3 × { 0 , 1 , 2 , 3 } ⊆ M ∣ F ∣ = 32 |F| = 32 ∣ F ∣ = 32
Proof. Fix q ∈ F q \in F q ∈ F i = 0 , 1 , 2 i = 0,1,2 i = 0 , 1 , 2 t ( i ) t^{(i)} t ( i ) i i i 5 − q i 5-q_i 5 − q i 0 , 1 0,1 0 , 1 2 3 = 8 2^3 = 8 2 3 = 8 q q q z ∈ L ∖ { q 3 } z \in L \setminus\{q_3\} z ∈ L ∖ { q 3 } [ q ] [q] [ q ] D ∪ { ( 3 , z ) } D \cup\{(3,z)\} D ∪ {( 3 , z )} q q q
The hole structure. Within A i A_i A i ( x i − 2 , x j , x k ) (x_i - 2,x_j,x_k) ( x i − 2 , x j , x k ) T T T A i A_i A i C ⊆ T C \subseteq T C ⊆ T 111 111 111 J J J C C C A i A_i A i
E i = ( 3 in i , 1 elsewhere ) , C i , j = ( 3 in i , 0 in j , 1 in the third ) E_i = (3\text{ in }i,\ 1\text{ elsewhere}), \qquad C_{i,j} = (3\text{ in }i,\ 0\text{ in }j,\ 1\text{ in the third}) E i = ( 3 in i , 1 elsewhere ) , C i , j = ( 3 in i , 0 in j , 1 in the third ) the top and the two low-coordinate coatoms. The remaining coatom has level 2 2 2 i i i 1 1 1 C i , j C_{i,j} C i , j i i i E i , C i , j , C i , k E_i,C_{i,j},C_{i,k} E i , C i , j , C i , k
A closed pairing on the 24 double-high triples. Put B = B 0 ∪ B 1 ∪ B 2 B = B_0 \cup B_1 \cup B_2 B = B 0 ∪ B 1 ∪ B 2 i → j i \to j i → j k k k a , b ∈ { 0 , 1 } a,b \in\{0,1\} a , b ∈ { 0 , 1 }
x i = ϵ i , x j = 2 + a , x k = 2 + b , y i = 2 + a , y j = 1 − ϵ j , y k = 3 − b . (8) \begin{aligned}
x_i &= \epsilon_i, & x_j &= 2+a, & x_k &= 2+b,\\
y_i &= 2+a, & y_j &= 1-\epsilon_j, & y_k &= 3-b. \tag*{(8)}
\end{aligned} x i y i = ϵ i , = 2 + a , x j y j = 2 + a , = 1 − ϵ j , x k y k = 2 + b , = 3 − b . (8) For any fixed ϵ ∈ { 0 , 1 } 3 \epsilon\in\{0,1\}^3 ϵ ∈ { 0 , 1 } 3 B B B i i i B i B_i B i ϵ i \epsilon_i ϵ i 1 − ϵ i 1-\epsilon_i 1 − ϵ i x x x y y y
Lemma 4.9 (Present complementary traces by a cyclic rule). The cycle and ϵ \epsilon ϵ x , y x,y x , y h , h ′ ∈ T h,h' \in T h , h ′ ∈ T
Proof. Ordinary case: at most one missing low-coordinate coatom. Set ϵ = 000 \epsilon= 000 ϵ = 000 C i , j C_{i,j} C i , j C u , v C_{u,v} C u , v v v v u u u i → j → k → i i \to j \to k \to i i → j → k → i
h i = 3 − a , h j = 0 , h k = 1 , h i ′ = 1 , h j ′ = 3 − a , h k ′ = 0. \begin{aligned}
h_i &= 3-a, & h_j &= 0, & h_k &= 1,\\
h'_i &= 1, & h'_j &= 3-a, & h'_k &= 0.
\end{aligned} h i h i ′ = 3 − a , = 1 , h j h j ′ = 0 , = 3 − a , h k h k ′ = 1 , = 0. These triples partition the unused levels. If a = 1 a=1 a = 1 A i , A j A_i,A_j A i , A j a = 0 a=0 a = 0 C i , j , C j , k C_{i,j},C_{j,k} C i , j , C j , k
Exceptional case: two missing low-coordinate coatoms. Relabel their common high index as 0; the holes are exactly 311, 310, 301. Blocks A 1 A_1 A 1 A 2 A_2 A 2 0 → 1 → 2 → 0 0 \to1 \to2 \to0 0 → 1 → 2 → 0 ϵ = ( 0 , 0 , 1 ) \epsilon= (0,0,1) ϵ = ( 0 , 0 , 1 ) i → j i \to j i → j
{ 1 − ϵ i , 3 − a } , { ϵ j , 3 − a } , { 0 , 1 } \{1-\epsilon_i,3-a\},\quad\{\epsilon_j,3-a\},\quad\{0,1\} { 1 − ϵ i , 3 − a } , { ϵ j , 3 − a } , { 0 , 1 } in coordinates i , j , k i,j,k i , j , k
h i = 3 − a , h j = ϵ j , h k = e , h i ′ = 1 − ϵ i , h j ′ = 3 − a , h k ′ = 1 − e . \begin{aligned}
h_i &= 3-a,\quad h_j = \epsilon_j,\quad h_k = e,\\
h'_i &= 1-\epsilon_i,\quad h'_j = 3-a,\quad h'_k = 1-e.
\end{aligned} h i h i ′ = 3 − a , h j = ϵ j , h k = e , = 1 − ϵ i , h j ′ = 3 − a , h k ′ = 1 − e . Use e = 0 e=0 e = 0 0 → 1 0 \to1 0 → 1 1 → 2 1 \to2 1 → 2 e = 1 e=1 e = 1 2 → 0 2 \to0 2 → 0 A 0 A_0 A 0 ( 3 − a , 0 , 0 ) (3-a,0,0) ( 3 − a , 0 , 0 )
Theorem 4.10 (Majority-to-80). Under the board interface, T ⊆ J T \subseteq J T ⊆ J ∣ T ∣ ≥ 29 |T| \ge29 ∣ T ∣ ≥ 29 M ≥ 80 M \ge80 M ≥ 80
Proof. For each of the twelve base pairs x , y x,y x , y Lemma 4.9 , pair the eight wide quadruples above it as
{ ( x , 0 ) , ( y , 2 ) } , { ( x , 1 ) , ( y , 3 ) } , { ( y , 0 ) , ( x , 2 ) } , { ( y , 1 ) , ( x , 3 ) } . (9) \{(x,0),(y,2)\},\quad\{(x,1),(y,3)\},\quad\{(y,0),(x,2)\},\quad\{(y,1),(x,3)\}. \tag*{(9)} {( x , 0 ) , ( y , 2 )} , {( x , 1 ) , ( y , 3 )} , {( y , 0 ) , ( x , 2 )} , {( y , 1 ) , ( x , 3 )} . (9) These 48 pairs partition B × { 0 , 1 , 2 , 3 } B \times\{0,1,2,3\} B × { 0 , 1 , 2 , 3 } q = ( x , ℓ ) q=(x,\ell) q = ( x , ℓ ) r = ( y , t ) r=(y,t) r = ( y , t ) ℓ ∈ L \ell\in L ℓ ∈ L t ∈ H t \in H t ∈ H x , y x,y x , y h , h ′ ∈ T h,h' \in T h , h ′ ∈ T ( h ′ , 5 − t ) (h',5-t) ( h ′ , 5 − t ) D ∪ { ( 3 , 1 − ℓ ) } D \cup\{(3,1-\ell)\} D ∪ {( 3 , 1 − ℓ )}
[ h ] , [ ( h ′ , 5 − t ) ] , D ∪ { ( 3 , 1 − ℓ ) } , [ q ] , [ r ] [h],\quad[(h',5-t)],\quad D \cup\{(3,1-\ell)\},\quad[q],\quad[r] [ h ] , [( h ′ , 5 − t )] , D ∪ {( 3 , 1 − ℓ )} , [ q ] , [ r ] partition the 19 vertices: in the first three columns the four traces x , y , h , h ′ x,y,h,h' x , y , h , h ′ ℓ , t , 1 − ℓ , 5 − t \ell,t,1-\ell,5-t ℓ , t , 1 − ℓ , 5 − t q , r q,r q , r Lemma 4.8 have three. The sets are disjoint, giving M ≥ 32 + 48 = 80 M \ge32+48=80 M ≥ 32 + 48 = 80
Corollary 4.11 (The dense rectangle alternative). On a board satisfying the interface and having no missing top-star,
∣ T I ∣ ≥ 29 ⟹ M ≥ 80 or R i j ⊆ M for some i < j . |T_I| \ge29 \quad\Longrightarrow\quad M \ge80\ \text{or}\ R_{ij} \subseteq M\ \text{for some }i<j. ∣ T I ∣ ≥ 29 ⟹ M ≥ 80 or R ij ⊆ M for some i < j . The absence of an upper-cube three-matching is unnecessary for this alternative. The size-28 cost is proved constructively below; the size-24 cost retains the finite proof in Lemma 4.17 .
Proof. Relabel I I I 0 , 1 , 2 0,1,2 0 , 1 , 2 Lemma 4.2 and Theorem 4.6 give the unique slab or majority container. Apply Theorem 4.7 or Theorem 4.10 , respectively.
A constructive cost at support size 28
Lemma 4.12 (The size-28 containers). Every legal down-set T ⊆ { 0 , 1 , 2 , 3 } 3 T \subseteq\{0,1,2,3\}^3 T ⊆ { 0 , 1 , 2 , 3 } 3 S i S_i S i J J J
W = { x : x 0 = 0 or x 1 = 0 } . W=\{x:x_0=0\text{ or }x_1=0\}. W = { x : x 0 = 0 or x 1 = 0 } . Proof. By Lemma 4.4 , the all-high block is empty. Outside the slabs and J J J a i a_i a i b i > 0 b_i>0 b i > 0 Theorem 4.6 , only ( r , h ) = ( 1 , 0 ) , ( 1 , 1 ) , ( 2 , 2 ) , ( 3 , 3 ) (r,h)=(1,0),(1,1),(2,2),(3,3) ( r , h ) = ( 1 , 0 ) , ( 1 , 1 ) , ( 2 , 2 ) , ( 3 , 3 ) ( 1 , 0 ) (1,0) ( 1 , 0 ) b 0 > 0 b_0>0 b 0 > 0 a 0 = 4 a_0=4 a 0 = 4 b 0 = 2 b_0=2 b 0 = 2 a 1 = a 2 = 7 a_1=a_2=7 a 1 = a 2 = 7 c = 8 c=8 c = 8 B 0 B_0 B 0
( 200 , 112 , 023 ) , ( 200 , 121 , 032 ) , ( 200 , 122 , 031 ) . (200,112,023),\qquad(200,121,032),\qquad(200,122,031). ( 200 , 112 , 023 ) , ( 200 , 121 , 032 ) , ( 200 , 122 , 031 ) . respectively. The auxiliary points are present because a seven-point ideal in A 1 A_1 A 1 A 2 A_2 A 2
For ( 1 , 1 ) (1,1) ( 1 , 1 ) a 0 = b 0 = 4 a_0=b_0=4 a 0 = b 0 = 4 a 1 = a 2 = 6 a_1=a_2=6 a 1 = a 2 = 6 c = 8 c=8 c = 8 Lemma 4.5 gives T ∩ B 0 = { 0 } × H 2 T\cap B_0=\{0\}\times H^2 T ∩ B 0 = { 0 } × H 2 A 1 A_1 A 1 A 2 A_2 A 2 A 0 A_0 A 0
For ( 2 , 2 ) (2,2) ( 2 , 2 ) b 0 , b 1 > 0 b_0,b_1>0 b 0 , b 1 > 0 Lemma 4.5 excludes 110, so T ⊂ W T\subset W T ⊂ W T = W T=W T = W ( 3 , 3 ) (3,3) ( 3 , 3 ) A i A_i A i a i = 4 a_i=4 a i = 4 W W W
We use two elementary missing-point rules. Four known present traces disjoint from one another and from [ q ] [q] [ q ] U ( q ) = { r ∈ Q : r ≥ q } ⊆ M U(q)=\{r\in Q:r\ge q\}\subseteq M U ( q ) = { r ∈ Q : r ≥ q } ⊆ M [ q ] , [ r ] [q],[r] [ q ] , [ r ] q , r q,r q , r h h h F F F M ≥ ∣ F ∣ + h M\ge|F|+h M ≥ ∣ F ∣ + h p ( i ) p^{(i)} p ( i ) i i i
Lemma 4.13 (Eight cyclic pairs with four holes). Let T ⊆ J T\subseteq J T ⊆ J 0 → 1 → 2 → 0 0\to1\to2\to0 0 → 1 → 2 → 0 ϵ i = 0 \epsilon_i=0 ϵ i = 0 (8) . At least eight of its twelve pairs have complementary triples in T T T
Proof. The core C = L 3 C=L^3 C = L 3 J J J A i A_i A i i → j i\to j i → j k k k a , b ∈ L a,b\in L a , b ∈ L e = 0 , 1 e=0,1 e = 0 , 1
h i = 3 − a , h j = 0 , h k = e , h i ′ = 1 , h j ′ = 3 − a , h k ′ = 1 − e . (10) \begin{aligned}
h_i&=3-a, & h_j&=0, & h_k&=e,\\
h'_i&=1, & h'_j&=3-a, & h'_k&=1-e. \tag*{(10)}
\end{aligned} h i h i ′ = 3 − a , = 1 , h j h j ′ = 0 , = 3 − a , h k h k ′ = e , = 1 − e . (10) These are complementary to x , y x,y x , y b b b ( i , a ) (i,a) ( i , a )
If a slot with a = 1 a=1 a = 1 e = 0 e=0 e = 0 h ′ = ( 1 , 2 , 1 ) h'=(1,2,1) h ′ = ( 1 , 2 , 1 ) i , j , k i,j,k i , j , k h = ( 2 , 0 , 0 ) h=(2,0,0) h = ( 2 , 0 , 0 ) A i A_i A i e = 1 e=1 e = 1 A i A_i A i A j A_j A j A j A_j A j x i = 1 x_i=1 x i = 1 A j A_j A j i → j i\to j i → j
Otherwise all three a = 1 a=1 a = 1 a = 0 a=0 a = 0 a = 0 a=0 a = 0 i → j i\to j i → j E j E_j E j C i , j , C j , k C_{i,j},C_{j,k} C i , j , C j , k C u , v C_{u,v} C u , v u u u v v v
Every retained pair lifts to the four pairs in (9) . The same three-trace witness used in Theorem 4.10 proves each clause. They are disjoint and lie above the double-high block B = B 0 ∪ B 1 ∪ B 2 B=B_0\cup B_1\cup B_2 B = B 0 ∪ B 1 ∪ B 2
Lemma 4.14 (The two exceptional majority cores). For T ⊆ J T \subseteq J T ⊆ J Lemma 4.8 forces all 32 points of H 3 × { 0 , 1 , 2 , 3 } H^3 \times\{0,1,2,3\} H 3 × { 0 , 1 , 2 , 3 }
Z I = { 300 , 301 , 310 , 311 } , Z I I = { 310 , 311 , 013 , 113 } . Z_I = \{300,301,310,311\}, \qquad Z_{II} = \{310,311,013,113\}. Z I = { 300 , 301 , 310 , 311 } , Z I I = { 310 , 311 , 013 , 113 } . For these two types it forces 16 and 24 core points, respectively. With the no-top-star premise these counts increase to 24 and 28.
Proof. Fix q ∈ H 3 × { 0 , 1 , 2 , 3 } q \in H^3 \times\{0,1,2,3\} q ∈ H 3 × { 0 , 1 , 2 , 3 } 5 − q i 5-q_i 5 − q i q q q q q q
Four holes can kill all eight orientations only if all are relevant and the four pairs of orientations they remove partition the cube. A high-level-2 hole forces a high-level-3 hole above it, at least one irrelevant to q q q A i A_i A i i i i 4 + 0 + 0 4+0+0 4 + 0 + 0 2 + 2 + 0 2+2+0 2 + 2 + 0
In the first case all holes form a high face, giving Z I Z_I Z I Z I I Z_{II} Z I I Z I Z_I Z I q 0 = 3 q_0=3 q 0 = 3 Z I I Z_{II} Z I I q 0 = 3 q_0=3 q 0 = 3 q 2 = 3 q_2=3 q 2 = 3
In both types 003 , 130 ∈ T 003,130 \in T 003 , 130 ∈ T
[ 003 ] , [ ( 130 , 3 ) ] , [ 3111 ] , D ∪ { ( 3 , 0 ) } , [ 2222 ] [003], \quad[(130,3)], \quad[3111], \quad D \cup\{(3,0)\}, \quad[2222] [ 003 ] , [( 130 , 3 )] , [ 3111 ] , D ∪ {( 3 , 0 )} , [ 2222 ] are disjoint. Thus U ( 2222 ) = H 4 U(2222)=H^4 U ( 2222 ) = H 4
Theorem 4.15 (Constructive support cost). Under the board interface, if there is no missing top-star, then ∣ T I ∣ ≥ 28 |T_I| \ge28 ∣ T I ∣ ≥ 28 M ≥ 64 M \ge64 M ≥ 64
Proof. Delete maximal elements to reduce the actual support to size 28; all retained traces and their completions remain present. Lemma 4.12 supplies the following complete cases.
Majority. Outside types I and II, Lemmas 4.13 and 4.14 give M ≥ 32 + 4 ⋅ 8 = 64 M \ge32+4\cdot8=64 M ≥ 32 + 4 ⋅ 8 = 64 a , b , ℓ ∈ L a,b,\ell\in L a , b , ℓ ∈ L
( 2 , 2 + a , 2 + b , ℓ ) ; ( 3 , 1 − a , 1 − b , 2 + ℓ ) . (11) (2,2+a,2+b,\ell); \ (3,1-a,1-b,2+\ell). \tag*{(11)} ( 2 , 2 + a , 2 + b , ℓ ) ; ( 3 , 1 − a , 1 − b , 2 + ℓ ) . (11) Use h = ( 0 , a , 3 − b ) h=(0,a,3-b) h = ( 0 , a , 3 − b ) h ′ = ( 1 , 3 − a , b ) h'=(1,3-a,b) h ′ = ( 1 , 3 − a , b ) 1 − ℓ 1-\ell 1 − ℓ 3 − ℓ 3-\ell 3 − ℓ B B B 24 + 32 + 8 = 64 24+32+8=64 24 + 32 + 8 = 64
For type II, all slots on 0 → 1 0 \to1 0 → 1 a = 1 a=1 a = 1 x = ( 3 , 2 , 1 ) x=(3,2,1) x = ( 3 , 2 , 1 ) y = ( 1 , 3 , 2 ) y=(1,3,2) y = ( 1 , 3 , 2 ) 003 , 210 003,210 003 , 210 (9) gives four new disjoint pairs above B B B
Slab. Normalize T ⊆ S 0 T \subseteq S_0 T ⊆ S 0 K = L × H 2 K = L \times H^2 K = L × H 2 K K K h , h ′ ∈ T ∩ K h,h' \in T \cap K h , h ′ ∈ T ∩ K [ h ] [h] [ h ] [ h ′ ] [h'] [ h ′ ] [ 3111 ] [3111] [ 3111 ] D ∪ { ( 3 , 0 ) } D \cup\{(3,0)\} D ∪ {( 3 , 0 )} [ 2002 ] [2002] [ 2002 ] U ( 2002 ) U(2002) U ( 2002 )
Otherwise T ∩ K T \cap K T ∩ K K K K ( x 0 , x 1 − 2 , x 2 − 2 ) (x_0,x_1-2,x_2-2) ( x 0 , x 1 − 2 , x 2 − 2 ) x 0 = 1 x_0=1 x 0 = 1 x 1 = 3 x_1=3 x 1 = 3 a , b , c , d ∈ L a,b,c,d \in L a , b , c , d ∈ L
( 3 − a , 2 + b , 2 + c , d ) ; ( 2 + a , b , c , 2 + d ) . (12) (3-a,2+b,2+c,d)\ ;\ (2+a,b,c,2+d). \tag*{(12)} ( 3 − a , 2 + b , 2 + c , d ) ; ( 2 + a , b , c , 2 + d ) . (12) The witnesses are h = ( 0 , 1 − b , 3 − c ) h=(0,1-b,3-c) h = ( 0 , 1 − b , 3 − c ) h ′ = ( 1 , 3 − b , 1 − c ) h'=(1,3-b,1-c) h ′ = ( 1 , 3 − b , 1 − c ) 1 − d 1-d 1 − d 3 − d 3-d 3 − d K K K 48 + 16 = 64 48+16=64 48 + 16 = 64
For the face x 1 = 3 x_1=3 x 1 = 3 U ( 2022 ) U(2022) U ( 2022 ) (12) and add, for a , c , d ∈ L a,c,d \in L a , c , d ∈ L
( 3 − a , 1 , 2 + c , d ) ; ( 2 + a , 2 , c , 2 + d ) . (13) (3-a,1,2+c,d)\ ;\ (2+a,2,c,2+d). \tag*{(13)} ( 3 − a , 1 , 2 + c , d ) ; ( 2 + a , 2 , c , 2 + d ) . (13) Here h = ( 0 , 3 , 1 − c ) h=(0,3,1-c) h = ( 0 , 3 , 1 − c ) h ′ = ( 1 , 0 , 3 − c ) h'=(1,0,3-c) h ′ = ( 1 , 0 , 3 − c ) 1 − d 1-d 1 − d 3 − d 3-d 3 − d 40 + 16 + 8 = 64 40+16+8=64 40 + 16 + 8 = 64
The exceptional container W W W The following rows each give four known traces disjoint from [ q ] [q] [ q ]
Table 1 (PDF p. 20).
All small traces belong to W W W
The proof uses geometric cases and explicit formulas. The companion module emc4/support28.py additionally constructs and checks the witnesses on all 99 labelled supports (21 coordinate orbits), without a stored packing list. The census is corroboration of the written classification. The cyclic pairing and four-pair lift are the same constructions used above for supports of size at least 29.
Lemma 4.16 (The retained no-top-star bounds). Suppose the actual board has no missing top-star and no present upper-cube 3-matching. Then M ≥ 33 M \ge33 M ≥ 33 M = 33 , 34 M=33,34 M = 33 , 34 35 , 36 35,36 35 , 36 41 , 42 41,42 41 , 42 47 47 47 M ≤ 59 M \le59 M ≤ 59 60 ≤ M ≤ 63 60 \le M \le63 60 ≤ M ≤ 63
Proof. We specify the two exhaustive searches and their soundness invariants. They are the consumed parts of HHL’s C1 and C2, with the exact released programs and their completed executions identified in the accompanying source and reproduction records. C1 and the seven consumed C2 records were rerun during this audit, with complete outputs and timeout checks; the source’s fast checker alone cannot replace those executions.
First translate the present upper cube to a down-set C ⊆ { 0 , 1 , 2 } 4 C \subseteq\{0,1,2\}^{4} C ⊆ { 0 , 1 , 2 } 4 ( 2 , 0 , 0 , 0 ) (2,0,0,0) ( 2 , 0 , 0 , 0 ) C C C C C C h a b c ∈ { 0 , 1 , 2 , 3 } h_{abc} \in\{0,1,2,3\} h ab c ∈ { 0 , 1 , 2 , 3 } a , b , c a,b,c a , b , c ∣ C ∣ |C| ∣ C ∣
At every remaining leaf test the 216 matchings
{ ( t , π 1 ( t ) , π 2 ( t ) , π 3 ( t ) ) : t = 0 , 1 , 2 } , π i ∈ S 3 . \{(t,\pi_1(t),\pi_2(t),\pi_3(t)):t=0,1,2\},\qquad\pi_i\in S_3. {( t , π 1 ( t ) , π 2 ( t ) , π 3 ( t )) : t = 0 , 1 , 2 } , π i ∈ S 3 . Every upper 3-matching has a unique such representation after ordering by its first coordinate. The exact run checks 3116823 complete candidates of size at least 49; each contains a matching. Hence ∣ C ∣ ≤ 48 |C|\le48 ∣ C ∣ ≤ 48 M ≥ ∣ M ∩ { 1 , 2 , 3 } 4 ∣ ≥ 81 − 48 = 33 M\ge|M\cap\{1,2,3\}^{4}|\ge81-48=33 M ≥ ∣ M ∩ { 1 , 2 , 3 } 4 ∣ ≥ 81 − 48 = 33
For the second search, fix a pair or triple value v v v μ ( v ) \mu(v) μ ( v ) N ⊆ Q N\subseteq Q N ⊆ Q v v v v v v μ ( v ) = + ∞ \mu(v)=+\infty μ ( v ) = + ∞ v v v M ≥ μ ( v ) M\ge\mu(v) M ≥ μ ( v )
Here is why the finite search is exhaustive. Denote the forced-present points, forbidden to N N N F F F x x x U x U_x U x U x ∩ F ≠ ∅ U_x\cap F\ne\varnothing U x ∩ F = ∅ N N N F F F N N N h h h h h h ∣ N ∣ + h |N|+h ∣ N ∣ + h N ∪ U x N\cup U_x N ∪ U x x x x
Only the following seven lower bounds are needed:
Table 5.
All seven records in the pinned certificate have exact mode: with cutoff one above the displayed bound the completed search returns the displayed value. The full verifier checks both equalities and rejects timeouts and nonzero process exits. Only the lower bounds are used here. Permuting columns transports each bound without requiring symmetry of the actual board.
Down-closure now gives the caps directly. For M = 33 M=33 M = 33 □ \square □
Lemma 4.17 (Two support costs and a rectangle alternative). Suppose the actual board has neither a missing top-star nor a present upper-cube 3-matching. For a triple support I I I
∣ T I ∣ ≥ 24 ⟹ M ≥ 56 , ∣ T I ∣ ≥ 28 ⟹ M ≥ 64. |T_I|\ge24\ \Longrightarrow\ M\ge56,\qquad|T_I|\ge28\ \Longrightarrow\ M\ge64. ∣ T I ∣ ≥ 24 ⟹ M ≥ 56 , ∣ T I ∣ ≥ 28 ⟹ M ≥ 64. If ∣ T I ∣ ≥ 29 |\mathcal{T}_I| \ge29 ∣ T I ∣ ≥ 29 M ≥ 80 M \ge80 M ≥ 80
R i j : = { q ∈ Q : q i , q j ≥ 2 } ⊆ M for some i < j . R_{ij} := \{q \in Q : q_i, q_j \ge2\} \subseteq\mathcal{M} \quad\text{for some } i < j. R ij := { q ∈ Q : q i , q j ≥ 2 } ⊆ M for some i < j . Proof. Encode a triple down-set by its 16 heights in { 0 , … , 4 } \{0,\ldots,4\} { 0 , … , 4 }
For a fixed legal diagram, mark its wide extensions and all quadruples with at most one high coordinate present. Generate the upper-cube matching clauses and the seed clauses of its triples. A clause not already hit by a forced missing point must be hit outside the forced present set. Singleton residues force their point missing; add its up-closure and iterate. If the resulting forced missing set is F F F h h h F F F
M ≥ ∣ F ∣ + h . (14) M \ge|F| + h. \tag*{(14)} M ≥ ∣ F ∣ + h . (14) For size 24, the exact certificate regenerates all representatives under coordinate permutations, all clauses, and every claimed disjointness:
Table 1 (PDF p. 22).
The size-28 implication is Theorem 4.15 . The rectangle alternative is Corollary 4.11; it uses explicit slab and majority constructions and no stored packing. For a larger support, delete maximal elements until the required size is reached. Down-set structure and legality persist, and the smaller diagram’s extensions and clauses remain necessary. This extends the size-24 certificate to every larger support.
Lemma 4.18 (Persistence through eleven additions). Suppose R i j ⊆ M R_{ij} \subseteq\mathcal{M} R ij ⊆ M M ≤ 75 M \le75 M ≤ 75 T ≤ 96 T \le96 T ≤ 96 P ≤ 4 P \le4 P ≤ 4
Proof. By permuting columns take R = R 01 R = R_{01} R = R 01 H H H C ( H ) C(H) C ( H ) C ( H ) ∩ R ≠ ∅ C(H) \cap R \ne\varnothing C ( H ) ∩ R = ∅ R R R C ( H ) C(H) C ( H ) M ∖ R \mathcal{M} \setminus R M ∖ R R R R M ≥ 64 + 12 = 76 M \ge64 + 12 = 76 M ≥ 64 + 12 = 76 M ≤ 75 M \le75 M ≤ 75
The rectangle and its 96/4 cap for M ≤ 66 M \le66 M ≤ 66
Integer orbit counts in the top-star branch
The symmetry reduction must retain integrality of counts, even though averaged indicators need not be binary.
Lemma 4.19 (Orbit-count integrality). Let a finite group G G G Ω \Omega Ω z ∈ { 0 , 1 } Ω z \in\{0,1\}^{\Omega} z ∈ { 0 , 1 } Ω z z z x j x_j x j O j O_j O j m j m_j m j
m j x j = ∑ ω ∈ O j z ω ∈ { 0 , 1 , … , m j } . m_jx_j=\sum_{\omega\in O_j}z_\omega\in\{0,1,\ldots,m_j\}. m j x j = ω ∈ O j ∑ z ω ∈ { 0 , 1 , … , m j } . Every necessary linear system closed under G G G z z z
Proof. Each position in an orbit receives every orbit element equally often under the group action. Its average is therefore the displayed count divided by m j m_j m j
Fix the fourth column of a missing top-star and let G = S 3 G=S_3 G = S 3 Lemma 3.1 gives monotonicity and completion; Lemma 4.2 gives the pair/triple obstruction rows and caps. For each trace H H H Q 1 , Q 2 , Q 3 Q_1,Q_2,Q_3 Q 1 , Q 2 , Q 3 1 H ≤ ∑ i = 1 3 1 Q i m i s s i n g 1_H \le\sum_{i=1}^{3}1_{Q_i\ \mathrm{missing}} 1 H ≤ ∑ i = 1 3 1 Q i missing S 3 S_3 S 3
The slice with fourth coordinate 3 has size 64, including the 27 missing top-star points. Partition by its number c ∈ { 0 , … , 37 } c \in\{0,\ldots,37\} c ∈ { 0 , … , 37 } M ≤ 71 M \le71 M ≤ 71 64 − c 64-c 64 − c ≤ 7 \le7 ≤ 7 S 3 S_3 S 3 [ 0 , 1 ] [0,1] [ 0 , 1 ]
Lemma 4.20 (Integral top-star certificate). For an actual board with a missing top-star and M ≤ 71 M \le71 M ≤ 71
α T + β P ≤ M , α = 18 35 , β = 18 71 . \alpha T+\beta P\le M,\qquad\alpha=\frac{18}{35},\quad\beta=\frac{18}{71}. α T + β P ≤ M , α = 35 18 , β = 71 18 . Proof. For each of the 38 slice classes, the certificate gives a binary tree over the valid initial box. At a split, an orbit count satisfies either m j x j ≤ a m_jx_j\le a m j x j ≤ a m j x j ≥ a + 1 m_jx_j\ge a+1 m j x j ≥ a + 1 a a a
Here is the exact leaf calculation. Write the necessary rows as a i ⋅ x ≤ b i a_i\cdot x\le b_i a i ⋅ x ≤ b i ℓ ≤ x ≤ u \ell\le x\le u ℓ ≤ x ≤ u f ( x ) = c ⋅ x = M − α T − β P f(x)=c\cdot x=M-\alpha T-\beta P f ( x ) = c ⋅ x = M − α T − β P z i z_i z i D ∗ = 2485000000 D_*=2485000000 D ∗ = 2485000000
r = D ∗ c + ∑ i z i a i , L = − ∑ i z i b i + ∑ j min { r j ℓ j , r j u j } D ∗ . (15) r=D_*c+\sum_i z_i a_i,\qquad L=\frac{-\sum_i z_i b_i+\sum_j\min\{r_j\ell_j,r_ju_j\}}{D_*}. \tag*{(15)} r = D ∗ c + i ∑ z i a i , L = D ∗ − ∑ i z i b i + ∑ j min { r j ℓ j , r j u j } . (15) Every feasible point obeys
D ∗ f ( x ) = r ⋅ x − ∑ i z i ( a i ⋅ x ) ≥ ∑ j min { r j ℓ j , r j u j } − ∑ i z i b i = D ∗ L . D_*f(x)=r\cdot x-\sum_i z_i(a_i\cdot x)\ge\sum_j\min\{r_j\ell_j,r_ju_j\}-\sum_i z_i b_i=D_*L. D ∗ f ( x ) = r ⋅ x − i ∑ z i ( a i ⋅ x ) ≥ j ∑ min { r j ℓ j , r j u j } − i ∑ z i b i = D ∗ L . The residual coefficients r j r_j r j c = 0 c=0 c = 0 L > 0 L>0 L > 0 0 ≥ L 0\ge L 0 ≥ L
The verifier checks all regenerated row references and 8633 selected multipliers, every split, all roots, and absence of cycles, reused or unvisited nodes. The complete forest has 55 splits, 84 objective leaves and 9 infeasibility leaves: 148 nodes, maximum depth 8. The minimum objective lower bound is 574507909 / 4970000000 > 0 574507909/4970000000>0 574507909/4970000000 > 0 1 / 50 1/50 1/50
Proposition 4.21 (Wide-layer bound). Every actual selected board satisfies
18 35 T 3 + 18 71 P 2 ≤ M 4 . (16) \frac{18}{35}T_3+\frac{18}{71}P_2\le M_4. \tag*{(16)} 35 18 T 3 + 71 18 P 2 ≤ M 4 . (16) Here the subscript is the number of columns met by a trace, not counting D D D
Proof. If the upper cube has a present 3-matching, T = P = 0 T=P=0 T = P = 0 T ≤ 128 T\le128 T ≤ 128 P ≤ 24 P\le24 P ≤ 24 M ≥ 72 M\ge72 M ≥ 72 M − α T − β P M-\alpha T-\beta P M − α T − β P 216 / 2485 > 0 216/2485>0 216/2485 > 0 M ≤ 71 M\le71 M ≤ 71 Lemma 4.16 gives M ≥ 33 M\ge33 M ≥ 33
The first three lines use Lemma 4.17 and the retained pair caps. In the last line that lemma forces an included rectangle, since M < 80 M<80 M < 80 Lemma 4.18 applies. These cases exhaust the range; no near-maximum gap is needed.
Explicit residual witnesses on 15 and 11 vertices
For an actual board write T i T_i T i P i P_i P i M i M_i M i i i i k ∈ { 2 , 3 } k\in\{2,3\} k ∈ { 2 , 3 } D D D M ^ \widehat{M} M T ^ \widehat{T} T P ^ \widehat{P} P ( 4 , k ) (4,k) ( 4 , k ) ( 3 , k − 1 ) (3,k-1) ( 3 , k − 1 ) ( 2 , k − 2 ) (2,k-2) ( 2 , k − 2 )
Lemma 4.22 (Residual inequalities). On the subboards of an actual selected board,
9 16 T ^ + 9 32 P ^ ≤ M ^ ( k = 3 ) , 2 3 T ^ + 1 3 P ^ ≤ M ^ ( k = 2 ) . \frac{9}{16}\widehat{T}+\frac{9}{32}\widehat{P}\le\widehat{M}\quad(k=3),\qquad
\frac{2}{3}\widehat{T}+\frac{1}{3}\widehat{P}\le\widehat{M}\quad(k=2). 16 9 T + 32 9 P ≤ M ( k = 3 ) , 3 2 T + 3 1 P ≤ M ( k = 2 ) . Consequently,
9 8 T 2 + 27 32 P 1 ≤ M 3 , 2 T 1 + 2 P 0 ≤ M 2 . (17) \frac{9}{8}T_2+\frac{27}{32}P_1\le M_3,\qquad2T_1+2P_0\le M_2. \tag*{(17)} 8 9 T 2 + 32 27 P 1 ≤ M 3 , 2 T 1 + 2 P 0 ≤ M 2 . (17) Proof. If H , R 1 , … , R k H,R_1,\ldots,R_k H , R 1 , … , R k H H H R i R_i R i k k k
1 H p r e s e n t ≤ ∑ i : R i h a s s p r e a d k 1 R i m i s s i n g . (18) \mathbf{1}_{H\ \mathrm{present}}\le\sum_{i:R_i\ \mathrm{has\ spread}\ k}\mathbf{1}_{R_i\ \mathrm{missing}}. \tag*{(18)} 1 H present ≤ i : R i has spread k ∑ 1 R i missing . (18) Otherwise these traces, with the 4 − k 4-k 4 − k
Transport each literal row below under Γ k = S 3 ( D ) × ( ( S 2 × S 2 ) k ⋊ S k ) \Gamma_k = S_3(D) \times((S_2 \times S_2)^k \rtimes S_k) Γ k = S 3 ( D ) × (( S 2 × S 2 ) k ⋊ S k ) D D D z z z d k d_k d k
Table 6.
Every labelled triple and pair has the displayed coefficient, and every missing quadruple has load at most the displayed maximum. The carrier sizes ( M , T , P ) (M,T,P) ( M , T , P ) ( 480 , 288 , 54 ) (480,288,54) ( 480 , 288 , 54 ) ( 260 , 68 , 3 ) (260,68,3) ( 260 , 68 , 3 ) ( 13 , 9 , 5 ) (13,9,5) ( 13 , 9 , 5 ) ( 19 , 7 , 1 ) (19,7,1) ( 19 , 7 , 1 ) D D D
Sum over the four three-column and six two-column subboards. The multiplicities for triples, pairs and missing quadruples are ( 2 , 3 , 1 ) (2,3,1) ( 2 , 3 , 1 ) ( 3 , 6 , 1 ) (3,6,1) ( 3 , 6 , 1 ) (17) . In an actual board P 0 = 0 P_0=0 P 0 = 0 D D D
The eight 11-vertex geometries use the displayed primitive witnesses, with multipliers scaled by 4 / 3 4/3 4/3
The 31 literal rows. Write D = { d 0 , d 1 , d 2 } D=\{d_0,d_1,d_2\} D = { d 0 , d 1 , d 2 } { a 0 , a 1 , a 2 , a 3 } \{a_0,a_1,a_2,a_3\} { a 0 , a 1 , a 2 , a 3 } { b 0 , b 1 , b 2 , b 3 } \{b_0,b_1,b_2,b_3\} { b 0 , b 1 , b 2 , b 3 } k = 3 k=3 k = 3 { c 0 , c 1 , c 2 , c 3 } \{c_0,c_1,c_2,c_3\} { c 0 , c 1 , c 2 , c 3 } H H H R 1 , … , R k R_1,\ldots,R_k R 1 , … , R k z z z (18) ; full columns and low seeds contribute no missing load. The tables decode the exact data.
Table 7. 15-vertex subboard
Table 8. 11-vertex subboard
A common counting functional for propagation
On an actual board let T z T_z T z P z P_z P z z z z M z M_z M z z z z D D D P 0 = T 0 = 0 P_0 = T_0 = 0 P 0 = T 0 = 0 q = n − 4 s − 3 q = n - 4s - 3 q = n − 4 s − 3 q ≥ 2 q \ge2 q ≥ 2 q = 1 q = 1 q = 1 D s = ( s − 1 ) ( s − 2 ) ( s − 3 ) D_s = (s - 1)(s - 2)(s - 3) D s = ( s − 1 ) ( s − 2 ) ( s − 3 ) G ( s , q ) = − D s Φ s , n G(s,q) = -D_s\Phi_{s,n} G ( s , q ) = − D s Φ s , n
G ( s , q ) = D s M 4 + ( s − 1 ) ( s − 2 ) M 3 + 2 ( s − 1 ) M 2 + 6 M 1 − q ( s − 1 ) ( s − 2 ) T 3 − q ( q − 1 ) ( s − 1 ) P 2 − 2 q ( s − 1 ) T 2 − 3 q ( q − 1 ) P 1 − 6 q T 1 . (19) \begin{aligned}
G(s,q) ={}& D_sM_4 + (s - 1)(s - 2)M_3 + 2(s - 1)M_2 + 6M_1 \\
&{}- q(s - 1)(s - 2)T_3 - q(q - 1)(s - 1)P_2 - 2q(s - 1)T_2 \\
&{}- 3q(q - 1)P_1 - 6qT_1. \tag*{(19)}
\end{aligned} G ( s , q ) = D s M 4 + ( s − 1 ) ( s − 2 ) M 3 + 2 ( s − 1 ) M 2 + 6 M 1 − q ( s − 1 ) ( s − 2 ) T 3 − q ( q − 1 ) ( s − 1 ) P 2 − 2 q ( s − 1 ) T 2 − 3 q ( q − 1 ) P 1 − 6 q T 1 . (19) The following layer inequalities proved above are used throughout:
M 4 ≥ 18 35 T 3 + 18 71 P 2 , M 3 ≥ 9 8 T 2 + 27 32 P 1 , M 2 ≥ 2 T 1 . (20) M_4 \ge\frac{18}{35}T_3 + \frac{18}{71}P_2,\qquad M_3 \ge\frac{9}{8}T_2 + \frac{27}{32}P_1,\qquad M_2 \ge2T_1. \tag*{(20)} M 4 ≥ 35 18 T 3 + 71 18 P 2 , M 3 ≥ 8 9 T 2 + 32 27 P 1 , M 2 ≥ 2 T 1 . (20) For the cover-ray argument we also use the support bounds
T 3 ≤ 128 , P 2 ≤ 24. (21) T_3 \le128,\qquad P_2 \le24. \tag*{(21)} T 3 ≤ 128 , P 2 ≤ 24. (21) The scalar support caps have the direct proofs above. Signed support facets, the other support costs, and the remaining layer calculations retain their specified finite checks.
Two incidence inequalities with direct proofs
Lemma 4.23 (Completion and shifting incidences). On every actual selected board with q ≥ 2 q \ge2 q ≥ 2
8 P 2 ≤ 3 T 3 , 3 T 3 ≤ 8 T 2 . (22) 8P_2 \le3T_3,\qquad3T_3 \le8T_2. \tag*{(22)} 8 P 2 ≤ 3 T 3 , 3 T 3 ≤ 8 T 2 . (22) Proof. Each wide pair meets two columns. Adding one of the eight vertices in the other two columns produces a present exact wide triple: completion is valid because an external vertex is available. Count incidences of such a pair and one of its wide triple completions. There are 8 P 2 8P_2 8 P 2
For the second inequality, start with a present wide triple H H H x x x x x x { 1 } ∪ ( H ∖ { x } ) \{1\} \cup(H \setminus\{x\}) { 1 } ∪ ( H ∖ { x }) 3 T 3 ≤ 8 T 2 3T_3 \le8T_2 3 T 3 ≤ 8 T 2
Remark 4.24. The second proof uses the actual minimum vertex, before any averaging that forgets which residual vertex is 1. The resulting count inequality is invariant under residual and column permutations, so it survives averaging. We do not assert that every point of the original linear relaxation satisfies an unrecorded labelled minimum-shift constraint.
Two fixed counting inequalities
The file analytic_anchors.json.gz supplies two fixed rational inequalities for the ordinary selected-board model. Their coefficients do not vary with s , q s, q s , q
Lemma 4.25 (Fixed base and tangent). Under the ordinary-board necessary rows,
12144 M 4 + 552 M 3 + 48 M 2 + 6 M 1 ≥ 6624 T 3 + 3168 P 2 + 576 T 2 + 396 P 1 + 72 T 1 . (23) 12144M_4 + 552M_3 + 48M_2 + 6M_1 \ge6624T_3 + 3168P_2 + 576T_2 + 396P_1 + 72T_1. \tag*{(23)} 12144 M 4 + 552 M 3 + 48 M 2 + 6 M 1 ≥ 6624 T 3 + 3168 P 2 + 576 T 2 + 396 P 1 + 72 T 1 . (23) 3172 M 4 + 94 M 3 ≥ 1680 T 3 + 816 P 2 + 96 T 2 + 69 P 1 . (24) 3172M_4 + 94M_3 \ge1680T_3 + 816P_2 + 96T_2 + 69P_1. \tag*{(24)} 3172 M 4 + 94 M 3 ≥ 1680 T 3 + 816 P 2 + 96 T 2 + 69 P 1 . (24) Exact rational proof interface. The left side minus right side in (23) is G ( 25 , 12 ) G(25, 12) G ( 25 , 12 ) (24) H H H
Here is the precise algebraic proof, so the certificates do not rely on solver tolerances. Let x i x_i x i z i = x i z_i = x_i z i = x i z i = 1 − x i z_i = 1 - x_i z i = 1 − x i z = 0 z = 0 z = 0 a r ⋅ z ≤ 0 a_r \cdot z \le0 a r ⋅ z ≤ 0 c c c y r y_r y r
r = c + ∑ r y r a r ≥ 0. r=c+\sum_r y_r a_r\ge0. r = c + r ∑ y r a r ≥ 0. Consequently
c ⋅ z = r ⋅ z − ∑ r y r ( a r ⋅ z ) ≥ 0. c\cdot z=r\cdot z-\sum_r y_r(a_r\cdot z)\ge0. c ⋅ z = r ⋅ z − r ∑ y r ( a r ⋅ z ) ≥ 0. The minimum free residual for (23) is 9058789 / 414960 > 0 9058789/414960>0 9058789/414960 > 0 (24) it is zero, with all residuals nonnegative. The verifier reconstructs the primitive rows from their literal witnesses, the coordinate multiplicities, clique tightness, and every rational residual coefficient. Baseline rows are checked against the declared layer formulas; their mathematical and finite proofs are those of this section.
A uniform clique band beginning at 25
Theorem 4.26 (Half-slope clique propagation). Let s ≥ 25 s\ge25 s ≥ 25 2 ≤ q ≤ ( s − 1 ) / 2 2\le q\le(s-1)/2 2 ≤ q ≤ ( s − 1 ) /2 G ( s , q ) ≥ 0 G(s,q)\ge0 G ( s , q ) ≥ 0 ∣ F ∣ ≤ A 4 ( s ) |\mathcal{F}|\le A_4(s) ∣ F ∣ ≤ A 4 ( s )
Proof. First work on the formal ray s = 25 + u s=25+u s = 25 + u q = 12 + u / 2 q=12+u/2 q = 12 + u /2 u ≥ 0 u\ge0 u ≥ 0 (19) gives
G ( 25 + u , 12 + u / 2 ) = G 0 + u G 1 + u 2 G 2 + u 3 G 3 , G(25+u,12+u/2)=G_0+uG_1+u^2G_2+u^3G_3, G ( 25 + u , 12 + u /2 ) = G 0 + u G 1 + u 2 G 2 + u 3 G 3 , where
G 0 = G ( 25 , 12 ) , G 1 = 1586 M 4 + 47 M 3 + 2 M 2 − 840 T 3 − 408 P 2 − 48 T 2 − 69 2 P 1 − 3 T 1 , G 2 = 69 M 4 + M 3 − 71 2 T 3 − 35 2 P 2 − T 2 − 3 4 P 1 , G 3 = M 4 − 1 2 T 3 − 1 4 P 2 . \begin{aligned}
G_0&=G(25,12),\\
G_1&=1586M_4+47M_3+2M_2-840T_3-408P_2-48T_2-\frac{69}{2}P_1-3T_1,\\
G_2&=69M_4+M_3-\frac{71}{2}T_3-\frac{35}{2}P_2-T_2-\frac{3}{4}P_1,\\
G_3&=M_4-\frac{1}{2}T_3-\frac{1}{4}P_2.
\end{aligned} G 0 G 1 G 2 G 3 = G ( 25 , 12 ) , = 1586 M 4 + 47 M 3 + 2 M 2 − 840 T 3 − 408 P 2 − 48 T 2 − 2 69 P 1 − 3 T 1 , = 69 M 4 + M 3 − 2 71 T 3 − 2 35 P 2 − T 2 − 4 3 P 1 , = M 4 − 2 1 T 3 − 4 1 P 2 . The first coefficient is nonnegative by (23) . The next satisfies
G 1 = 1 2 H + 2 M 2 − 3 T 1 ≥ 0 G_1=\frac{1}{2}H+2M_2-3T_1\ge0 G 1 = 2 1 H + 2 M 2 − 3 T 1 ≥ 0 by (24) and M 2 ≥ 2 T 1 M_2\ge2T_1 M 2 ≥ 2 T 1
G 2 ≥ − T 3 70 − P 2 142 + T 2 8 + 3 P 1 32 . G_2\ge-\frac{T_3}{70}-\frac{P_2}{142}+\frac{T_2}{8}+\frac{3P_1}{32}. G 2 ≥ − 70 T 3 − 142 P 2 + 8 T 2 + 32 3 P 1 . Apply (22) ; because the coefficient of P 2 P_2 P 2
G 2 ≥ ( 3 64 − 1 70 − 3 1136 ) T 3 + 3 32 P 1 = 4763 159040 T 3 + 3 32 P 1 ≥ 0. (25) G_2\ge\left(\frac{3}{64}-\frac{1}{70}-\frac{3}{1136}\right)T_3+\frac{3}{32}P_1
=\frac{4763}{159040}T_3+\frac{3}{32}P_1\ge0. \tag*{(25)} G 2 ≥ ( 64 3 − 70 1 − 1136 3 ) T 3 + 32 3 P 1 = 159040 4763 T 3 + 32 3 P 1 ≥ 0. (25) Finally,
G 3 ≥ T 3 70 + P 2 284 ≥ 0. G_3\ge\frac{T_3}{70}+\frac{P_2}{284}\ge0. G 3 ≥ 70 T 3 + 284 P 2 ≥ 0. All four Taylor coefficients are nonnegative, proving the entire ray, not merely a finite sample. For fixed s s s G ( s , q ) G(s,q) G ( s , q ) q ≥ 1 q\ge1 q ≥ 1 q q q q ( q − 1 ) q(q-1) q ( q − 1 ) Φ = − G / D s ≤ 0 \Phi=-G/D_s\le0 Φ = − G / D s ≤ 0
Cover rays from two fixed endpoint anchors
For s > 0 s > 0 s > 0
Z ( s , q ) = 24 s [ B 4 ( 4 s + 3 + q , s ) − A 4 ( s ) ] = 4 q 3 + 42 q 2 s + 18 q 2 + 148 q s 2 + 126 q s + 22 q − 81 s 3 − 162 s 2 − 99 s − 18 , (26) Z(s,q)=\frac{24}{s}\left[B_4(4s+3+q,s)-A_4(s)\right]
=4q^3+42q^2s+18q^2+148qs^2+126qs+22q-81s^3-162s^2-99s-18, \tag*{(26)} Z ( s , q ) = s 24 [ B 4 ( 4 s + 3 + q , s ) − A 4 ( s ) ] = 4 q 3 + 42 q 2 s + 18 q 2 + 148 q s 2 + 126 q s + 22 q − 81 s 3 − 162 s 2 − 99 s − 18 , (26) and set J ( s , q ) = G ( s , q ) + Z ( s , q ) J(s,q)=G(s,q)+Z(s,q) J ( s , q ) = G ( s , q ) + Z ( s , q ) Z Z Z ( s 4 ) / D s = s / 24 \binom{s}{4}/D_s=s/24 ( 4 s ) / D s = s /24 J ≥ 0 J\geq0 J ≥ 0
∣ F ∣ − A 4 ( s ) ≤ ( s 4 ) Z ( s , q ) D s = B 4 ( n , s ) − A 4 ( s ) . |\mathcal{F}|-A_4(s)\leq\binom{s}{4}\frac{Z(s,q)}{D_s}=B_4(n,s)-A_4(s). ∣ F ∣ − A 4 ( s ) ≤ ( 4 s ) D s Z ( s , q ) = B 4 ( n , s ) − A 4 ( s ) . We use the upper-endpoint certificates at ( s , n ) = ( 33 , 152 ) (s,n)=(33,152) ( s , n ) = ( 33 , 152 ) ( 36 , 165 ) (36,165) ( 36 , 165 )
J ( 33 , 17 ) ≥ m o : = 37290250580546743 1562500000000 > 0 , J(33,17)\geq m_o:=\frac{37290250580546743}{1562500000000}>0, J ( 33 , 17 ) ≥ m o := 1562500000000 37290250580546743 > 0 , J ( 36 , 18 ) ≥ m e : = 426057745890672159 50000000000000 > 0. (27) J(36,18)\geq m_e:=\frac{426057745890672159}{50000000000000}>0. \tag*{(27)} J ( 36 , 18 ) ≥ m e := 50000000000000 426057745890672159 > 0. (27) These follow from the rational upper bounds for Φ \Phi Φ
Theorem 4.27 (Two cover rays). The cover bound holds for actual shifted saturated ONE families at
n = 9 s + 7 2 ( s ≥ 33 odd ) , n = 9 s + 6 2 ( s ≥ 36 even ) . n=\frac{9s+7}{2}\quad(s\geq33\ \text{odd}),\qquad n=\frac{9s+6}{2}\quad(s\geq36\ \text{even}). n = 2 9 s + 7 ( s ≥ 33 odd ) , n = 2 9 s + 6 ( s ≥ 36 even ) . Proof. Expand J J J ( s , q ) = ( 33 + u , 17 + u / 2 ) (s,q)=(33+u,17+u/2) ( s , q ) = ( 33 + u , 17 + u /2 ) ( 36 + u , 18 + u / 2 ) (36+u,18+u/2) ( 36 + u , 18 + u /2 ) J = J 0 + u J 1 + u 2 J 2 + u 3 J 3 J=J_0+uJ_1+u^2J_2+u^3J_3 J = J 0 + u J 1 + u 2 J 2 + u 3 J 3 (27) . At either anchor ( s 0 , q 0 ) (s_0,q_0) ( s 0 , q 0 ) G G G
G 1 ≥ a 1 T 3 + b 1 P 2 + c 1 T 2 + d 1 P 1 + T 1 , G_1\geq a_1T_3+b_1P_2+c_1T_2+d_1P_1+T_1, G 1 ≥ a 1 T 3 + b 1 P 2 + c 1 T 2 + d 1 P 1 + T 1 , G 2 ≥ a 2 T 3 + b 2 P 2 + 1 8 T 2 + 3 32 P 1 , G_2\geq a_2T_3+b_2P_2+\frac{1}{8}T_2+\frac{3}{32}P_1, G 2 ≥ a 2 T 3 + b 2 P 2 + 8 1 T 2 + 32 3 P 1 , G 3 ≥ 1 70 T 3 + 1 284 P 2 , G_3\geq\frac{1}{70}T_3+\frac{1}{284}P_2, G 3 ≥ 70 1 T 3 + 284 1 P 2 , where the exact coefficients at the two anchors are
Table 1 (PDF p. 29).
The Z Z Z u u u
( 145792 , 13196 , 398 , 4 ) , ( 60966 , 8660 , 675 / 2 , 4 ) . (145792,13196,398,4),\qquad(60966,8660,675/2,4). ( 145792 , 13196 , 398 , 4 ) , ( 60966 , 8660 , 675/2 , 4 ) . Using T 3 ≤ 128 T_3\leq128 T 3 ≤ 128 P 2 ≤ 24 P_2\leq24 P 2 ≤ 24
Table 2.
All are strictly positive. Thus J > 0 J>0 J > 0 u ≥ 0 u\geq0 u ≥ 0
The strict margins in (27) suffice for propagation. The numerical ONE gaps in § 5 continue to use their separately checked endpoint bounds.
Locating every critical point without a finite scan
Lemma 4.28 (Crossing localization). For odd s ≥ 3 s \ge3 s ≥ 3
a s ≤ 9 s + 7 2 a_s \le\frac{9s+7}{2} a s ≤ 2 9 s + 7 For even s ≥ 26 s \ge26 s ≥ 26
a s ≤ 9 s + 6 2 a_s \le\frac{9s+6}{2} a s ≤ 2 9 s + 6 Consequently, for every integer s ≥ 25 s \ge25 s ≥ 25 a s − 1 ≤ ⌊ ( 9 s + 5 ) / 2 ⌋ a_s-1 \le\lfloor(9s+5)/2\rfloor a s − 1 ≤ ⌊( 9 s + 5 ) /2 ⌋
Proof. Substitution in (26) gives
Z ( s , s + 1 2 ) = 2 ( s 2 − 1 ) ( 2 s + 1 ) > 0 ( s > 1 ) . Z\left(s,\frac{s+1}{2}\right)=2(s^2-1)(2s+1)>0 \qquad(s>1). Z ( s , 2 s + 1 ) = 2 ( s 2 − 1 ) ( 2 s + 1 ) > 0 ( s > 1 ) . At q = s / 2 q=s/2 q = s /2 s = 26 + u s=26+u s = 26 + u
Z ( 26 + u , 26 + u 2 ) = 4116 + 3110 u + 435 2 u 2 + 4 u 3 > 0 ( u ≥ 0 ) . Z\left(26+u,\frac{26+u}{2}\right)=4116+3110u+\frac{435}{2}u^2+4u^3>0 \qquad(u\ge0). Z ( 26 + u , 2 26 + u ) = 4116 + 3110 u + 2 435 u 2 + 4 u 3 > 0 ( u ≥ 0 ) . For the stated parity, the corresponding n n n B 4 ( n , s ) B_4(n,s) B 4 ( n , s )
Corollary 4.29 (Critical endpoints from a finite anchor set). All critical ONE inputs hold for every s ≥ 35 s \ge35 s ≥ 35 and also for s = 33 s=33 s = 33 using Theorems 4.26 and 4.27 . Every lower critical input with s ≥ 25 s \ge25 s ≥ 25 follows from Theorem 4.26 .
Proof. The lower point belongs to the clique band by Lemma 4.28 . If the upper point also satisfies 2 q ≤ s − 1 2q \le s-1 2 q ≤ s − 1 q = ( s + 1 ) / 2 q=(s+1)/2 q = ( s + 1 ) /2 q = s / 2 q=s/2 q = s /2 s ≥ 33 s \ge33 s ≥ 33 s ≥ 36 s \ge36 s ≥ 36
For the remaining finite range retain both endpoints for 5 ≤ s ≤ 24 5 \le s \le24 5 ≤ s ≤ 24 25 ≤ s ≤ 32 25 \le s \le32 25 ≤ s ≤ 32 s = 34 s=34 s = 34 s = 33 , 36 s=33,36 s = 33 , 36 Lemma 4.25 , they give 53 endpoint-or-anchor obligations for the main cardinality argument. The polynomial argument supplies all other critical inputs. The four small full-carrier cases and the layer proofs remain separate dependencies.
The strong critical clique bound from the layers
Proposition 4.30 (Direct layer proof of a half-ray). Using only (20) and (22) , G ( s , q ) ≥ 0 G(s,q) \ge0 G ( s , q ) ≥ 0 whenever s ≥ 71 s \ge71 s ≥ 71 and 2 ≤ q ≤ ( s − 1 ) / 2 2 \le q \le(s-1)/2 2 ≤ q ≤ ( s − 1 ) /2
Proof. At q = ( s − 1 ) / 2 q=(s-1)/2 q = ( s − 1 ) /2 G G G G ≥ a T 3 + b P 2 + c T 2 + d P 1 + e T 1 G \ge aT_3+bP_2+cT_2+dP_1+eT_1 G ≥ a T 3 + b P 2 + c T 2 + d P 1 + e T 1
a = ( s − 73 ) ( s − 2 ) ( s − 1 ) 70 , b = ( s − 73 ) ( s − 3 ) ( s − 1 ) 284 , a=\frac{(s-73)(s-2)(s-1)}{70},\qquad
b=\frac{(s-73)(s-3)(s-1)}{284}, a = 70 ( s − 73 ) ( s − 2 ) ( s − 1 ) , b = 284 ( s − 73 ) ( s − 3 ) ( s − 1 ) , c = ( s − 10 ) ( s − 1 ) 8 , d = 3 ( s − 1 ) ( s + 6 ) 32 , e = s − 1. c=\frac{(s-10)(s-1)}{8},\qquad
d=\frac{3(s-1)(s+6)}{32},\qquad
e=s-1. c = 8 ( s − 10 ) ( s − 1 ) , d = 32 3 ( s − 1 ) ( s + 6 ) , e = s − 1. For s ≥ 73 s \ge73 s ≥ 73 71 ≤ s ≤ 73 71 \le s \le73 71 ≤ s ≤ 73 b ≤ 0 b \le0 b ≤ 0 (22) gives
G ≥ ( a + 3 8 b + 3 8 c ) T 3 + d P 1 + e T 1 . G\ge\left(a+\frac{3}{8}b+\frac{3}{8}c\right)T_3+dP_1+eT_1. G ≥ ( a + 8 3 b + 8 3 c ) T 3 + d P 1 + e T 1 . The coefficient in parentheses equals
( s − 1 ) ( 2482 s 2 − 178905 s + 303152 ) 159040 . \frac{(s-1)(2482s^2-178905s+303152)}{159040}. 159040 ( s − 1 ) ( 2482 s 2 − 178905 s + 303152 ) . Writing s = 71 + u s=71+u s = 71 + u 112659 + 173539 u + 2482 u 2 > 0 112659+173539u+2482u^2>0 112659 + 173539 u + 2482 u 2 > 0 q q q
Proof of Proposition 4.1 . The following identities locate the upper crossing:
Z ( 49 + u , 48 + u 2 ) = 4728 + 9946 u + 397 u 2 + 4 u 3 > 0 , Z\left(49+u,\frac{48+u}{2}\right)=4728+9946u+397u^2+4u^3>0, Z ( 49 + u , 2 48 + u ) = 4728 + 9946 u + 397 u 2 + 4 u 3 > 0 , Z ( 74 + u , 72 + u 2 ) = 32904 + 22978 u + 1201 2 u 2 + 4 u 3 > 0 ( u ≥ 0 ) . Z\left(74+u,\frac{72+u}{2}\right)=32904+22978u+\frac{1201}{2}u^2+4u^3>0 \qquad(u\ge0). Z ( 74 + u , 2 72 + u ) = 32904 + 22978 u + 2 1201 u 2 + 4 u 3 > 0 ( u ≥ 0 ) . For odd s ≥ 73 s\ge73 s ≥ 73 q ≤ ( s − 1 ) / 2 q\le(s-1)/2 q ≤ ( s − 1 ) /2 n = a s n=a_s n = a s s ≥ 74 s\ge74 s ≥ 74 q ≤ ( s − 2 ) / 2 q\le(s-2)/2 q ≤ ( s − 2 ) /2 Proposition 4.30 . Summing − G / D s -G/D_s − G / D s ∣ F ∣ ≤ A 4 ( s ) |\mathcal{F}|\le A_4(s) ∣ F ∣ ≤ A 4 ( s )
Structural consequences of the global proof
The strict margins in the preceding proof also constrain extremizers. The following conclusions have explicitly stated domains; they do not classify every crossing case or transfer quantitative stability through arbitrary shifts.
ONE gaps and their propagation
Proposition 5.1 (All finite upper gaps). For 5 ≤ s ≤ 72 5\le s\le72 5 ≤ s ≤ 72 U s U_s U s ∣ F ∣ − A 4 ( s ) |\mathcal{F}|-A_4(s) ∣ F ∣ − A 4 ( s ) n = a s n=a_s n = a s h s = B 4 ( a s , s ) − A 4 ( s ) − ⌊ U s ⌋ h_s=B_4(a_s,s)-A_4(s)-\lfloor U_s\rfloor h s = B 4 ( a s , s ) − A 4 ( s ) − ⌊ U s ⌋ h s h_s h s s = 5 s=5 s = 5 s s s n ≥ a s n\ge a_s n ≥ a s
∣ F ∣ ≤ B 4 ( n , s ) − h s . |\mathcal{F}|\le B_4(n,s)-h_s. ∣ F ∣ ≤ B 4 ( n , s ) − h s . For 73 ≤ s ≤ 121 73\le s\le121 73 ≤ s ≤ 121 h s = B 4 ( a s , s ) − A 4 ( s ) > 0 h_s=B_4(a_s,s)-A_4(s)>0 h s = B 4 ( a s , s ) − A 4 ( s ) > 0 s = 97 s=97 s = 97
Proof. At the base, saturation preserves the matching avoiding 1. For 5 ≤ s ≤ 72 5\le s\le72 5 ≤ s ≤ 72 h s h_s h s 73 ≤ s ≤ 121 73\le s\le121 73 ≤ s ≤ 121 Proposition 4.1 gives ∣ F ∣ ≤ A 4 ( s ) |\mathcal{F}|\le A_4(s) ∣ F ∣ ≤ A 4 ( s )
Write F [ N ] = F ∩ ( [ N ] 4 ) \mathcal{F}[N]=\mathcal{F}\cap\binom{[N]}{4} F [ N ] = F ∩ ( 4 [ N ] ) s s s { 2 , … , 4 s + 1 } \{2,\ldots,4s+1\} { 2 , … , 4 s + 1 } F [ a s ] \mathcal{F}[a_s] F [ a s ] s s s N ≥ a s N\ge a_s N ≥ a s Lemma 2.4 gives
B 4 ( N + 1 , s ) − ∣ F [ N + 1 ] ∣ ≥ B 4 ( N , s ) − ∣ F [ N ] ∣ . B_4(N+1,s)-|\mathcal{F}[N+1]|\ge B_4(N,s)-|\mathcal{F}[N]|. B 4 ( N + 1 , s ) − ∣ F [ N + 1 ] ∣ ≥ B 4 ( N , s ) − ∣ F [ N ] ∣. The added link has at most B 3 ( N , s ) B_3(N,s) B 3 ( N , s )
The stronger weight surplus for stability
For reference the six layer comparisons are
q s − 3 ≤ 18 35 , q ( q − 1 ) ( s − 2 ) ( s − 3 ) ≤ 18 71 \frac{q}{s-3} \le\frac{18}{35}, \qquad\frac{q(q-1)}{(s-2)(s-3)} \le\frac{18}{71} s − 3 q ≤ 35 18 , ( s − 2 ) ( s − 3 ) q ( q − 1 ) ≤ 71 18 2 q s − 2 ≤ 9 8 , 3 q ( q − 1 ) ( s − 1 ) ( s − 2 ) ≤ 27 32 \frac{2q}{s-2} \le\frac{9}{8}, \qquad\frac{3q(q-1)}{(s-1)(s-2)} \le\frac{27}{32} s − 2 2 q ≤ 8 9 , ( s − 1 ) ( s − 2 ) 3 q ( q − 1 ) ≤ 32 27 3 q s − 1 ≤ 2 , 6 q ( q − 1 ) s ( s − 1 ) ≤ 2. (28) \frac{3q}{s-1} \le2, \qquad\frac{6q(q-1)}{s(s-1)} \le2. \tag*{(28)} s − 1 3 q ≤ 2 , s ( s − 1 ) 6 q ( q − 1 ) ≤ 2. (28) Lemma 5.2 (Structural weight surplus). Let s ≥ 122 s \ge122 s ≥ 122 4 s + 4 ≤ n ≤ a s 4s+4 \le n \le a_s 4 s + 4 ≤ n ≤ a s (28) , in row order, are bounded componentwise by ( 1 / 2 , 1 / 4 , 1 , 3 / 4 , 3 / 2 , 3 / 2 ) (1/2,1/4,1,3/4,3/2,3/2) ( 1/2 , 1/4 , 1 , 3/4 , 3/2 , 3/2 )
Proof. For s ≥ 122 s \ge122 s ≥ 122
a s ≤ N s : = ⌊ 9 s + 3 2 ⌋ . a_s \le N_s := \left\lfloor\frac{9s+3}{2} \right\rfloor. a s ≤ N s := ⌊ 2 9 s + 3 ⌋ . Write P ( s ) = 24 [ B 4 ( N s , s ) − A 4 ( s ) ] P(s)=24[B_4(N_s,s)-A_4(s)] P ( s ) = 24 [ B 4 ( N s , s ) − A 4 ( s )] s = 2 u s=2u s = 2 u N s = 9 u + 1 N_s=9u+1 N s = 9 u + 1
P ( 2 u ) = 64 u 4 − 3844 u 3 − 736 u 2 − 44 u . P(2u)=64u^4-3844u^3-736u^2-44u. P ( 2 u ) = 64 u 4 − 3844 u 3 − 736 u 2 − 44 u . At u = 61 + v u=61+v u = 61 + v
10877520 + 15106728 v + 724676 v 2 + 11772 v 3 + 64 v 4 > 0 ( v ≥ 0 ) . 10877520+15106728v+724676v^2+11772v^3+64v^4>0 \qquad(v\ge0). 10877520 + 15106728 v + 724676 v 2 + 11772 v 3 + 64 v 4 > 0 ( v ≥ 0 ) . For s = 2 u + 1 s=2u+1 s = 2 u + 1 N s = 9 u + 6 N_s=9u+6 N s = 9 u + 6
P ( 2 u + 1 ) = 64 u 4 − 2944 u 3 − 5296 u 2 − 3104 u − 600. P(2u+1)=64u^4-2944u^3-5296u^2-3104u-600. P ( 2 u + 1 ) = 64 u 4 − 2944 u 3 − 5296 u 2 − 3104 u − 600. At u = 48 + v u=48+v u = 48 + v
1804200 + 7451104 v + 455504 v 2 + 9344 v 3 + 64 v 4 > 0 ( v ≥ 0 ) . 1804200+7451104v+455504v^2+9344v^3+64v^4>0 \qquad(v\ge0). 1804200 + 7451104 v + 455504 v 2 + 9344 v 3 + 64 v 4 > 0 ( v ≥ 0 ) . The odd case holds already for s ≥ 97 s\ge97 s ≥ 97 s ≥ 122 s\ge122 s ≥ 122 B 4 ( n , s ) B_4(n,s) B 4 ( n , s )
q = n − 4 s − 3 ≤ s − 3 2 . q=n-4s-3\le\frac{s-3}{2}. q = n − 4 s − 3 ≤ 2 s − 3 . Using also q ( q − 1 ) ≤ ( s − 3 ) ( s − 5 ) / 4 q(q-1)\le(s-3)(s-5)/4 q ( q − 1 ) ≤ ( s − 3 ) ( s − 5 ) /4 (28) are bounded componentwise by
( 1 / 2 , 1 / 4 , 1 , 3 / 4 , 3 / 2 , 3 / 2 ) , (1/2,1/4,1,3/4,3/2,3/2), ( 1/2 , 1/4 , 1 , 3/4 , 3/2 , 3/2 ) , strictly below the respective right sides.
The polynomial checker reconstructs both identities from falling products. These stronger coefficients are used for stability below; cardinality already follows from the wider band in § 4.9 .
Clique stability and equality
The source of stability is a surplus in the same layer inequalities that prove cardinality. If S τ S_\tau S τ W τ W_\tau W τ W τ ≥ ( 1 + 1 / 71 ) S τ W_\tau\ge(1+1/71)S_\tau W τ ≥ ( 1 + 1/71 ) S τ d = ∑ τ ( W τ − S τ ) ≥ X / 71 d=\sum_\tau(W_\tau-S_\tau)\ge X/71 d = ∑ τ ( W τ − S τ ) ≥ X /71 ∑ τ S τ \sum_\tau S_\tau ∑ τ S τ X X X
Theorem 5.3 (Explicit clique stability for shifted ONE families). Let s ≥ 122 s \ge122 s ≥ 122 4 s + 4 ≤ n ≤ a s 4s+4 \le n \le a_s 4 s + 4 ≤ n ≤ a s F \mathcal{F} F s s s K = [ 4 s + 3 ] K=[4s+3] K = [ 4 s + 3 ] d = A 4 ( s ) − ∣ F ∣ d=A_4(s)-|\mathcal{F}| d = A 4 ( s ) − ∣ F ∣ X = ∣ F ∖ ( K 4 ) ∣ X=\left|\mathcal{F}\setminus\binom{K}{4}\right| X = F ∖ ( 4 K ) d ≥ 0 d \ge0 d ≥ 0
X ≤ 71 d , ∣ F △ ( K 4 ) ∣ ≤ 143 d . X \le71d,\qquad\left|\mathcal{F}\mathbin{\triangle}\binom{K}{4}\right| \le143d. X ≤ 71 d , F △ ( 4 K ) ≤ 143 d . Proof. First take a saturated family at n = a s n=a_s n = a s λ 4 = 1 \lambda_4=1 λ 4 = 1 λ 3 = 1 / ( s − 3 ) \lambda_3=1/(s-3) λ 3 = 1/ ( s − 3 ) λ 2 = 1 / ( s − 2 2 ) \lambda_2=1/\binom{s-2}{2} λ 2 = 1/ ( 2 s − 2 ) e 1 , … , e 6 e_1,\ldots,e_6 e 1 , … , e 6 (28) , in row order. On a board τ \tau τ
S τ = λ 4 ( e 1 T 3 + e 2 P 2 ) + λ 3 ( e 3 T 2 + e 4 P 1 ) + λ 2 ( e 5 T 1 + e 6 P 0 ) . S_\tau=\lambda_4(e_1T_3+e_2P_2)+\lambda_3(e_3T_2+e_4P_1)+\lambda_2(e_5T_1+e_6P_0). S τ = λ 4 ( e 1 T 3 + e 2 P 2 ) + λ 3 ( e 3 T 2 + e 4 P 1 ) + λ 2 ( e 5 T 1 + e 6 P 0 ) . The notation T z T_z T z P z P_z P z W τ W_\tau W τ S τ − W τ S_\tau-W_\tau S τ − W τ
The proof of Lemma 5.2 bounds e e e v = ( 1 / 2 , 1 / 4 , 1 , 3 / 4 , 3 / 2 , 3 / 2 ) v=(1/2,1/4,1,3/4,3/2,3/2) v = ( 1/2 , 1/4 , 1 , 3/4 , 3/2 , 3/2 ) c = ( 18 / 35 , 18 / 71 , 9 / 8 , 27 / 32 , 2 , 2 ) c=(18/35,18/71,9/8,27/32,2,2) c = ( 18/35 , 18/71 , 9/8 , 27/32 , 2 , 2 )
( c i v i ) i = 1 6 = ( 36 / 35 , 72 / 71 , 9 / 8 , 9 / 8 , 4 / 3 , 4 / 3 ) . \left(\frac{c_i}{v_i}\right)_{i=1}^{6}=(36/35,72/71,9/8,9/8,4/3,4/3). ( v i c i ) i = 1 6 = ( 36/35 , 72/71 , 9/8 , 9/8 , 4/3 , 4/3 ) . Thus c i ≥ ( 72 / 71 ) e i c_i\ge(72/71)e_i c i ≥ ( 72/71 ) e i λ 4 , λ 3 , λ 2 \lambda_4,\lambda_3,\lambda_2 λ 4 , λ 3 , λ 2 72 S τ / 71 72S_\tau/71 72 S τ /71 W τ − S τ ≥ S τ / 71 W_\tau-S_\tau\ge S_\tau/71 W τ − S τ ≥ S τ /71 d = ∑ τ ( W τ − S τ ) d=\sum_\tau(W_\tau-S_\tau) d = ∑ τ ( W τ − S τ )
∑ τ S τ = ∑ H a trace ∣ H ∣ = 2 , 3 ( n − 4 s − 3 4 − ∣ H ∣ ) = X . \sum_\tau S_\tau=\sum_{\substack{H\text{ a trace}\\|H|=2,3}}\left(\frac{n-4s-3}{4-|H|}\right)=X. τ ∑ S τ = H a trace ∣ H ∣ = 2 , 3 ∑ ( 4 − ∣ H ∣ n − 4 s − 3 ) = X . Indeed Lemma 3.1 gives one small trace per edge outside K K K X ≤ 71 d X\le71d X ≤ 71 d
Start with the original family, add isolated vertices up to a s a_s a s G ⊇ F \mathcal{G}\supseteq\mathcal{F} G ⊇ F § 3.1 . The original matching avoiding 1 persists, and the fixed set K K K
X ( F ) ≤ X ( G ) ≤ 71 ( A 4 ( s ) − ∣ G ∣ ) ≤ 71 ( A 4 ( s ) − ∣ F ∣ ) . X(\mathcal{F})\le X(\mathcal{G})\le71(A_4(s)-|\mathcal{G}|)\le71(A_4(s)-|\mathcal{F}|). X ( F ) ≤ X ( G ) ≤ 71 ( A 4 ( s ) − ∣ G ∣ ) ≤ 71 ( A 4 ( s ) − ∣ F ∣ ) . This also gives d ≥ 0 d\ge0 d ≥ 0 ∣ F △ ( K 4 ) ∣ = d + 2 X \left|\mathcal{F}\mathbin{\triangle}\binom{K}{4}\right|=d+2X F △ ( 4 K ) = d + 2 X
The constants are sufficient, without an optimality assertion. The quantitative statement requires both shiftedness and ONE.
Proposition 5.4 (Clique rigidity from the strict anchor). Let s ≥ 25 s\ge25 s ≥ 25 4 s + 4 ≤ n < a s 4s+4\le n<a_s 4 s + 4 ≤ n < a s F \mathcal{F} F s s s ∣ F ∣ = A 4 ( s ) |\mathcal{F}|=A_4(s) ∣ F ∣ = A 4 ( s )
F = ( [ 4 s + 3 ] 4 ) . \mathcal{F}=\binom{[4s+3]}{4}. F = ( 4 [ 4 s + 3 ] ) . Proof. First prove rigidity for saturated shifted ONE families of size A 4 ( s ) A_4(s) A 4 ( s ) 2 ≤ q = n − 4 s − 3 ≤ ( s − 1 ) / 2 2\le q=n-4s-3\le(s-1)/2 2 ≤ q = n − 4 s − 3 ≤ ( s − 1 ) /2 Theorem 4.26 gives G ( s , q ) ≥ G ( 25 , 12 ) G(s,q)\ge G(25,12) G ( s , q ) ≥ G ( 25 , 12 ) G G G q q q Lemma 4.25 gives
G ( 25 , 12 ) ≥ r 0 ∑ i f r e e z i , r 0 = 9058789 414960 > 0 , G(25,12)\ge r_0\sum_{i\ \mathrm{free}}z_i,\qquad r_0=\frac{9058789}{414960}>0, G ( 25 , 12 ) ≥ r 0 i free ∑ z i , r 0 = 414960 9058789 > 0 , where z i = x i z_i=x_i z i = x i z i = 1 − x i z_i=1-x_i z i = 1 − x i
∑ τ G τ ( s , q ) = D s ( A 4 ( s ) − ∣ F ∣ ) = 0. (29) \sum_\tau G_\tau(s,q)=D_s(A_4(s)-|\mathcal{F}|)=0. \tag*{(29)} τ ∑ G τ ( s , q ) = D s ( A 4 ( s ) − ∣ F ∣ ) = 0. (29) All summands are nonnegative, so every free small-trace coordinate vanishes on every board. These coordinates are averages of indicators; thus all corresponding traces are absent. The small traces contained entirely in D D D Lemma 3.1 .
Every trace meets at most four matching columns, which can be extended to a selection of four columns since s ≥ 25 s \ge25 s ≥ 25 Lemma 3.1 then excludes every edge outside K = [ 4 s + 3 ] K = [4s + 3] K = [ 4 s + 3 ] ∣ F ∣ = ( ∣ K ∣ 4 ) |\mathcal{F}| = \binom{|K|}{4} ∣ F ∣ = ( 4 ∣ K ∣ ) K K K
For a general shifted ONE family in the stated domain, Lemma 4.28 gives
n ≤ a s − 1 ≤ N s = ⌊ 9 s + 5 2 ⌋ . n \le a_s - 1 \le N_s = \left\lfloor\frac{9s + 5}{2} \right\rfloor. n ≤ a s − 1 ≤ N s = ⌊ 2 9 s + 5 ⌋ . Add isolated vertices up to N s N_s N s G ⊇ F \mathcal{G} \supseteq\mathcal{F} G ⊇ F § 3.1 . The matching avoiding vertex 1 persists, so G \mathcal{G} G q ∗ = ⌊ ( s − 1 ) / 2 ⌋ ≥ 2 q_* = \lfloor(s - 1)/2 \rfloor\ge2 q ∗ = ⌊( s − 1 ) /2 ⌋ ≥ 2 Theorem 4.26 gives ∣ G ∣ ≤ A 4 ( s ) = ∣ F ∣ |\mathcal{G}| \le A_4(s) = |\mathcal{F}| ∣ G ∣ ≤ A 4 ( s ) = ∣ F ∣ F \mathcal{F} F q = 1 q = 1 q = 1
This equality statement uses the strict anchor, while the constants 71, 143 retain the stronger hypotheses of Theorem 5.3 .
Lemma 5.5 (Inverting a shift at a complete clique). Let s ≥ 2 s \ge2 s ≥ 2 ∣ T ∣ = 4 s + 3 |T| = 4s + 3 ∣ T ∣ = 4 s + 3 ν ( H ) ≤ s \nu(\mathcal{H}) \le s ν ( H ) ≤ s S i j ( H ) = ( T 4 ) S_{ij}(\mathcal{H}) = \binom{T}{4} S ij ( H ) = ( 4 T ) H \mathcal{H} H 4 s + 3 4s + 3 4 s + 3
Proof. A shift preserves the number of edges in each i / j i/j i / j i , j i,j i , j T T T j ∈ T j \in T j ∈ T i ∉ T i \notin T i ∈ / T S i j S_{ij} S ij i ∈ T i \in T i ∈ T j ∉ T j \notin T j ∈ / T R = T ∖ { i } R = T \setminus\{i\} R = T ∖ { i } ∣ R ∣ = 4 s + 2 ≥ 10 |R| = 4s + 2 \ge10 ∣ R ∣ = 4 s + 2 ≥ 10 R R R U ⊂ R U \subset R U ⊂ R { i } ∪ U \{i\} \cup U { i } ∪ U { j } ∪ U \{j\} \cup U { j } ∪ U U , V U,V U , V U ∪ V U \cup V U ∪ V 4 s − 4 4s - 4 4 s − 4 R R R s − 1 s - 1 s − 1
Corollary 5.6 (Arbitrary extremizers strictly below the crossing). For s ≥ 25 s \ge25 s ≥ 25 4 s + 4 ≤ n < a s 4s + 4 \le n < a_s 4 s + 4 ≤ n < a s ν ( F ) ≤ s \nu(\mathcal{F}) \le s ν ( F ) ≤ s ∣ F ∣ = A 4 ( s ) |\mathcal{F}| = A_4(s) ∣ F ∣ = A 4 ( s ) F \mathcal{F} F 4 s + 3 4s + 3 4 s + 3
Proof. Shift an extremal family to F ′ \mathcal{F}' F ′ s s s s s s Theorem 1.1 . A missing edge exists since n ≥ 4 s + 4 n \ge4s + 4 n ≥ 4 s + 4 M ( n − 1 , s − 1 ) M(n - 1,s - 1) M ( n − 1 , s − 1 ) B 4 ( n , s ) < A 4 ( s ) B_4(n,s) < A_4(s) B 4 ( n , s ) < A 4 ( s ) Lemma 4.28 gives n − 1 ≤ ( 9 s + 3 ) / 2 ≤ 5 s − 2 n - 1 \le(9s + 3)/2 \le5s - 2 n − 1 ≤ ( 9 s + 3 ) /2 ≤ 5 s − 2 Lemma 2.3 therefore gives A 4 ( s − 1 ) + ( n − 1 3 ) < A 4 ( s ) A_4(s - 1) + \binom{n-1}{3} < A_4(s) A 4 ( s − 1 ) + ( 3 n − 1 ) < A 4 ( s ) F ′ \mathcal{F}' F ′ ( [ 4 s + 3 ] 4 ) \binom{[4s+3]}{4} ( 4 [ 4 s + 3 ] ) Lemma 5.5 ; every intermediate family has matching number at most s s s
Cover uniqueness near the crossing
Lemma 5.7 (ONE cannot attain the upper cover). A shifted ONE family with matching number s s s B 4 ( n , s ) B_4(n,s) B 4 ( n , s ) 5 ≤ s ≤ 121 5 \le s \le121 5 ≤ s ≤ 121 n ≥ a s n \ge a_s n ≥ a s s ≥ 122 s \ge122 s ≥ 122 n ≥ a s + 1 n \ge a_s + 1 n ≥ a s + 1
Proof. The first range is Proposition 5.1 . For s ≥ 122 s \ge122 s ≥ 122 n > a s n > a_s n > a s [ a s ] [a_s] [ a s ]
Proposition 4.1 , after saturation, bounds this ONE restriction by A 4 ( s ) A_4(s) A 4 ( s ) B 4 ( a s , s ) > A 4 ( s ) B_4(a_s,s)>A_4(s) B 4 ( a s , s ) > A 4 ( s ) Theorem 5.3 identifies the restriction as the complete clique on K = [ 4 s + 3 ] K=[4s+3] K = [ 4 s + 3 ] K K K 4 s 4s 4 s K K K B 4 ( n , s ) B_4(n,s) B 4 ( n , s ) n n n
Lemma 5.8 (Inverting a shift at a complete cover). Let t ≥ 2 t\ge2 t ≥ 2 n ≥ 4 t + 4 n\ge4t+4 n ≥ 4 t + 4 ν ( F ) ≤ t \nu(\mathcal{F})\le t ν ( F ) ≤ t S i j S_{ij} S ij j j j i < j i<j i < j F \mathcal{F} F C T C_T C T t t t T T T F \mathcal{F} F t t t
Proof. A shift preserves the number of edges in each i / j i/j i / j i , j i,j i , j T T T F = C T \mathcal{F}=C_T F = C T j ∈ T , i ∉ T j\in T,i\notin T j ∈ T , i ∈ / T S i j S_{ij} S ij
Suppose i ∈ T , j ∉ T i\in T,j\notin T i ∈ T , j ∈ / T K = T ∖ { i } K=T\setminus\{i\} K = T ∖ { i } W = [ n ] ∖ ( K ∪ { i , j } ) W=[n]\setminus(K\cup\{i,j\}) W = [ n ] ∖ ( K ∪ { i , j }) m = ∣ W ∣ = n − t − 1 ≥ 3 t + 3 ≥ 9 m=|W|=n-t-1\ge3t+3\ge9 m = ∣ W ∣ = n − t − 1 ≥ 3 t + 3 ≥ 9 K K K F \mathcal{F} F U ∈ ( W 3 ) U\in\binom{W}{3} U ∈ ( 3 W ) { i } ∪ U \{i\}\cup U { i } ∪ U { j } ∪ U \{j\}\cup U { j } ∪ U F \mathcal{F} F m ≥ 9 m\ge9 m ≥ 9 t − 1 t-1 t − 1 K K K 3 ( t − 1 ) 3(t-1) 3 ( t − 1 ) W W W m − 6 ≥ 3 ( t − 1 ) m-6\ge3(t-1) m − 6 ≥ 3 ( t − 1 ) F \mathcal{F} F C K ∪ { i } C_{K\cup\{i\}} C K ∪ { i } C K ∪ { j } C_{K\cup\{j\}} C K ∪ { j }
Theorem 5.9 (Complete covers in an explicit finite domain). Let ν ( F ) ≤ s \nu(\mathcal{F})\le s ν ( F ) ≤ s ∣ F ∣ = B 4 ( n , s ) |\mathcal{F}|=B_4(n,s) ∣ F ∣ = B 4 ( n , s ) F \mathcal{F} F s s s
s = 5 , n ≥ 33 , s = 6 , n ≥ 34 , 7 ≤ s ≤ 121 , n ≥ a s , s ≥ 122 , n ≥ a s + 1. \begin{aligned}
s&=5, & n&\ge33,\\
s&=6, & n&\ge34,\\
7\le s&\le121, & n&\ge a_s,\\
s&\ge122, & n&\ge a_s+1.
\end{aligned} s s 7 ≤ s s = 5 , = 6 , ≤ 121 , ≥ 122 , n n n n ≥ 33 , ≥ 34 , ≥ a s , ≥ a s + 1. This conclusion additionally uses Frankl’s cover-uniqueness theorem [3 Theorem 1.1] to start at s = 4 s=4 s = 4 n ≥ 32 n\ge32 n ≥ 32
Proof. First a s ≥ a s − 1 + 1 a_s\ge a_{s-1}+1 a s ≥ a s − 1 + 1 s ≥ 2 s\ge2 s ≥ 2 (3) , a s ≤ 5 s + 4 a_s\le5s+4 a s ≤ 5 s + 4 u = s − 2 ≥ 0 u=s-2\ge0 u = s − 2 ≥ 0
24 [ A 4 ( s ) − A 4 ( s − 1 ) − ( 5 s + 3 3 ) ] = 216 + 2356 u + 2160 u 2 + 524 u 3 > 0. 24\left[A_4(s)-A_4(s-1)-\binom{5s+3}{3}\right]=216+2356u+2160u^2+524u^3>0. 24 [ A 4 ( s ) − A 4 ( s − 1 ) − ( 3 5 s + 3 ) ] = 216 + 2356 u + 2160 u 2 + 524 u 3 > 0. Consequently Pascal’s identity implies
B 4 ( a s − 1 , s − 1 ) = B 4 ( a s , s ) − ( a s − 1 3 ) > A 4 ( s − 1 ) . B_4(a_s-1,s-1)=B_4(a_s,s)-\binom{a_s-1}{3}>A_4(s-1). B 4 ( a s − 1 , s − 1 ) = B 4 ( a s , s ) − ( 3 a s − 1 ) > A 4 ( s − 1 ) . This parameter is admissible, so the crossing claim follows.
Frankl’s theorem states cover uniqueness for exact matching u u u n ≥ 7 u + 4 n\ge7u+4 n ≥ 7 u + 4 s = 4 s=4 s = 4 n ≥ 32 n\ge32 n ≥ 32 u ≤ 4 u\le4 u ≤ 4 u < 4 u<4 u < 4 B 4 ( n , u ) < B 4 ( n , 4 ) B_4(n,u)<B_4(n,4) B 4 ( n , u ) < B 4 ( n , 4 ) e 4 = 32 e_4=32 e 4 = 32
e s = { max { e s − 1 + 1 , a s } , 5 ≤ s ≤ 121 , max { e s − 1 + 1 , a s + 1 } , s ≥ 122. e_s=
\begin{cases}
\max\{e_{s-1}+1,a_s\}, & 5\le s\le121,\\
\max\{e_{s-1}+1,a_s+1\}, & s\ge122.
\end{cases} e s = { max { e s − 1 + 1 , a s } , max { e s − 1 + 1 , a s + 1 } , 5 ≤ s ≤ 121 , s ≥ 122. The crossings a 5 = 26 , a 6 = 31 , a 7 = 35 a_5=26,a_6=31,a_7=35 a 5 = 26 , a 6 = 31 , a 7 = 35 e 5 = 33 , e 6 = 34 , e 7 = a 7 e_5=33,e_6=34,e_7=a_7 e 5 = 33 , e 6 = 34 , e 7 = a 7
Induct on s s s n ≥ e s n \ge e_s n ≥ e s s s s Lemma 5.7 rules out ONE, so deleting vertex 1 leaves a family F 0 \mathcal{F}_0 F 0 s − 1 s-1 s − 1 n − 1 ≥ e s − 1 n-1 \ge e_{s-1} n − 1 ≥ e s − 1
B 4 ( n , s ) − ∣ F ∣ = [ B 4 ( n − 1 , s − 1 ) − ∣ F 0 ∣ ] + [ ( n − 1 3 ) − deg F ( 1 ) ] . B_4(n,s)-|\mathcal{F}|=\left[B_4(n-1,s-1)-|\mathcal{F}_0|\right]+\left[\binom{n-1}{3}-\deg_{\mathcal{F}}(1)\right]. B 4 ( n , s ) − ∣ F ∣ = [ B 4 ( n − 1 , s − 1 ) − ∣ F 0 ∣ ] + [ ( 3 n − 1 ) − deg F ( 1 ) ] . Equality forces a complete ( s − 1 ) (s-1) ( s − 1 ) s s s Lemma 5.8 inverts each shift in the original family; its domain s ≥ 2 s \ge2 s ≥ 2 n ≥ 4 s + 4 n \ge4s+4 n ≥ 4 s + 4
These exact-equality conclusions do not imply quantitative stability for arbitrary families. The crossing itself for s ≥ 122 s \ge122 s ≥ 122
Two elementary applications
These consequences illustrate the cardinality theorem. The probabilistic limit already follows from HHL’s large-s s s [14 Conjecture 1.1 and Lemma 3.2] . It is not a new consequence made possible by the small cases.
Corollary 6.1 (Finite weights and four i.i.d. variables). For nonnegative weights w 1 , … , w n w_1,\ldots,w_n w 1 , … , w n s = ⌊ ∑ i w i ⌋ s=\lfloor\sum_i w_i\rfloor s = ⌊ ∑ i w i ⌋ s ≥ 1 s\ge1 s ≥ 1 n ≥ 4 s + 4 n\ge4s+4 n ≥ 4 s + 4 M ( n , s ) M(n,s) M ( n , s ) s = 0 s=0 s = 0
For independent, identically distributed nonnegative X 1 , … , X 4 X_1,\ldots,X_4 X 1 , … , X 4 x x x
sup Pr ( X 1 + X 2 + X 3 + X 4 ≥ 1 ) = { max { 1 − ( 1 − x ) 4 , ( 4 x ) 4 } , 0 ≤ x ≤ 1 / 4 , 1 , x ≥ 1 / 4. \sup\Pr(X_1+X_2+X_3+X_4\ge1)=
\begin{cases}
\max\{1-(1-x)^4,(4x)^4\}, & 0\le x\le1/4,\\
1, & x\ge1/4.
\end{cases} sup Pr ( X 1 + X 2 + X 3 + X 4 ≥ 1 ) = { max { 1 − ( 1 − x ) 4 , ( 4 x ) 4 } , 1 , 0 ≤ x ≤ 1/4 , x ≥ 1/4. No classification of all optimizing laws is asserted.
Proof. The weighted four-subsets form a family in which every matching has size at most the total weight, proving the finite assertion.
For the limit, truncating a variable at 1 preserves the event and can only lower its mean. Fix 0 < x < 1 / 4 0<x<1/4 0 < x < 1/4 0 < ε < 1 / 4 − x 0<\varepsilon<1/4-x 0 < ε < 1/4 − x N N N x + ε x+\varepsilon x + ε Theorem 1.1 with s N = ⌊ N ( x + ε ) ⌋ s_N=\lfloor N(x+\varepsilon)\rfloor s N = ⌊ N ( x + ε )⌋ N ≥ 4 s N + 4 N\ge4s_N+4 N ≥ 4 s N + 4 s N ≥ 1 s_N\ge1 s N ≥ 1 N N N 1 / 4 1/4 1/4
Pr ( X 1 + ⋯ + X 4 ≥ 1 ) ≤ M ( N , s N ) ( N 4 ) + 1 4 N ε 2 . \Pr(X_1+\cdots+X_4\ge1)\le\frac{M(N,s_N)}{\binom{N}{4}}+\frac{1}{4N\varepsilon^2}. Pr ( X 1 + ⋯ + X 4 ≥ 1 ) ≤ ( 4 N ) M ( N , s N ) + 4 N ε 2 1 . Let N → ∞ N\to\infty N → ∞ ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 ( 1 − x ) δ 0 + x δ 1 (1-x)\delta_0+x\delta_1 ( 1 − x ) δ 0 + x δ 1 ( 1 − 4 x ) δ 0 + 4 x δ 1 / 4 (1-4x)\delta_0+4x\delta_{1/4} ( 1 − 4 x ) δ 0 + 4 x δ 1/4 x > 1 / 4 x>1/4 x > 1/4 s N → ∞ s_N\to\infty s N → ∞ s N ≥ 6961 s_N\ge6961 s N ≥ 6961
Corollary 6.2 (An explicit supersaturation bound). Let s > 1 s>1 s > 1 n ≥ m ≥ 4 ( s + 1 ) n\ge m\ge4(s+1) n ≥ m ≥ 4 ( s + 1 ) L s + 1 ( F ) L_{s+1}(\mathcal{F}) L s + 1 ( F ) s + 1 s+1 s + 1 F ⊆ ( [ n ] 4 ) \mathcal{F}\subseteq\binom{[n]}{4} F ⊆ ( 4 [ n ] )
L s + 1 ( F ) ≥ max { 0 , ⌈ ∣ F ∣ ( n − 4 m − 4 ) − M ( m , s ) ( n m ) ( n − 4 ( s + 1 ) m − 4 ( s + 1 ) ) ⌉ } . L_{s+1}(\mathcal{F})\ge\max\left\{0,\left\lceil\frac{|\mathcal{F}|\binom{n-4}{m-4}-M(m,s)\binom{n}{m}}{\binom{n-4(s+1)}{m-4(s+1)}}\right\rceil\right\}. L s + 1 ( F ) ≥ max { 0 , ⌈ ( m − 4 ( s + 1 ) n − 4 ( s + 1 ) ) ∣ F ∣ ( m − 4 n − 4 ) − M ( m , s ) ( m n ) ⌉ } . One may maximize over the integer choices of m m m
Proof. For each m m m V V V F [ V ] \mathcal{F}[V] F [ V ] L s + 1 ( F [ V ] ) L_{s+1}(\mathcal{F}[V]) L s + 1 ( F [ V ]) s s s Theorem 1.1 gives L s + 1 ( F [ V ] ) ≥ ∣ F [ V ] ∣ − M ( m , s ) L_{s+1}(\mathcal{F}[V]) \ge|\mathcal{F}[V]|-M(m,s) L s + 1 ( F [ V ]) ≥ ∣ F [ V ] ∣ − M ( m , s ) V V V ( n − 4 m − 4 ) \binom{n-4}{m-4} ( m − 4 n − 4 ) ( n − 4 ( s + 1 ) m − 4 ( s + 1 ) ) \binom{n-4(s+1)}{m-4(s+1)} ( m − 4 ( s + 1 ) n − 4 ( s + 1 ) )
For example, n = 30 n=30 n = 30 s = 2 s=2 s = 2 ∣ F ∣ = 15000 |\mathcal{F}|=15000 ∣ F ∣ = 15000 m = 13 m=13 m = 13
Comparison with earlier results
Cardinality and the finite-board method
Table 2 separates the ranges of the principal antecedents. The theorem locators refer to the identified preprint versions where the published text has not been checked in full.
Table 2 (PDF p. 37). Statement-level comparison. Asymptotic constants and restricted family classes are not interchangeable with explicit finite thresholds. The table does not establish an exhaustive priority claim.
Frankl’s later author copy [13 Section 13, Theorem 13.2] also announces the four-uniform conjecture for sufficiently large matching number, with a proof deferred to future work. That announcement is an antecedent distinct from a proof supplied in that text and from the all-parameter conclusion here. The direct-deletion and ONE reductions are attributed at their use; the polynomial proof in Lemma 2.3 is retained for its explicit strict inequality. The withdrawn complete-solution claim [16 ] is not a theorem input; its withdrawal does not determine another work’s priority.
Our finite certificates couple the selected-residual constraints with actual local order, integer orbit counts, support costs and rectangle persistence. The exact-trace and selected-residual mechanisms follow [12 Sections 2 and 4] . The support census, support maxima and residual-row method likewise have HHL antecedents. HHL’s C3 gives the rectangle cap 96/4 through 66 missing points; Lemma 4.18 extends it to 75 under its displayed premises. Neither averaging nor orbit-count integrality is proposed as a new general principle.
Clique-side structure
Guo–Lu [2 Theorem 1.3 and Corollary 1.5, arXiv v1] work for k ≥ 3 k \ge3 k ≥ 3 s s s k s + k ≤ n ≤ ( 1 + β ) k s + k − 2 ks+k \le n \le(1+\beta)ks+k-2 k s + k ≤ n ≤ ( 1 + β ) k s + k − 2 β > 0 \beta>0 β > 0 k k k ν ≤ s \nu\le s ν ≤ s k s + k − 1 ks+k-1 k s + k − 1 Theorem 5.3 instead gives a linear deficit bound with constants 71, 143 and cutoff s ≥ 122 s \ge122 s ≥ 122
Local stability and weighted graphs
The section and shadow decomposition follows Frankl [3 Sections 3–5] . Nested weighted section estimates and canonical diversity have established antecedents [5 Section 8] . The finite variance is imported from that paper; its Theorem 32 already gives the asymptotic coefficient 5.74 in uniformity four. Proposition A.10 supplies an explicit cutoff using the inequalities displayed here. Wang [7 Lemmas 2.1–2.2, 3.2 and proof of Theorem 1.2] provides the graph compression and the container/convexity antecedent. For the signed functional K 3 − λ e K_3-\lambda e K 3 − λ e Lemma A.8 is therefore retained.
A direct stability comparison is Frankl–Lu–Ma–Wu [10 Definition 1.4 and Theorem 1.5] . For fixed c 0 ∈ ( 0 , 1 / 5 ) c_0 \in(0,1/5) c 0 ∈ ( 0 , 1/5 ) ε > 0 \varepsilon> 0 ε > 0 c 0 c_0 c 0 n ≥ n 0 ( ε , c 0 ) n \ge n_0(\varepsilon,c_0) n ≥ n 0 ( ε , c 0 ) c 0 n ≤ t ≤ n / 5 c_0n \le t \le n/5 c 0 n ≤ t ≤ n /5 ν ( F ) ≤ t \nu(\mathcal{F}) \le t ν ( F ) ≤ t
d t ( F ) ≤ ε n 4 ⟹ ∣ C t ∖ F ∣ < 400 ε 1 / 4 n 4 d_t(\mathcal{F}) \le\varepsilon n^4 \quad\Longrightarrow\quad|\mathcal{C}_t \setminus\mathcal{F}| < 400\varepsilon^{1/4}n^4 d t ( F ) ≤ ε n 4 ⟹ ∣ C t ∖ F ∣ < 400 ε 1/4 n 4 Their distance is asymmetric. Our conclusions instead give ∣ C t ∖ F ∣ ≤ ( K + 1 ) d t ( F ) |\mathcal{C}_t \setminus\mathcal{F}| \le(K+1)d_t(\mathcal{F}) ∣ C t ∖ F ∣ ≤ ( K + 1 ) d t ( F ) K K K ε \varepsilon ε n n n n 0 = 10 107 n_0=10^{107} n 0 = 1 0 107 n ≥ 5 t n \ge5t n ≥ 5 t ε \varepsilon ε c 0 c_0 c 0
Cao–Liu–Zhang [11 Theorem 1.4] prove stability for arbitrary families in every compact subinterval of 0 < t / n ≤ 1 / 5 0 < t/n \le1/5 0 < t / n ≤ 1/5 n n n t ≥ t 0 ( 4 ) t \ge t_0(4) t ≥ t 0 ( 4 ) n ≥ 5 t n \ge5t n ≥ 5 t k + 0.6 k+0.6 k + 0.6 k ≥ 5 k \ge5 k ≥ 5
Frankl’s uniqueness statement at n ≥ 7 t + 4 n \ge7t+4 n ≥ 7 t + 4 [3 Theorem 1.1] and the finite hypothesis of Frankl–Kupavskii [8 Theorem 3] , which here requires n ≥ 12 t + 8 n \ge12t+8 n ≥ 12 t + 8 [9 Section 7, Theorem 28] has a sufficiently-large-n n n
The compatibility argument in Section A.6 averages constraints from all submatchings of one matching, then uses the same deficit to bound every later link. The density-adapted centre in Lemma A.13 preserves the two-endpoint proof while sharpening the bound. These two ingredients account for the smaller finite bases, including the additional points (2904, 15676), (888, 4798), (360, 1950), (72, 395), and, with the one-sided variance and all-weight graph bound, (49, 269). The first-deficit example has a nonempty tail of nonpositive weight; it does not establish sharpness for a positive tail. The constants and cutoffs are sufficient, not optimal. Proposition A.15 extends shifted stability above a base with a growing coefficient by monotonicity of the deficit and double counting. It is an elementary consequence of the base theorem; no priority is claimed for this propagation principle. Quantitative transfer through arbitrary shifts would require additional arguments.
Computational specifications and reproducibility
Verification command and scope
The computational supplement has one verification entry point:
python -X utf8 -S -B scripts/verify.py
--hhl-bundle EMC_certificate.zip --zig PATH_TO_ZIG
--node PATH_TO_NODE --output build/checkThe displayed lines form one command, run from the repository root. It uses standard-library Python 3.12 or later, Zig 0.16.0 and Node 24. The dependencies and hash-pinned HHL archive are supplied before the offline verification. No optimization solver is needed to check the certificates.
The default command verifies every computational component of this article. It recompiles and executes C1 and all seven consumed C2 cases, checks the support and layer inequalities, verifies the four small points, the 51 endpoint records and two fixed inequalities used for cardinality, and checks their polynomial propagation. It also verifies all 88 endpoint records retained for the structural results and the stronger stability weights. It extracts the 68 strict upper margins and then verifies the seven computational components of Appendix § 9 , including their stability normalizations. Complete success emits
PASS_ALL_ARTICLE_COMPUTATIONS.Missing or changed inputs, failed processes, incomplete coverage, malformed output and timeouts prevent this marker. The new output directory contains a receipt, complete process logs and the exact endpoint bounds. Failure controls are supplied in tests/.
The rational checkers reconstruct the labelled universes, transports and row bounds. Multiplier rounding occurs only after the full global multiplicity is applied. Certificates are compressed JSON files grouped by cases and lemmas in certificates/; their mathematical formats are documented there. Verification code is in emc4/. The 37 other ordinary upper records remain distributed to check the structural gap claims, including all 68 upper gaps for 5 ≤ s ≤ 72 5 \le s \le72 5 ≤ s ≤ 72 73 ≤ s ≤ 121 73 \le s \le121 73 ≤ s ≤ 121 Lemma 5.2 . Thus the 53-obligation count describes the intermediate cardinality argument, not the number of computations in the complete article.
The root REPRODUCE.md gives dependencies, commands, expected results and instructions for rebuilding the paper.
The option --scope global restricts verification to Table 3 and these structural gap and weight checks, and reports PASS_GLOBAL_COMPUTATIONS. The option --scope appendices runs the additional computations below using Python alone and reports PASS_APPENDIX_COMPUTATIONS. Both restricted modes explicitly report that the whole article has not been checked.
Table 3. Computations needed by the global cardinality proof. Exact row arithmetic is separated from the mathematical proof that every actual configuration satisfies those rows.
Additional computations in the appendices
The local estimates do not serve as inputs to Theorem 1.1 . Their computational groups are:
Table 1 (PDF p. 40).
The moment checks reconstruct all specified cuts and intervals, then substitute the strict margins into the stability formula. The uniform result is checked through coefficient signs rather than a sample of parameter values.
Replaying C1/C2 relies on the correctness of the credited implementations. The trace reductions, necessity of the constraints, graph inequalities, shifting arguments and induction are proved in this paper. Their mathematical validity is not a conclusion of a software success marker.
Authorship, assistance and materials
The author directed the research programme and selected its scope. AI systems were used extensively to explore proof approaches, propose lemmas and counterchecks, generate certificate and verification code, draft and revise text, and conduct adversarial reviews. Additional AI-assisted calculations supplied by the author were checked against the proofs and exact computations. They include the common-board polynomial propagation, the two fixed inequalities, and the direct dense support constructions incorporated here. This assistance includes scientific and computational work, not only language editing. Agent reviews are not independent specialist acceptance; the proofs and identified computations carry the justification.
The computational supplement consists of verification programs, exact certificates, documented expected results and file hashes. HHL methods and programs retain their attribution; the pinned external archive and its applicable terms are specified separately in the supplement. The supplement contains the source and PDF of this article together with instructions for rebuilding the paper and reproducing the computations.
Effective shifted stability and weighted graph bounds
This appendix preserves the local results and their proofs as a complement to Theorem 1.1 . They do not use finite HHL board certificates, and the global proof does not use their estimates. Here t t t
Statements and proof route
For a family F ⊆ ( [ n ] 4 ) \mathcal{F} \subseteq\binom{[n]}{4} F ⊆ ( 4 [ n ] ) t t t
d t ( F ) = B 4 ( n , t ) − ∣ F ∣ , γ t ( F ) = min S ⊆ [ n ] ∣ S ∣ = t ∣ { E ∈ F : E ∩ S = ∅ } ∣ . d_t(\mathcal{F}) = B_4(n,t) - |\mathcal{F}|,\qquad\gamma_t(\mathcal{F}) = \min_{\substack{S \subseteq[n]\\ |S|=t}} |\{E \in\mathcal{F}: E \cap S = \varnothing\}|. d t ( F ) = B 4 ( n , t ) − ∣ F ∣ , γ t ( F ) = S ⊆ [ n ] ∣ S ∣ = t min ∣ { E ∈ F : E ∩ S = ∅ } ∣. For shifted families, [ t ] [t] [ t ]
Theorem A.1 (Effective shifted stability). Let t ≥ 2200 t \ge2200 t ≥ 2200 n = ⌈ 287 t / 50 ⌉ n = \lceil287t/50\rceil n = ⌈ 287 t /50 ⌉ F ⊆ ( [ n ] 4 ) \mathcal{F} \subseteq\binom{[n]}{4} F ⊆ ( 4 [ n ] ) ν ( F ) ≤ t \nu(\mathcal{F}) \le t ν ( F ) ≤ t d = d t ( F ) ≥ 0 d = d_t(\mathcal{F}) \ge0 d = d t ( F ) ≥ 0
γ t ( F ) = ∣ F ∖ C t ∣ ≤ 2285 d , ∣ F △ C t ∣ ≤ 4571 d . \gamma_t(\mathcal{F}) = |\mathcal{F} \setminus\mathcal{C}_t| \le2285d,\qquad|\mathcal{F} \mathbin{\triangle} \mathcal{C}_t| \le4571d. γ t ( F ) = ∣ F ∖ C t ∣ ≤ 2285 d , ∣ F △ C t ∣ ≤ 4571 d . A more detailed estimate is useful when the number of vertices is reduced. A matching in a tail link forces missing head triples on every residual set obtained by selecting some of its pairs. Averaging these constraints and adapting the moment centre produces the next finite refinement.
Theorem A.2 (Smaller finite bases). Let ( t , n , K ) (t,n,K) ( t , n , K )
( t , n , K ) ∈ { ( 49 , 269 , 160 ) , ( 72 , 395 , 148 ) , ( 360 , 1950 , 319 ) , ( 888 , 4798 , 601 ) , ( 2904 , 15676 , 1427 ) } , (t,n,K) \in\{(49,269,160),(72,395,148),(360,1950,319),
(888,4798,601),(2904,15676,1427)\}, ( t , n , K ) ∈ {( 49 , 269 , 160 ) , ( 72 , 395 , 148 ) , ( 360 , 1950 , 319 ) , ( 888 , 4798 , 601 ) , ( 2904 , 15676 , 1427 )} , ( n , K ) = ( t + 15301 , 4692 ) ( 3229 ≤ t ≤ 3480 ) . (n,K) = (t+15301,4692)\qquad(3229 \le t \le3480). ( n , K ) = ( t + 15301 , 4692 ) ( 3229 ≤ t ≤ 3480 ) . Every shifted F ⊆ ( [ n ] 4 ) \mathcal{F} \subseteq\binom{[n]}{4} F ⊆ ( 4 [ n ] ) ν ( F ) ≤ t \nu(\mathcal{F}) \le t ν ( F ) ≤ t d = d t ( F ) ≥ 0 d=d_t(\mathcal{F}) \ge0 d = d t ( F ) ≥ 0
γ t ( F ) = ∣ F ∖ C t ∣ ≤ K d , ∣ F △ C t ∣ ≤ ( 1 + 2 K ) d . \gamma_t(\mathcal{F}) = |\mathcal{F} \setminus\mathcal{C}_t| \le Kd,\qquad|\mathcal{F} \mathbin{\triangle} \mathcal{C}_t| \le(1+2K)d. γ t ( F ) = ∣ F ∖ C t ∣ ≤ K d , ∣ F △ C t ∣ ≤ ( 1 + 2 K ) d . The 252 bases in the interval have between 5 and 1195 fewer vertices than ⌈ 287 t / 50 ⌉ \lceil287t/50\rceil ⌈ 287 t /50 ⌉ t = 2904 t=2904 t = 2904 t = 888 t=888 t = 888 t = 360 t=360 t = 360 t = 72 t=72 t = 72 t = 49 t=49 t = 49 t t t t = 49 t=49 t = 49 d = 0 d=0 d = 0
Corollary A.3 (Exact extremizers above the bases). Suppose t ≥ 2200 t \ge2200 t ≥ 2200 n ≥ ⌈ 287 t / 50 ⌉ n \ge\lceil287t/50\rceil n ≥ ⌈ 287 t /50 ⌉ 3229 ≤ t ≤ 3480 3229 \le t \le3480 3229 ≤ t ≤ 3480 n ≥ t + 15301 n \ge t+15301 n ≥ t + 15301 t = 2904 t=2904 t = 2904 n ≥ 15676 n \ge15676 n ≥ 15676 t = 888 t=888 t = 888 n ≥ 4798 n \ge4798 n ≥ 4798 t = 360 t=360 t = 360 n ≥ 1950 n \ge1950 n ≥ 1950 t = 72 t=72 t = 72 n ≥ 395 n \ge395 n ≥ 395 t = 49 t=49 t = 49 n ≥ 269 n \ge269 n ≥ 269 F ⊆ ( [ n ] 4 ) \mathcal{F} \subseteq\binom{[n]}{4} F ⊆ ( 4 [ n ] ) ν ( F ) ≤ t \nu(\mathcal{F}) \le t ν ( F ) ≤ t ∣ F ∣ ≤ B 4 ( n , t ) |\mathcal{F}| \le B_4(n,t) ∣ F ∣ ≤ B 4 ( n , t ) F = C T ( n ) \mathcal{F} = \mathcal{C}_T(n) F = C T ( n ) t t t T T T
Corollary A.4 (Shifted stability above a base). Let ( a , K ) (a,K) ( a , K )
( a , K ) = ( ⌈ 287 t 50 ⌉ , 2285 ) ( t ≥ 2200 ) , ( a , K ) = ( t + 15301 , 4692 ) ( 3229 ≤ t ≤ 3480 ) , ( a , K ) = ( 15676 , 1427 ) ( t = 2904 ) , ( a , K ) = ( 4798 , 601 ) ( t = 888 ) , ( a , K ) = ( 1950 , 319 ) ( t = 360 ) , ( a , K ) = ( 395 , 148 ) ( t = 72 ) , ( a , K ) = ( 269 , 160 ) ( t = 49 ) . \begin{aligned}
(a,K)&=\left(\left\lceil\frac{287t}{50}\right\rceil,2285\right) &&(t\ge2200),\\
(a,K)&=(t+15301,4692) &&(3229\le t\le3480),\\
(a,K)&=(15676,1427) &&(t=2904),\\
(a,K)&=(4798,601) &&(t=888),\\
(a,K)&=(1950,319) &&(t=360),\\
(a,K)&=(395,148) &&(t=72),\\
(a,K)&=(269,160) &&(t=49).
\end{aligned} ( a , K ) ( a , K ) ( a , K ) ( a , K ) ( a , K ) ( a , K ) ( a , K ) = ( ⌈ 50 287 t ⌉ , 2285 ) = ( t + 15301 , 4692 ) = ( 15676 , 1427 ) = ( 4798 , 601 ) = ( 1950 , 319 ) = ( 395 , 148 ) = ( 269 , 160 ) ( t ≥ 2200 ) , ( 3229 ≤ t ≤ 3480 ) , ( t = 2904 ) , ( t = 888 ) , ( t = 360 ) , ( t = 72 ) , ( t = 49 ) . For every n ≥ a n\ge a n ≥ a F ⊆ ( [ n ] 4 ) \mathcal{F}\subseteq\binom{[n]}{4} F ⊆ ( 4 [ n ] ) ν ( F ) ≤ t \nu(\mathcal{F})\le t ν ( F ) ≤ t R = ( n − t 4 ) / ( a − t 4 ) R=\binom{n-t}{4}/\binom{a-t}{4} R = ( 4 n − t ) / ( 4 a − t )
d t ( F ) ≥ 0 , γ t ( F ) ≤ K R d t ( F ) , ∣ F △ C t ∣ ≤ ( 1 + 2 K R ) d t ( F ) . d_t(\mathcal{F})\ge0,\qquad\gamma_t(\mathcal{F})\le KRd_t(\mathcal{F}),\qquad|\mathcal{F}\mathbin{\triangle}\mathcal{C}_t|\le(1+2KR)d_t(\mathcal{F}). d t ( F ) ≥ 0 , γ t ( F ) ≤ K R d t ( F ) , ∣ F △ C t ∣ ≤ ( 1 + 2 K R ) d t ( F ) . Where several base pairs are available, their smallest applicable coefficient may be used. The loss is explicit: at fixed t t t ( n − t ) 4 (n-t)^4 ( n − t ) 4 t = 3480 t=3480 t = 3480 a = 18781 a=18781 a = 18781 n = 19000 n=19000 n = 19000 γ t ( F ) ≤ 4967 d t ( F ) \gamma_t(\mathcal{F})\le4967d_t(\mathcal{F}) γ t ( F ) ≤ 4967 d t ( F ) [3 ] and the finite variance estimate of Frankl–Kupavskii [5 ] . Sections A.4–A.5 prove the uniform estimate. Sections A.6–A.7 give the finite refinement and quantitative propagation; Section A.8 handles exact equality and inversion of shifts. The weighted graph Lemma A.8 determines an exact maximum for K 3 ( G ) − λ e ( G ) K_3(G)-\lambda e(G) K 3 ( G ) − λ e ( G )
Additional inputs for the local results
The shadow theorem was stated in § 2 . The following inputs are used only in this appendix.
Triple systems. Frankl–Rödl–Ruciński [4 Theorem 1] gives, for u ≥ 33 u\ge33 u ≥ 33 N ≥ 3 u + 3 N\ge3u+3 N ≥ 3 u + 3 u u u
∣ A ∣ ≤ max { ( 3 u + 2 3 ) , B 3 ( N , u ) } . |\mathcal{A}|\le\max\left\{\binom{3u+2}{3},B_3(N,u)\right\}. ∣ A ∣ ≤ max { ( 3 3 u + 2 ) , B 3 ( N , u ) } . To extend it to matching number at most u u u u u u
B 3 ( 4 u − 1 , u ) − ( 3 u + 2 3 ) = u ( 10 u 2 − 69 u + 5 ) 6 > 0 ( u ≥ 33 ) . B_3(4u-1,u)-\binom{3u+2}{3}=\frac{u(10u^2-69u+5)}{6}>0\qquad(u\ge33). B 3 ( 4 u − 1 , u ) − ( 3 3 u + 2 ) = 6 u ( 10 u 2 − 69 u + 5 ) > 0 ( u ≥ 33 ) . Indeed the numerator at u = 33 + x u=33+x u = 33 + x 10 x 3 + 921 x 2 + 28121 x + 284394 10x^3+921x^2+28121x+284394 10 x 3 + 921 x 2 + 28121 x + 284394 N N N
ν ( A ) ≤ u , u ≥ 33 , N ≥ 4 u − 1 ⟹ ∣ A ∣ ≤ B 3 ( N , u ) . (30) \nu(\mathcal{A})\le u,\qquad u\ge33,\qquad N\ge4u-1\quad\Longrightarrow\quad|\mathcal{A}|\le B_3(N,u). \tag*{(30)} ν ( A ) ≤ u , u ≥ 33 , N ≥ 4 u − 1 ⟹ ∣ A ∣ ≤ B 3 ( N , u ) . (30) For smaller residual ground sets we retain the full maximum in FRR.
Finite variance. For a uniformly random matching B \mathcal{B} B v v v [ m ] [m] [ m ] m ≥ 3 v m \ge3v m ≥ 3 v Z = ∣ A ∩ B ∣ Z = |\mathcal{A} \cap\mathcal{B}| Z = ∣ A ∩ B ∣ μ = v ∣ A ∣ / ( m 3 ) \mu= v|\mathcal{A}|/\binom{m}{3} μ = v ∣ A ∣/ ( 3 m ) [5 Lemma 10, Proposition 11 and equation (20)] is
Var Z ≤ 2 μ ( 1 − μ / v ) . (31) \operatorname{Var} Z \le2\mu(1-\mu/v). \tag*{(31)} Var Z ≤ 2 μ ( 1 − μ / v ) . (31) No asymptotic threshold from that paper is used in the proof.
Clique cap. The Lovász form of Kruskal–Katona, stated in [6 Theorem 1] , says that if ∣ A 0 ∣ = ( x 3 ) > 0 |\mathcal{A}_0| = \binom{x}{3} > 0 ∣ A 0 ∣ = ( 3 x ) > 0 x ≥ 3 x \ge3 x ≥ 3
K 4 ( A 0 ) ≤ ( x 4 ) = x − 3 4 ∣ A 0 ∣ . (32) K_4(\mathcal{A}_0) \le\binom{x}{4} = \frac{x-3}{4}|\mathcal{A}_0|. \tag*{(32)} K 4 ( A 0 ) ≤ ( 4 x ) = 4 x − 3 ∣ A 0 ∣. (32) Graph compression. For graphs, compression preserves the number of edges, does not increase the matching number and does not decrease the number of triangles [7 Lemmas 2.1–2.2] . Thus it does not decrease K 3 ( G ) − λ e ( G ) K_3(G)-\lambda e(G) K 3 ( G ) − λ e ( G )
Lemma A.5 (One-sided Kneser variance). Let m ≥ 6 m \ge6 m ≥ 6 v ≥ 1 v \ge1 v ≥ 1 3 v ≤ m 3v \le m 3 v ≤ m For any triple family A ⊆ ( [ m ] 3 ) \mathcal{A} \subseteq\binom{[m]}{3} A ⊆ ( 3 [ m ] ) and a uniformly random matching B \mathcal{B} B of v v v triples, put Z = ∣ A ∩ B ∣ Z = |\mathcal{A} \cap\mathcal{B}| Z = ∣ A ∩ B ∣ and μ = v ∣ A ∣ / ( m 3 ) \mu= v|\mathcal{A}|/\binom{m}{3} μ = v ∣ A ∣/ ( 3 m ) Then
Var Z ≤ ρ m , v μ ( 1 − μ / v ) , ρ m , v = 1 + 6 ( v − 1 ) ( m − 3 ) ( m − 4 ) . (33) \operatorname{Var} Z \le\rho_{m,v}\mu(1-\mu/v), \qquad\rho_{m,v}=1+\frac{6(v-1)}{(m-3)(m-4)}. \tag*{(33)} Var Z ≤ ρ m , v μ ( 1 − μ / v ) , ρ m , v = 1 + ( m − 3 ) ( m − 4 ) 6 ( v − 1 ) . (33) Proof. Give functions on ( [ m ] 3 ) \binom{[m]}{3} ( 3 [ m ] ) K K K d = ( m − 3 3 ) d=\binom{m-3}{3} d = ( 3 m − 3 ) g J ( T ) = 1 J ⊆ T g_J(T)=1_{J\subseteq T} g J ( T ) = 1 J ⊆ T V j V_j V j ∣ J ∣ = j |J|=j ∣ J ∣ = j V 0 V_0 V 0 V 3 V_3 V 3
( K g J ) ( T ) = ( m − 3 − j 3 − j ) 1 J ∩ T = ∅ = ( m − 3 − j 3 − j ) ∑ I ⊆ J ( − 1 ) ∣ I ∣ g I ( T ) . (Kg_J)(T)=\binom{m-3-j}{3-j}1_{J\cap T=\varnothing}=\binom{m-3-j}{3-j}\sum_{I\subseteq J}(-1)^{|I|}g_I(T). ( K g J ) ( T ) = ( 3 − j m − 3 − j ) 1 J ∩ T = ∅ = ( 3 − j m − 3 − j ) I ⊆ J ∑ ( − 1 ) ∣ I ∣ g I ( T ) . Thus K K K V j / V j − 1 V_j/V_{j-1} V j / V j − 1 ( − 1 ) j ( m − 3 − j 3 − j ) (-1)^j\binom{m-3-j}{3-j} ( − 1 ) j ( 3 − j m − 3 − j ) K K K − ( m − 4 2 ) -\binom{m-4}{2} − ( 2 m − 4 ) m − 5 m-5 m − 5 − 1 -1 − 1 m − 5 m-5 m − 5 f = 1 A − α f=1_{\mathcal{A}}-\alpha f = 1 A − α α = ∣ A ∣ / ( m 3 ) \alpha=|\mathcal{A}|/\binom{m}{3} α = ∣ A ∣/ ( 3 m )
⟨ f , K f ⟩ d ≤ m − 5 d α ( 1 − α ) . \frac{\langle f,Kf\rangle}{d}\le\frac{m-5}{d}\alpha(1-\alpha). d ⟨ f , K f ⟩ ≤ d m − 5 α ( 1 − α ) . Two distinct positions of a random matching are uniform disjoint triples. Adding the v v v v ( v − 1 ) v(v-1) v ( v − 1 )
Var Z ≤ v α ( 1 − α ) ( 1 + ( v − 1 ) m − 5 d ) , \operatorname{Var} Z\le v\alpha(1-\alpha)\left(1+(v-1)\frac{m-5}{d}\right), Var Z ≤ v α ( 1 − α ) ( 1 + ( v − 1 ) d m − 5 ) , which is (A.4). The case v = 1 v=1 v = 1
This uses the Kneser spectral method underlying [5 ] . For this upper bound the largest algebraic eigenvalue suffices; the larger absolute value of a negative eigenvalue need not be used. We retain (A.2) for the other numerical arguments and use (A.4) only where specified.
Sections and shifted completion
Recall the elementary shifted-completion Lemma 2.1 .
Fix t ≥ 1 t \ge1 t ≥ 1 n ≥ 4 t + 4 n \ge4t+4 n ≥ 4 t + 4 F \mathcal{F} F ν ( F ) = t \nu(\mathcal{F})=t ν ( F ) = t t t t [ t + 3 ] [t+3] [ t + 3 ] [ t − 1 ] [t-1] [ t − 1 ] { t , t + 1 , t + 2 , t + 3 } \{t,t+1,t+2,t+3\} { t , t + 1 , t + 2 , t + 3 }
X = [ t + 1 ] , Y = [ t + 2 , n ] , m = ∣ Y ∣ , c = t − ⌊ t + 1 4 ⌋ , X=[t+1],\quad Y=[t+2,n],\quad m=|Y|,\quad c=t-\left\lfloor\frac{t+1}{4}\right\rfloor, X = [ t + 1 ] , Y = [ t + 2 , n ] , m = ∣ Y ∣ , c = t − ⌊ 4 t + 1 ⌋ , H = F ∩ ( Y 4 ) , A i = { T ∈ ( Y 3 ) : T ∪ { i } ∈ F } , A = A t + 1 . \mathcal{H}=\mathcal{F}\cap\binom{Y}{4},\qquad\mathcal{A}_i=\left\{T\in\binom{Y}{3}:T\cup\{i\}\in\mathcal{F}\right\},\quad\mathcal{A}=\mathcal{A}_{t+1}. H = F ∩ ( 4 Y ) , A i = { T ∈ ( 3 Y ) : T ∪ { i } ∈ F } , A = A t + 1 . These sections meet X X X A 1 ⊇ ⋯ ⊇ A t + 1 \mathcal{A}_1\supseteq\cdots\supseteq\mathcal{A}_{t+1} A 1 ⊇ ⋯ ⊇ A t + 1 t + 1 t+1 t + 1 ν ( A ) ≤ t \nu(\mathcal{A})\le t ν ( A ) ≤ t X X X ν ( H ) ≤ c \nu(\mathcal{H})\le c ν ( H ) ≤ c ∂ H ⊆ A \partial\mathcal{H}\subseteq\mathcal{A} ∂ H ⊆ A
∣ H ∣ ≤ c ∣ A ∣ , ∣ H ∣ ≤ K 4 ( A ) . (34) |\mathcal{H}|\le c|\mathcal{A}|,\qquad|\mathcal{H}|\le K_4(\mathcal{A}). \tag*{(34)} ∣ H ∣ ≤ c ∣ A ∣ , ∣ H ∣ ≤ K 4 ( A ) . (34) All sections with at least two vertices in X X X [ t ] [t] [ t ]
∣ H ∣ + ∑ i = 1 t + 1 ∣ A i ∣ ≤ t ( m 3 ) . (35) |\mathcal{H}|+\sum_{i=1}^{t+1}|\mathcal{A}_i|\le t\binom{m}{3}. \tag*{(35)} ∣ H ∣ + i = 1 ∑ t + 1 ∣ A i ∣ ≤ t ( 3 m ) . (35) Lemma A.6 (Deficit and canonical diversity). For the sections above, put C = ( m 3 ) C=\binom{m}{3} C = ( 3 m ) d = B 4 ( n , t ) − ∣ F ∣ d=B_4(n,t)-|\mathcal{F}| d = B 4 ( n , t ) − ∣ F ∣
d ≥ t C − ∣ H ∣ − ∑ i = 1 t + 1 ∣ A i ∣ , γ t ( F ) = ∣ F ∖ C t ∣ = ∣ H ∣ + ∣ A ∣ ≤ ( c + 1 ) ∣ A ∣ . d\ge tC-|\mathcal{H}|-\sum_{i=1}^{t+1}|\mathcal{A}_i|,\qquad\gamma_t(\mathcal{F})=|\mathcal{F}\setminus\mathcal{C}_t|=|\mathcal{H}|+|\mathcal{A}|\le(c+1)|\mathcal{A}|. d ≥ tC − ∣ H ∣ − i = 1 ∑ t + 1 ∣ A i ∣ , γ t ( F ) = ∣ F ∖ C t ∣ = ∣ H ∣ + ∣ A ∣ ≤ ( c + 1 ) ∣ A ∣. Moreover, for every shifted family,
∣ C t ∖ F ∣ = d + ∣ F ∖ C t ∣ , ∣ F △ C t ∣ = d + 2 ∣ F ∖ C t ∣ . |\mathcal{C}_t\setminus\mathcal{F}|=d+|\mathcal{F}\setminus\mathcal{C}_t|,\qquad|\mathcal{F}\mathbin{\triangle}\mathcal{C}_t|=d+2|\mathcal{F}\setminus\mathcal{C}_t|. ∣ C t ∖ F ∣ = d + ∣ F ∖ C t ∣ , ∣ F △ C t ∣ = d + 2∣ F ∖ C t ∣. Proof. The cover has all t C tC tC X X X [ t ] [t] [ t ] X X X [ t ] [t] [ t ] [ t ] [t] [ t ] H \mathcal{H} H A = A t + 1 \mathcal{A}=\mathcal{A}_{t+1} A = A t + 1 [ t ] [t] [ t ] [ n ] ∖ S = { u 1 < ⋯ < u n − t } [n]\setminus S=\{u_1<\cdots<u_{n-t}\} [ n ] ∖ S = { u 1 < ⋯ < u n − t } u i ≤ t + i u_i\le t+i u i ≤ t + i t + i ↦ u i t+i\mapsto u_i t + i ↦ u i [ t ] [t] [ t ] S S S
Lemma A.7 (Nested incidence). On a matching of v v v d 1 ≥ ⋯ ≥ d t + 1 = z d_1\ge\cdots\ge d_{t+1}=z d 1 ≥ ⋯ ≥ d t + 1 = z w w w j ∈ [ z , t ] j\in[z,t] j ∈ [ z , t ]
W − t v ≤ j ( j − v ) + w z , W = ∑ i = 1 t d i + w z . (36) W-tv\le j(j-v)+wz,\qquad W=\sum_{i=1}^{t}d_i+wz. \tag*{(36)} W − t v ≤ j ( j − v ) + w z , W = i = 1 ∑ t d i + w z . (36) Proof. Nested neighbourhoods have distinct representatives if d i ≥ t + 2 − i d_i\ge t+2-i d i ≥ t + 2 − i i i i d t + 1 − j ≤ j d_{t+1-j}\le j d t + 1 − j ≤ j 0 ≤ j ≤ t 0\le j\le t 0 ≤ j ≤ t z ≤ j z\le j z ≤ j t − j t-j t − j v v v j j j t t t j j j
A centered moment inequality
Suppose
m ≥ 3 v , t + 1 ≤ v ≤ 2 t , y = v − t , 0 < b ≤ v , b v ≥ 2 t y . m \ge3v,\qquad t+1 \le v \le2t,\qquad y=v-t,\qquad0<b\le v,\qquad bv\ge2ty. m ≥ 3 v , t + 1 ≤ v ≤ 2 t , y = v − t , 0 < b ≤ v , b v ≥ 2 t y . Convexity in j j j
W − t v ≤ G w ( z ) : = max { z ( z + w − v ) , − t y + w z } , 0 ≤ z ≤ t . W-tv\le G_w(z):=\max\{z(z+w-v),-ty+wz\},\qquad0\le z\le t. W − t v ≤ G w ( z ) := max { z ( z + w − v ) , − t y + w z } , 0 ≤ z ≤ t . Put κ = t y / b 2 \kappa=ty/b^2 κ = t y / b 2
Q w ( z ) = w z − t y + κ ( z − b ) 2 = κ z 2 + ( w − 2 t y / b ) z Q_w(z)=wz-ty+\kappa(z-b)^2=\kappa z^2+(w-2ty/b)z Q w ( z ) = w z − t y + κ ( z − b ) 2 = κ z 2 + ( w − 2 t y / b ) z dominates both branches. Its difference from the linear branch is a square; its difference from the other branch is z [ ( κ − 1 ) z + v − 2 t y / b ] z[(\kappa-1)z+v-2ty/b] z [( κ − 1 ) z + v − 2 t y / b ] z z z y ( t / b − 1 ) 2 y(t/b-1)^2 y ( t / b − 1 ) 2 t t t
Using (A.2), with C = ( t 3 ) C=\binom{t}{3} C = ( 3 t ) μ = v ∣ A ∣ / C \mu=v|A|/C μ = v ∣ A ∣/ C
E ( W − t v ) ≤ Φ w ( μ ) : = κ ( 1 − 2 / v ) μ 2 + ( w − 2 t y / b + 2 κ ) μ . (37) \mathbb{E}(W-tv)\le\Phi_w(\mu):=\kappa(1-2/v)\mu^2+(w-2ty/b+2\kappa)\mu. \tag*{(37)} E ( W − t v ) ≤ Φ w ( μ ) := κ ( 1 − 2/ v ) μ 2 + ( w − 2 t y / b + 2 κ ) μ . (37) This is convex, including the limiting case v = 2 v=2 v = 2 μ ≤ b \mu\le b μ ≤ b Φ w ( 0 ) = 0 \Phi_w(0)=0 Φ w ( 0 ) = 0
M w : = t y − w b − 2 t y b ( 1 − b / v ) ≥ 0 , (38) M_w:=ty-wb-\frac{2ty}{b}(1-b/v)\ge0, \tag*{(38)} M w := t y − w b − b 2 t y ( 1 − b / v ) ≥ 0 , (38) then Φ w ( μ ) ≤ 0 \Phi_w(\mu)\le0 Φ w ( μ ) ≤ 0 Φ w ( b ) = − M w \Phi_w(b)=-M_w Φ w ( b ) = − M w ∣ H ∣ ≤ ( w − 1 ) ∣ A ∣ |\mathcal{H}|\le(w-1)|A| ∣ H ∣ ≤ ( w − 1 ) ∣ A ∣
Section A.7 adapts the centre to the actual mean for the finite refinement, while retaining a two-endpoint reduction.
Lemma A.8. For an integer t ≥ 1 t\ge1 t ≥ 1 G G G ν ( G ) ≤ t \nu(G)\le t ν ( G ) ≤ t
K 3 ( G ) − t − 1 2 e ( G ) ≤ g 1 / 2 : = t ( t + 1 ) ( 2 t + 1 ) 6 . (39) K_3(G)-\frac{t-1}{2}e(G)\le g_{1/2}:=\frac{t(t+1)(2t+1)}{6}. \tag*{(39)} K 3 ( G ) − 2 t − 1 e ( G ) ≤ g 1/2 := 6 t ( t + 1 ) ( 2 t + 1 ) . (39) If its ground set has size N ≥ 2 t + 1 N\ge2t+1 N ≥ 2 t + 1 0 ≤ λ ≤ ( t − 1 ) / 3 0\le\lambda\le(t-1)/3 0 ≤ λ ≤ ( t − 1 ) /3
K 3 ( G ) − λ e ( G ) ≤ g λ ( t , N ) : = max { C λ ( t ) , J λ ( N , t ) } , K_3(G)-\lambda e(G)\le g_\lambda(t,N):=\max\{C_\lambda(t),J_\lambda(N,t)\}, K 3 ( G ) − λ e ( G ) ≤ g λ ( t , N ) := max { C λ ( t ) , J λ ( N , t )} , C λ ( t ) = ( 2 t + 1 3 ) − λ ( 2 t + 1 2 ) , C_\lambda(t)=\binom{2t+1}{3}-\lambda\binom{2t+1}{2}, C λ ( t ) = ( 3 2 t + 1 ) − λ ( 2 2 t + 1 ) , J λ ( N , t ) = ( t 3 ) + ( N − t ) ( t 2 ) − λ [ ( t 2 ) + t ( N − t ) ] . (40) J_\lambda(N,t)=\binom{t}{3}+(N-t)\binom{t}{2}-\lambda\left[\binom{t}{2}+t(N-t)\right]. \tag*{(40)} J λ ( N , t ) = ( 3 t ) + ( N − t ) ( 2 t ) − λ [ ( 2 t ) + t ( N − t ) ] . (40) In particular,
K 3 ( G ) − t − 1 3 e ( G ) ≤ max { t 2 ( 2 t + 1 ) 3 , t ( t − 1 ) ( N − t − 1 ) 6 } . (41) K_3(G)-\frac{t-1}{3}e(G)\le\max\left\{\frac{t^2(2t+1)}{3},\frac{t(t-1)(N-t-1)}{6}\right\}. \tag*{(41)} K 3 ( G ) − 3 t − 1 e ( G ) ≤ max { 3 t 2 ( 2 t + 1 ) , 6 t ( t − 1 ) ( N − t − 1 ) } . (41) Proof. By graph compression, we may assume that G G G h b h_b h b b b b 1 2 ∑ b h b ( h b − t ) \frac{1}{2}\sum_b h_b(h_b-t) 2 1 ∑ b h b ( h b − t ) b ≥ 2 t + 2 b\ge2t+2 b ≥ 2 t + 2 h b ≤ t h_b\le t h b ≤ t ( t + 1 , b ) (t+1,b) ( t + 1 , b ) ( i , t + 1 + i ) (i,t+1+i) ( i , t + 1 + i ) 1 ≤ i ≤ t + 1 1\le i\le t+1 1 ≤ i ≤ t + 1 h b > t h_b>t h b > t t + 1 t+1 t + 1 − t ( t 2 − 1 ) / 12 -t(t^2-1)/12 − t ( t 2 − 1 ) /12 t + 2 ≤ b ≤ 2 t + 1 t+2 \le b \le2t+1 t + 2 ≤ b ≤ 2 t + 1 ( b − 1 ) ( b − 1 − t ) / 2 (b-1)(b-1-t)/2 ( b − 1 ) ( b − 1 − t ) /2 t ( 5 t 2 + 6 t + 1 ) / 12 t(5t^2+6t+1)/12 t ( 5 t 2 + 6 t + 1 ) /12 h b > t h_b>t h b > t
For (A.11), the case N = 2 t + 1 N=2t+1 N = 2 t + 1 3 K 3 ≤ ( N − 2 ) e 3K_3 \le(N-2)e 3 K 3 ≤ ( N − 2 ) e ( N − 2 ) / 3 − λ ≥ 0 (N-2)/3-\lambda\ge0 ( N − 2 ) /3 − λ ≥ 0 N ≥ 2 t + 2 N \ge2t+2 N ≥ 2 t + 2 ( a + 1 , 2 t + 2 − a ) (a+1,2t+2-a) ( a + 1 , 2 t + 2 − a ) 0 ≤ a ≤ t 0 \le a \le t 0 ≤ a ≤ t b 0 = 2 t + 1 − a b_0=2t+1-a b 0 = 2 t + 1 − a [ b 0 ] [b_0] [ b 0 ] [ a ] [a] [ a ] ( b 0 3 ) − λ ( b 0 2 ) \binom{b_0}{3}-\lambda\binom{b_0}{2} ( 3 b 0 ) − λ ( 2 b 0 ) ( b 0 − 2 ) / 3 − λ ≥ 0 (b_0-2)/3-\lambda\ge0 ( b 0 − 2 ) /3 − λ ≥ 0 h ≤ a h \le a h ≤ a ( h 2 ) − λ h \binom{h}{2}-\lambda h ( 2 h ) − λh max { 0 , ( a 2 ) − λ a } \max\{0,\binom{a}{2}-\lambda a\} max { 0 , ( 2 a ) − λa } a ≤ 2 λ + 1 a \le2\lambda+1 a ≤ 2 λ + 1 C λ ( t ) C_\lambda(t) C λ ( t ) b 0 ≥ t + 1 b_0 \ge t+1 b 0 ≥ t + 1
T ( a ) = ( 2 t + 1 − a 3 ) − λ ( 2 t + 1 − a 2 ) + ( N − 2 t − 1 + a ) ( ( a 2 ) − λ a ) . T(a)=\binom{2t+1-a}{3}-\lambda\binom{2t+1-a}{2}+(N-2t-1+a)\left(\binom{a}{2}-\lambda a\right). T ( a ) = ( 3 2 t + 1 − a ) − λ ( 2 2 t + 1 − a ) + ( N − 2 t − 1 + a ) ( ( 2 a ) − λa ) . Here T ′ ′ ( a ) = N + 2 a − 3 λ − 2 > 0 T''(a)=N+2a-3\lambda-2>0 T ′′ ( a ) = N + 2 a − 3 λ − 2 > 0 C λ ( t ) C_\lambda(t) C λ ( t ) a = t a=t a = t J λ ( N , t ) J_\lambda(N,t) J λ ( N , t ) λ = ( t − 1 ) / 3 \lambda=(t-1)/3 λ = ( t − 1 ) /3
Both bounds are sharp when N ≥ 2 t + 1 N \ge2t+1 N ≥ 2 t + 1 K 2 t + 1 K_{2t+1} K 2 t + 1 t t t ( 2 t + 1 2 ) \binom{2t+1}{2} ( 2 2 t + 1 ) ( 2 t + 1 3 ) \binom{2t+1}{3} ( 3 2 t + 1 ) K t ∨ K N − t K_t \vee K_{N-t} K t ∨ K N − t t t t
e = ( t 2 ) + t ( N − t ) , K 3 = ( t 3 ) + ( N − t ) ( t 2 ) . e=\binom{t}{2}+t(N-t),\qquad K_3=\binom{t}{3}+(N-t)\binom{t}{2}. e = ( 2 t ) + t ( N − t ) , K 3 = ( 3 t ) + ( N − t ) ( 2 t ) . It attains the second term of (A.12). For every admissible weight, the same two graphs realize the two terms in (A.11). Thus all the displayed bounds are exact maxima.
Lemma A.9 (A graph bound for all nonnegative weights). For an integer u ≥ 1 u \ge1 u ≥ 1 G G G N ≥ 2 u + 1 N \ge2u+1 N ≥ 2 u + 1 λ ≥ 0 \lambda\ge0 λ ≥ 0 ν ( G ) ≤ u \nu(G) \le u ν ( G ) ≤ u x + = max { 0 , x } x_+=\max\{0,x\} x + = max { 0 , x }
K 3 ( G ) − λ e ( G ) ≤ g ^ λ ( u , N ) K_3(G)-\lambda e(G)\le\widehat{g}_\lambda(u,N) K 3 ( G ) − λ e ( G ) ≤ g λ ( u , N ) : = max 0 ≤ a ≤ u { ( ( 2 u + 1 − a 3 ) − λ ( 2 u + 1 − a 2 ) ) + + ( ( N − 2 u − 1 + a ) ( ( a 2 ) − λ a ) ) + } . (42) :=\max_{0\le a\le u}\left\{\left(\binom{2u+1-a}{3}-\lambda\binom{2u+1-a}{2}\right)_+ +\left((N-2u-1+a)\left(\binom{a}{2}-\lambda a\right)\right)_+\right\}. \tag*{(42)} := 0 ≤ a ≤ u max { ( ( 3 2 u + 1 − a ) − λ ( 2 2 u + 1 − a ) ) + + ( ( N − 2 u − 1 + a ) ( ( 2 a ) − λa ) ) + } . (42) where a a a
Proof. Compress G G G N = 2 u + 1 N=2u+1 N = 2 u + 1 3 K 3 ≤ ( N − 2 ) e 3K_3\le(N-2)e 3 K 3 ≤ ( N − 2 ) e a = 0 a=0 a = 0 N ≥ 2 u + 2 N\ge2u+2 N ≥ 2 u + 2 Lemma A.8 gives a head of size b = 2 u + 1 − a b=2u+1-a b = 2 u + 1 − a [ a ] [a] [ a ] 3 K 3 ≤ ( b − 2 ) e 3K_3\le(b-2)e 3 K 3 ≤ ( b − 2 ) e K 3 − λ e ≤ ( ( b 3 ) − λ ( b 2 ) ) + K_3-\lambda e\le\left(\binom{b}{3}-\lambda\binom{b}{2}\right)_+ K 3 − λ e ≤ ( ( 3 b ) − λ ( 2 b ) ) + e ≤ ( b 2 ) e\le\binom{b}{2} e ≤ ( 2 b ) h ≤ a h\le a h ≤ a ( h 2 ) − λ h \binom{h}{2}-\lambda h ( 2 h ) − λh h h h 0 0 0 ( a 2 ) − λ a \binom{a}{2}-\lambda a ( 2 a ) − λa a a a
For a stable triple family A \mathcal{A} A [ m ] [m] [ m ] q = 3 t + 2 q=3t+2 q = 3 t + 2
G j = { P ∈ ( [ j − 1 ] 2 ) : P ∪ { j } ∈ A } . G_j=\left\{P\in\binom{[j-1]}{2}:P\cup\{j\}\in\mathcal{A}\right\}. G j = { P ∈ ( 2 [ j − 1 ] ) : P ∪ { j } ∈ A } . For j > q j>q j > q ν ( G j ) ≤ t \nu(G_j)\le t ν ( G j ) ≤ t t + 1 t+1 t + 1 t t t j j j j j j ν ( A ) ≤ t \nu(\mathcal{A})\le t ν ( A ) ≤ t j j j K 3 ( G j ) K_3(G_j) K 3 ( G j ) j j j A 0 = A ∩ ( [ q ] 3 ) A_0=A\cap\binom{[q]}{3} A 0 = A ∩ ( 3 [ q ] ) 4 K 4 ( A 0 ) ≤ ( q − 3 ) ∣ A 0 ∣ 4K_4(A_0)\le(q-3)|A_0| 4 K 4 ( A 0 ) ≤ ( q − 3 ) ∣ A 0 ∣
K 4 ( A ) ≤ t − 1 2 ∣ A ∣ + E 1 / 2 ( t , m ) , E 1 / 2 ( t , m ) = t + 1 4 ( 3 t + 2 3 ) + ( m − 3 t − 2 ) g 1 / 2 . (43) K_4(\mathcal{A})\le\frac{t-1}{2}|\mathcal{A}|+E_{1/2}(t,m),\qquad E_{1/2}(t,m)=\frac{t+1}{4}\binom{3t+2}{3}+(m-3t-2)g_{1/2}. \tag*{(43)} K 4 ( A ) ≤ 2 t − 1 ∣ A ∣ + E 1/2 ( t , m ) , E 1/2 ( t , m ) = 4 t + 1 ( 3 3 t + 2 ) + ( m − 3 t − 2 ) g 1/2 . (43) Proposition A.10. For t ≥ 2200 t\ge2200 t ≥ 2200 n ≥ ⌈ 287 t / 50 ⌉ n\ge\lceil287t/50\rceil n ≥ ⌈ 287 t /50 ⌉
Proof. At a = ⌈ 287 t / 50 ⌉ a=\lceil287t/50\rceil a = ⌈ 287 t /50 ⌉ m = a − t − 1 m=a-t-1 m = a − t − 1 m 0 = 237 t / 50 − 1 m_0=237t/50-1 m 0 = 237 t /50 − 1 m + = 237 t / 50 m_+=237t/50 m + = 237 t /50
m 0 ≤ m < m + , 79 t / 50 − 1 ≤ v = ⌊ m / 3 ⌋ ≤ 79 t / 50 , 29 t / 50 − 1 ≤ y ≤ 29 t / 50. m_0\le m<m_+,\qquad79t/50-1\le v=\lfloor m/3\rfloor\le79t/50,\qquad29t/50-1\le y\le29t/50. m 0 ≤ m < m + , 79 t /50 − 1 ≤ v = ⌊ m /3 ⌋ ≤ 79 t /50 , 29 t /50 − 1 ≤ y ≤ 29 t /50. For the lower bound on v v v v = ⌊ ( ⌈ 237 t / 50 ⌉ − 1 ) / 3 ⌋ v=\lfloor(\lceil237t/50\rceil-1)/3\rfloor v = ⌊(⌈ 237 t /50 ⌉ − 1 ) /3 ⌋ t ≥ 2200 t\ge2200 t ≥ 2200 m ≥ 4 t − 1 m\ge4t-1 m ≥ 4 t − 1
Write α = ∣ A ∣ / ( t 3 ) \alpha=|\mathcal{A}|/\binom{t}{3} α = ∣ A ∣/ ( 3 t ) α ≤ 161 / 316 \alpha\le161/316 α ≤ 161/316 ( m − t 3 ) / ( m 3 ) = ∏ i = 0 2 ( 1 − t / ( m − i ) ) \binom{m-t}{3}/\binom{m}{3}=\prod_{i=0}^{2}(1-t/(m-i)) ( 3 m − t ) / ( 3 m ) = ∏ i = 0 2 ( 1 − t / ( m − i )) m m m
316 ( m 0 − t 3 ) − 155 ( m 0 3 ) = P A ( t ) / 750000 , 316\binom{m_0-t}{3}-155\binom{m_0}{3}=P_A(t)/750000, 316 ( 3 m 0 − t ) − 155 ( 3 m 0 ) = P A ( t ) /750000 , P A ( t ) = 3019933 t 3 − 703202700 t 2 + 614817500 t − 120750000. P_A(t)=3019933t^3-703202700t^2+614817500t-120750000. P A ( t ) = 3019933 t 3 − 703202700 t 2 + 614817500 t − 120750000. Its coefficients after t = 2200 + x t=2200+x t = 2200 + x § 10 ).
If α > 12 / 25 \alpha>12/25 α > 12/25 ∣ H ∣ ≤ ( 23 t / 32 ) ∣ A ∣ |\mathcal{H}|\le(23t/32)|\mathcal{A}| ∣ H ∣ ≤ ( 23 t /32 ) ∣ A ∣
( 7 t / 32 + 1 / 2 ) ( 12 / 25 ) ( m 0 3 ) − E 1 / 2 ( t , m + ) = P J ( t ) / 150000000 > 0 , (7t/32+1/2)(12/25)\binom{m_0}{3}-E_{1/2}(t,m_+)=P_J(t)/150000000>0, ( 7 t /32 + 1/2 ) ( 12/25 ) ( 3 m 0 ) − E 1/2 ( t , m + ) = P J ( t ) /150000000 > 0 , P J ( t ) = 23803113 t 4 − 82886156 t 3 − 771716100 t 2 + 309590000 t − 36000000. P_J(t)=23803113t^4-82886156t^3-771716100t^2+309590000t-36000000. P J ( t ) = 23803113 t 4 − 82886156 t 3 − 771716100 t 2 + 309590000 t − 36000000. Again the translated coefficients are positive. Use the following weights and centers in (A.9):
Table 1 (PDF p. 47).
The first weight bounds c + 1 c+1 c + 1 t + 1 t+1 t + 1 μ ≤ b ≤ v \mu\le b\le v μ ≤ b ≤ v
b v − 2 t y ≥ 598 t 2 15625 , M w ≥ 7 t ( 474 t − 124127 ) 296250 , bv-2ty\ge\frac{598t^2}{15625},\qquad M_w\ge\frac{7t(474t-124127)}{296250}, b v − 2 t y ≥ 15625 598 t 2 , M w ≥ 296250 7 t ( 474 t − 124127 ) , b v − 2 t y ≥ 1119 t 2 10000 , M w ≥ 9 t ( 12719 t − 22718432 ) 81401600 . bv-2ty\ge\frac{1119t^2}{10000},\qquad M_w\ge\frac{9t(12719t-22718432)}{81401600}. b v − 2 t y ≥ 10000 1119 t 2 , M w ≥ 81401600 9 t ( 12719 t − 22718432 ) . For the first column, write b v − 2 t y = b t + ( b − 2 t ) y bv-2ty=bt+(b-2t)y b v − 2 t y = b t + ( b − 2 t ) y y y y y y y t y ty t y 1 − b / v ≤ 13 / 25 1-b/v\le13/25 1 − b / v ≤ 13/25 155 / 316 155/316 155/316 t ≥ 2200 t\ge2200 t ≥ 2200 t t t n n n
Proof of Theorem A.1 . First assume ν ( F ) = t \nu(\mathcal{F}) = t ν ( F ) = t w , b w,b w , b
v ( C ) ( ∣ H ∣ + ∑ i ∣ A i ∣ − t C ) ≤ Φ w ( μ ) . \frac{v}{\binom{C}{}} \left(|\mathcal{H}|+\sum_i|\mathcal{A}_i|-tC\right)\leq\Phi_w(\mu). ( C ) v ( ∣ H ∣ + i ∑ ∣ A i ∣ − tC ) ≤ Φ w ( μ ) . For 0 < μ ≤ b 0<\mu\leq b 0 < μ ≤ b Φ w ( μ ) / μ \Phi_w(\mu)/\mu Φ w ( μ ) / μ Φ w ( b ) = − M w \Phi_w(b)=-M_w Φ w ( b ) = − M w ( M w / b ) ∣ A ∣ (M_w/b)|\mathcal{A}| ( M w / b ) ∣ A ∣
η 1 ( t ) = 7 ( 474 t − 124127 ) 224676 , η 2 ( t ) = 9 ( 12719 t − 22718432 ) 65528288 . \eta_1(t)=\frac{7(474t-124127)}{224676},\qquad\eta_2(t)=\frac{9(12719t-22718432)}{65528288}. η 1 ( t ) = 224676 7 ( 474 t − 124127 ) , η 2 ( t ) = 65528288 9 ( 12719 t − 22718432 ) . For t ≥ 2200 t\geq2200 t ≥ 2200 η 1 > η 2 > 0 \eta_1>\eta_2>0 η 1 > η 2 > 0 2285 η 2 ≥ 3 t / 4 + 3 / 2 ≥ c + 1 2285\eta_2\geq3t/4+3/2\geq c+1 2285 η 2 ≥ 3 t /4 + 3/2 ≥ c + 1 t = 2200 + x t=2200+x t = 2200 + x
Table 9.
and every entry is positive. The section accounting and canonical diversity argument of Lemma A.6 yield d ≥ η 2 ∣ A ∣ d\geq\eta_2|\mathcal{A}| d ≥ η 2 ∣ A ∣ γ t ( F ) ≤ ( c + 1 ) ∣ A ∣ ≤ 2285 d \gamma_t(\mathcal{F})\leq(c+1)|\mathcal{A}|\leq2285d γ t ( F ) ≤ ( c + 1 ) ∣ A ∣ ≤ 2285 d μ = 0 \mu=0 μ = 0 A = H = ∅ \mathcal{A}=\mathcal{H}=\varnothing A = H = ∅ Lemma 2.1 extends the first bound to ν ( F ) ≤ t \nu(\mathcal{F})\leq t ν ( F ) ≤ t
Averaged matching deficits and a common tail bound
Let A ⊆ ( [ m ] 3 ) \mathcal{A}\subseteq\binom{[m]}{3} A ⊆ ( 3 [ m ] ) ν ( A ) ≤ t \nu(\mathcal{A})\leq t ν ( A ) ≤ t
q = 3 t + 2 ≤ m , A 0 = A ∩ ( [ q ] 3 ) , Δ = ( q 3 ) − ∣ A 0 ∣ , M = m − q . q=3t+2\leq m,\qquad\mathcal{A}_0=\mathcal{A}\cap\binom{[q]}{3},\qquad\Delta=\binom{q}{3}-|\mathcal{A}_0|,\qquad M=m-q. q = 3 t + 2 ≤ m , A 0 = A ∩ ( 3 [ q ] ) , Δ = ( 3 q ) − ∣ A 0 ∣ , M = m − q . Use the link graphs G j G_j G j ν ( G j ) ≤ t \nu(G_j)\leq t ν ( G j ) ≤ t j > q j>q j > q { 1 , 2 , j } \{1,2,j\} { 1 , 2 , j } j > q j>q j > q [ 3 , q ] [3,q] [ 3 , q ] t t t
Δ ≥ d 0 : = ( 3 t − 1 2 ) . (44) \Delta\geq d_0:=\binom{3t-1}{2}. \tag*{(44)} Δ ≥ d 0 := ( 2 3 t − 1 ) . (44) A sharp first deficit. On [ q + 1 ] [q+1] [ q + 1 ]
A ∗ = ( ( [ q ] 3 ) ∖ { { a , b , q } : 3 ≤ a < b ≤ q − 1 } ) ∪ { { 1 , 2 , q + 1 } } . \mathcal{A}^*=\left(\binom{[q]}{3}\setminus\{\{a,b,q\}:3\leq a<b\leq q-1\}\right)\cup\{\{1,2,q+1\}\}. A ∗ = ( ( 3 [ q ] ) ∖ {{ a , b , q } : 3 ≤ a < b ≤ q − 1 } ) ∪ {{ 1 , 2 , q + 1 }} . This family is stable and its head deficit is exactly d 0 d_0 d 0 t t t 1 , 2 , q 1,2,q 1 , 2 , q 3 t − 1 3t-1 3 t − 1 t − 1 t-1 t − 1 [ q − 1 ] [q-1] [ q − 1 ] t t t ν ( A ∗ ) = t \nu(\mathcal{A}^*)=t ν ( A ∗ ) = t K 3 − λ e K_3-\lambda e K 3 − λ e − λ ≤ 0 -\lambda\leq0 − λ ≤ 0
Lemma A.11 (Averaging over submatchings). Suppose G q + L G_{q+L} G q + L u u u 3 ≤ u ≤ t 3 \le u \le t 3 ≤ u ≤ t 1 ≤ r ≤ min { u , L } 1 \le r \le\min\{u,L\} 1 ≤ r ≤ min { u , L } t − r ≥ 33 t-r \ge33 t − r ≥ 33 h = q − 2 u h=q-2u h = q − 2 u
V t ( r ) = min { ( q − 2 r 3 ) − ( 3 ( t − r ) + 2 3 ) , ( 2 t + 2 − r 3 ) } . V_t(r)=\min\left\{\binom{q-2r}{3}-\binom{3(t-r)+2}{3},\binom{2t+2-r}{3}\right\}. V t ( r ) = min { ( 3 q − 2 r ) − ( 3 3 ( t − r ) + 2 ) , ( 3 2 t + 2 − r ) } . n 0 = ( h 3 ) , n 1 = u ( 2 ( h 2 ) + h ) , n_0=\binom{h}{3},\qquad n_1=u\left(2\binom{h}{2}+h\right), n 0 = ( 3 h ) , n 1 = u ( 2 ( 2 h ) + h ) , n 2 = ( u 2 ) ( 4 h + 4 ) , n 3 = 8 ( u 3 ) . n_2=\binom{u}{2}(4h+4),\qquad n_3=8\binom{u}{3}. n 2 = ( 2 u ) ( 4 h + 4 ) , n 3 = 8 ( 3 u ) . Put p k = ( u − k r ) / ( u r ) p_k=\binom{u-k}{r}/\binom{u}{r} p k = ( r u − k ) / ( r u ) 0 ≤ k ≤ 3 0\le k\le3 0 ≤ k ≤ 3
Δ ≥ D t ( u , r ) : = max { 0 , max 0 ≤ k ≤ 3 p k > 0 V t ( r ) − ∑ i < k ( p i − p k ) n i p k } . (45) \Delta\ge D_t(u,r):=\max\left\{0,\max_{\substack{0\le k\le3\\p_k>0}}\frac{V_t(r)-\sum_{i<k}(p_i-p_k)n_i}{p_k}\right\}. \tag*{(45)} Δ ≥ D t ( u , r ) := max ⎩ ⎨ ⎧ 0 , 0 ≤ k ≤ 3 p k > 0 max p k V t ( r ) − ∑ i < k ( p i − p k ) n i ⎭ ⎬ ⎫ . (45) Proof. By replacing occupied vertices with smaller unused vertices, shiftedness places a u u u [ 2 u ] [2u] [ 2 u ] u u u r r r q + 1 , … , q + r q+1,\ldots,q+r q + 1 , … , q + r A \mathcal{A} A 2 r 2r 2 r t − r t-r t − r q − 2 r q-2r q − 2 r
( q − 2 r ) − 3 ( t − r ) − 3 = r − 1 ≥ 0 , (q-2r)-3(t-r)-3=r-1\ge0, ( q − 2 r ) − 3 ( t − r ) − 3 = r − 1 ≥ 0 , and forces at least V t ( r ) V_t(r) V t ( r )
Classify head triples by the number k k k n k n_k n k k = 1 k=1 k = 1 k = 2 k=2 k = 2 x k x_k x k k k k 0 ≤ x k ≤ n k 0\le x_k\le n_k 0 ≤ x k ≤ n k Δ = ∑ k x k \Delta=\sum_k x_k Δ = ∑ k x k k k k r r r p k p_k p k ∑ k p k x k ≥ V t ( r ) \sum_k p_kx_k\ge V_t(r) ∑ k p k x k ≥ V t ( r ) p 0 ≥ p 1 ≥ p 2 ≥ p 3 p_0\ge p_1\ge p_2\ge p_3 p 0 ≥ p 1 ≥ p 2 ≥ p 3 p k > 0 p_k>0 p k > 0
V t ( r ) ≤ p k Δ + ∑ i < k ( p i − p k ) x i + ∑ i > k ( p i − p k ) x i ≤ p k Δ + ∑ i < k ( p i − p k ) n i . V_t(r)\le p_k\Delta+\sum_{i<k}(p_i-p_k)x_i+\sum_{i>k}(p_i-p_k)x_i\le p_k\Delta+\sum_{i<k}(p_i-p_k)n_i. V t ( r ) ≤ p k Δ + i < k ∑ ( p i − p k ) x i + i > k ∑ ( p i − p k ) x i ≤ p k Δ + i < k ∑ ( p i − p k ) n i . Taking ceilings proves (A.16).
The bound is necessary; it does not claim that every feasible four-class profile can be realized by a stable family. Its useful feature is that the same Δ \Delta Δ T \mathcal{T} T ( u , r , D t ( u , r ) ) (u,r,D_t(u,r)) ( u , r , D t ( u , r )) ( 1 , 1 , d 0 ) (1,1,d_0) ( 1 , 1 , d 0 ) Δ < D \Delta<D Δ < D ( u , r , D ) (u,r,D) ( u , r , D ) ν ( G q + j ) ≤ u − 1 \nu(G_{q+j})\le u-1 ν ( G q + j ) ≤ u − 1 j ≥ r j\ge r j ≥ r 0 ≤ δ ≤ ( q 3 ) 0\le\delta\le\binom{q}{3} 0 ≤ δ ≤ ( 3 q )
u δ ( j ) = min ( { t } ∪ { u − 1 : ( u , r , D ) ∈ T , r ≤ j , D > δ } ) . u_\delta(j)=\min\left(\{t\}\cup\{u-1:(u,r,D)\in\mathcal{T},\ r\le j,\ D>\delta\}\right). u δ ( j ) = min ( { t } ∪ { u − 1 : ( u , r , D ) ∈ T , r ≤ j , D > δ } ) . These are upper bounds for the link matchings, not a realizability claim. For 0 ≤ a ≤ ( q 3 ) 0\le a\le\binom{q}{3} 0 ≤ a ≤ ( 3 q ) z ( a ) ≥ 3 z(a)\ge3 z ( a ) ≥ 3 ( z ( a ) 3 ) ≥ a \binom{z(a)}{3}\ge a ( 3 z ( a ) ) ≥ a z ( 0 ) = 3 z(0)=3 z ( 0 ) = 3
β λ ( a ) = max { 0 , ( ( z ( a ) − 3 ) / 4 − λ ) a } . (46) \beta_\lambda(a)=\max\{0,((z(a)-3)/4-\lambda)a\}. \tag*{(46)} β λ ( a ) = max { 0 , (( z ( a ) − 3 ) /4 − λ ) a } . (46) Equation (A.3) implies K 4 ( A 0 ) − λ ∣ A 0 ∣ ≤ β λ ( a ) K_4(A_0)-\lambda|A_0|\le\beta_\lambda(a) K 4 ( A 0 ) − λ ∣ A 0 ∣ ≤ β λ ( a ) ∣ A 0 ∣ ≤ a |A_0|\le a ∣ A 0 ∣ ≤ a β λ \beta_\lambda β λ
Proposition A.12 (A common deficit for the tail). Assume all cut values lie in [ 0 , ( q 3 ) ] [0,\binom{q}{3}] [ 0 , ( 3 q ) ] Take 0 ≤ λ ≤ ( t − 1 ) / 3 0 \le\lambda\le(t-1)/3 0 ≤ λ ≤ ( t − 1 ) /3 u δ ( j ) u_\delta(j) u δ ( j ) λ ≤ ( u δ ( j ) − 1 ) / 3 \lambda\le(u_\delta(j)-1)/3 λ ≤ ( u δ ( j ) − 1 ) /3 g λ ( 0 , N ) = 0 g_\lambda(0,N)=0 g λ ( 0 , N ) = 0
D = { 0 } ∪ { D : ( u , r , D ) ∈ T } , \mathcal{D}=\{0\}\cup\{D:(u,r,D)\in\mathcal{T}\}, D = { 0 } ∪ { D : ( u , r , D ) ∈ T } , E T = max δ ∈ D { β λ ( ( q 3 ) − δ ) + ∑ j = 1 M g λ ( u δ ( j ) , q + j − 1 ) } . (47) E_{\mathcal{T}}=\max_{\delta\in\mathcal{D}}\left\{\beta_\lambda\left(\binom{q}{3}-\delta\right)+\sum_{j=1}^{M}g_\lambda(u_\delta(j),q+j-1)\right\}. \tag*{(47)} E T = δ ∈ D max { β λ ( ( 3 q ) − δ ) + j = 1 ∑ M g λ ( u δ ( j ) , q + j − 1 ) } . (47) Then K 4 ( A ) ≤ λ ∣ A ∣ + E T K_4(\mathcal{A})\le\lambda|\mathcal{A}|+E_{\mathcal{T}} K 4 ( A ) ≤ λ ∣ A ∣ + E T
Proof. Decomposition by largest vertex gives exactly
K 4 ( A ) − λ ∣ A ∣ = K 4 ( A 0 ) − λ ∣ A 0 ∣ + ∑ j = 1 M ( K 3 ( G q + j ) − λ e ( G q + j ) ) . K_4(\mathcal{A})-\lambda|\mathcal{A}|=K_4(\mathcal{A}_0)-\lambda|\mathcal{A}_0|+\sum_{j=1}^{M}\left(K_3(G_{q+j})-\lambda e(G_{q+j})\right). K 4 ( A ) − λ ∣ A ∣ = K 4 ( A 0 ) − λ ∣ A 0 ∣ + j = 1 ∑ M ( K 3 ( G q + j ) − λ e ( G q + j ) ) . Apply (A.17) to the head and (A.11) to each positive-cap link; a zero cap makes that link empty. Between consecutive cut values the caps are constant and the head term is nonincreasing. The left endpoint of each interval therefore suffices, proving (A.18). The state δ = 0 \delta=0 δ = 0
The finite reduction covers every deficit interval. It does not sample selected hypergraphs or assume that the relaxed maximizing state is attained.
The same proposition holds for every λ ≥ 0 \lambda\ge0 λ ≥ 0 g λ g_\lambda g λ g ^ λ \widehat{g}_\lambda g λ q + j − 1 ≥ 3 t + 2 ≥ 2 u δ ( j ) + 1 q+j-1\ge3t+2\ge2u_\delta(j)+1 q + j − 1 ≥ 3 t + 2 ≥ 2 u δ ( j ) + 1 E ^ T \widehat{E}_{\mathcal{T}} E T
Adapted moments and the finite certificate
The centre used in Section A.4 can depend on the mean density while remaining deterministic.
Lemma A.13 (Density-adapted centre). Suppose m ≥ 3 v m\ge3v m ≥ 3 v t + 1 ≤ v ≤ 2 t t+1\le v\le2t t + 1 ≤ v ≤ 2 t v > 2 v>2 v > 2 Var Z ≤ ρ μ ( 1 − μ / v ) \operatorname{Var}Z\le\rho\mu(1-\mu/v) Var Z ≤ ρ μ ( 1 − μ / v ) 0 < ρ < v 0<\rho<v 0 < ρ < v y = v − t y=v-t y = v − t a v = 1 − ρ / v a_v=1-\rho/v a v = 1 − ρ / v ξ 0 = 2 t y / v \xi_0=2ty/v ξ 0 = 2 t y / v ξ ( μ ) = max { ξ 0 , a v μ + ρ } \xi(\mu)=\max\{\xi_0,a_v\mu+\rho\} ξ ( μ ) = max { ξ 0 , a v μ + ρ } 0 ≤ μ ≤ v 0\le\mu\le v 0 ≤ μ ≤ v
For the nested incidence variable of Lemma A.7,
E ( W − t v ) ≤ Ψ w ( μ ) : = w μ − 2 t y μ ξ ( μ ) + t y ( a v μ 2 + ρ μ ) ξ ( μ ) 2 . (48) \mathbb{E}(W-tv)\le\Psi_w(\mu):=w\mu-\frac{2ty\mu}{\xi(\mu)}+\frac{ty(a_v\mu^2+\rho\mu)}{\xi(\mu)^2}. \tag*{(48)} E ( W − t v ) ≤ Ψ w ( μ ) := w μ − ξ ( μ ) 2 t y μ + ξ ( μ ) 2 t y ( a v μ 2 + ρ μ ) . (48) The function Ψ w \Psi_w Ψ w Ψ w ( 0 ) = 0 \Psi_w(0)=0 Ψ w ( 0 ) = 0
Proof. For every ξ ∈ [ ξ 0 , v ] \xi\in[\xi_0,v] ξ ∈ [ ξ 0 , v ] w z − t y + t y ( z − ξ ) 2 / ξ 2 wz-ty+ty(z-\xi)^2/\xi^2 w z − t y + t y ( z − ξ ) 2 / ξ 2 b = ξ b=\xi b = ξ ξ \xi ξ μ > 0 \mu>0 μ > 0 ξ \xi ξ ξ − ( a v μ + ρ ) \xi-(a_v\mu+\rho) ξ − ( a v μ + ρ ) a v μ + ρ ≤ v a_v\mu+\rho\le v a v μ + ρ ≤ v ξ ( μ ) \xi(\mu) ξ ( μ )
On the free branch the expression is
w μ − t y μ a v μ + ρ , d 2 d μ 2 ( w μ − t y μ a v μ + ρ ) = 2 t y ρ a v ( a v μ + ρ ) 3 > 0. w\mu-\frac{ty\mu}{a_v\mu+\rho},\qquad
\frac{d^2}{d\mu^2}\left(w\mu-\frac{ty\mu}{a_v\mu+\rho}\right)=\frac{2ty\rho a_v}{(a_v\mu+\rho)^3}>0. w μ − a v μ + ρ t y μ , d μ 2 d 2 ( w μ − a v μ + ρ t y μ ) = ( a v μ + ρ ) 3 2 t y ρ a v > 0. The clamped branch is a convex quadratic with second derivative 2 t y a v / ξ 0 2 2tya_v/\xi_0^2 2 t y a v / ξ 0 2 ξ 0 ≤ ρ \xi_0\le\rho ξ 0 ≤ ρ μ = 0 \mu=0 μ = 0
In the formulas below, ρ = 2 \rho= 2 ρ = 2 ρ = 2 \rho= 2 ρ = 2
Set C = ( m 3 ) C = \binom{m}{3} C = ( 3 m ) B = B 3 ( m , t ) B = B_3(m,t) B = B 3 ( m , t ) b = v B / C b = vB/C b = v B / C t ≥ 33 t \ge33 t ≥ 33 m ≥ 4 t − 1 m \ge4t - 1 m ≥ 4 t − 1 μ ≤ b \mu\le b μ ≤ b K 4 ( A ) ≤ λ ∣ A ∣ + E K_4(A) \le\lambda|A| + E K 4 ( A ) ≤ λ ∣ A ∣ + E 0 ≤ λ < c 0 \le\lambda< c 0 ≤ λ < c
v C ( ∣ H ∣ + ∑ i ∣ A i ∣ − t C ) ≤ F ( μ ) : = Ψ λ + 1 ( μ ) + min { ( c − λ ) μ , E v / C } . (49) \frac{v}{C}\left(|\mathcal{H}| + \sum_i |A_i| - tC\right) \le F(\mu) := \Psi_{\lambda+1}(\mu) + \min\{(c-\lambda)\mu, Ev/C\}. \tag*{(49)} C v ( ∣ H ∣ + i ∑ ∣ A i ∣ − tC ) ≤ F ( μ ) := Ψ λ + 1 ( μ ) + min {( c − λ ) μ , E v / C } . (49) If 0 < μ ∗ : = E v / [ C ( c − λ ) ] < b ≤ v 0 < \mu_* := Ev/[C(c-\lambda)] < b \le v 0 < μ ∗ := E v / [ C ( c − λ )] < b ≤ v F F F [ 0 , μ ∗ ] [0,\mu_*] [ 0 , μ ∗ ] [ μ ∗ , b ] [\mu_*,b] [ μ ∗ , b ] F ( 0 ) = 0 F(0) = 0 F ( 0 ) = 0
For each 3229 ≤ t ≤ 3480 3229 \le t \le3480 3229 ≤ t ≤ 3480
n = t + 15301 , m = 15300 , v = 5100 , λ = 3 ( t − 1 ) 100 , E = E T . n = t + 15301,\qquad m = 15300,\qquad v = 5100,\qquad\lambda= \frac{3(t-1)}{100},\qquad E = E_T. n = t + 15301 , m = 15300 , v = 5100 , λ = 100 3 ( t − 1 ) , E = E T . The finite cut set consists of ( 1 , 1 , d 0 ) (1,1,d_0) ( 1 , 1 , d 0 )
u = ⌊ i t / 1000 ⌋ , i = 250 , 300 , … , 1000 , r = ⌊ j t / 1000 ⌋ , j = 25 , 75 , … , j ≤ i , u = \lfloor it/1000\rfloor,\quad i = 250,300,\ldots,1000,\qquad r = \lfloor jt/1000\rfloor,\quad j = 25,75,\ldots,\quad j \le i, u = ⌊ i t /1000 ⌋ , i = 250 , 300 , … , 1000 , r = ⌊ j t /1000 ⌋ , j = 25 , 75 , … , j ≤ i , subject to 1 ≤ r ≤ u 1 \le r \le u 1 ≤ r ≤ u t − r ≥ 33 t-r \ge33 t − r ≥ 33
Table 10.
The cuts encode a fractional capacity calculation; the distributed verifier checks them using the dual inequalities (A.16). It reconstructs every deficit interval and sums the tail envelopes exactly, using arithmetic progressions between their breakpoints. In particular, this covers all 103 states at the critical base.
Both endpoint maxima occur at t = 3480 t = 3480 t = 3480
q = 10442 , c = 2610 , 100 E = 62543109568930107 , b = 321648884360 117022051 , q = 10442,\qquad c = 2610,\qquad100E = 62543109568930107,\qquad b = \frac{321648884360}{117022051}, q = 10442 , c = 2610 , 100 E = 62543109568930107 , b = 117022051 321648884360 , μ ∗ = 20847703189643369 9773798721571 , \mu_* = \frac{20847703189643369}{9773798721571}, μ ∗ = 9773798721571 20847703189643369 , and
F ( b ) = − 734432834661303950523791651 480071155938247978303700 < 0 , F(b) = -\frac{734432834661303950523791651}{480071155938247978303700} < 0, F ( b ) = − 480071155938247978303700 734432834661303950523791651 < 0 , F ( μ ∗ ) = − 12342446404786844238991062728486983 211193652014625943473584177232 < 0. F(\mu_*) = -\frac{12342446404786844238991062728486983}{211193652014625943473584177232} < 0. F ( μ ∗ ) = − 211193652014625943473584177232 12342446404786844238991062728486983 < 0. The maximizing envelope state is Δ = 45051066360 \Delta= 45051066360 Δ = 45051066360
The additional base at t = 2904 t = 2904 t = 2904 Use the same cut selection and envelope with
n = 15676 , m = 12771 , v = 4257 , y = 1353 , q = 8714 , c = 2178 , λ = 8709 100 . n = 15676,\quad m = 12771,\quad v = 4257,\quad y = 1353,\quad q = 8714,\quad c = 2178,\quad\lambda= \frac{8709}{100}. n = 15676 , m = 12771 , v = 4257 , y = 1353 , q = 8714 , c = 2178 , λ = 100 8709 . There are 200 averaged cuts and 103 deficit states, including zero. The certificate checks all the domains used above and gives
100 E = 30345188802828751 , b = 37403488540 16306013 , μ ∗ = 30345188802828751 17047202820915 . 100E = 30345188802828751,\quad b = \frac{37403488540}{16306013},\quad\mu_* = \frac{30345188802828751}{17047202820915}. 100 E = 30345188802828751 , b = 16306013 37403488540 , μ ∗ = 17047202820915 30345188802828751 . In particular, 0 < μ ∗ < b ≤ v 0 < \mu_* < b \le v 0 < μ ∗ < b ≤ v
F ( b ) = − 206897019088563628476145569 59031722428985718476500 < 0 , F(b) = -\frac{206897019088563628476145569}{59031722428985718476500} < 0, F ( b ) = − 59031722428985718476500 206897019088563628476145569 < 0 , F ( μ ∗ ) = − 396285397094368554542026979822553289 9226892430402448555509056468640 < 0. F(\mu_*) = -\frac{396285397094368554542026979822553289}{9226892430402448555509056468640} < 0. F ( μ ∗ ) = − 9226892430402448555509056468640 396285397094368554542026979822553289 < 0. At each of the 103 states the verifier sums the envelope over all 4057 tail positions using exact arithmetic progressions. These are fixed certificate checks, with no additional hypothesis on F \mathcal{F} F
The further base at t = 888 t = 888 t = 888 The general lemmas above also apply at
n = 4798 , m = 3909 , v = 1303 , y = 415 , q = 2666 , c = 666 , λ = 2661 100 . n = 4798,\quad m = 3909,\quad v = 1303,\quad y = 415,\quad q = 2666,\quad c = 666,\quad\lambda= \frac{2661}{100}. n = 4798 , m = 3909 , v = 1303 , y = 415 , q = 2666 , c = 666 , λ = 100 2661 . Here t ≥ 33 t \ge33 t ≥ 33 m ≥ 4 t − 1 m \ge4t - 1 m ≥ 4 t − 1 q ≤ m q \le m q ≤ m n ≥ 4 t + 4 n \ge4t + 4 n ≥ 4 t + 4 t + 1 ≤ v ≤ 2 t t + 1 \le v \le2t t + 1 ≤ v ≤ 2 t ( 1 , 1 , d 0 ) (1,1,d_0) ( 1 , 1 , d 0 ) d 0 = 3544453 d_0 = 3544453 d 0 = 3544453 t − r ≥ 33 t-r \ge33 t − r ≥ 33
100 E = 265583224513928 , b = 2678431702 3817139 , μ ∗ = 132791612256964 244064050521 , 100E = 265583224513928,\quad b = \frac{2678431702}{3817139},\quad\mu_* = \frac{132791612256964}{244064050521}, 100 E = 265583224513928 , b = 3817139 2678431702 , μ ∗ = 244064050521 132791612256964 , and
F ( b ) = − 21670567755141894005923 27790259876854163550 < 0 , F(b) = -\frac{21670567755141894005923}{27790259876854163550} < 0, F ( b ) = − 27790259876854163550 21670567755141894005923 < 0 , F ( μ ∗ ) = − 9548351932641510714925649296621 2195172693406543742168343732 < 0. F(\mu_*) = -\frac{9548351932641510714925649296621}{2195172693406543742168343732} < 0. F ( μ ∗ ) = − 2195172693406543742168343732 9548351932641510714925649296621 < 0. We have 0 < μ ∗ < b ≤ v 0 < \mu_* < b \le v 0 < μ ∗ < b ≤ v t ≥ 2200 t \ge2200 t ≥ 2200
The base at t = 360 t = 360 t = 360 The same cut grid and moment lemmas apply with
n = 1950 , m = 1589 , v = 529 , y = 169 , q = 1082 , c = 270 , λ = 1077 100 . n = 1950,\quad m = 1589,\quad v = 529,\quad y = 169,\quad q = 1082,\quad c = 270,\quad\lambda= \frac{1077}{100}. n = 1950 , m = 1589 , v = 529 , y = 169 , q = 1082 , c = 270 , λ = 100 1077 . Here m = 3 v + 2 m = 3v + 2 m = 3 v + 2 m ≥ 3 v m \ge3v m ≥ 3 v t ≥ 33 t \ge33 t ≥ 33 m ≥ 4 t − 1 m \ge4t - 1 m ≥ 4 t − 1 q ≤ m q \le m q ≤ m n ≥ 4 t + 4 n \ge4t + 4 n ≥ 4 t + 4 t + 1 ≤ v ≤ 2 t t + 1 \le v \le2t t + 1 ≤ v ≤ 2 t
100 E = 7198243043040 , b = 179393730 630833 , μ ∗ = 171386739120 778718279 , 100E = 7198243043040,\quad b = \frac{179393730}{630833},\quad\mu_* = \frac{171386739120}{778718279}, 100 E = 7198243043040 , b = 630833 179393730 , μ ∗ = 778718279 171386739120 , with 0 < μ ∗ < b ≤ v 0 < \mu_* < b \le v 0 < μ ∗ < b ≤ v
F ( b ) = − 2272864566320194107 9384421237500155 < 0 , F(b)=-\frac{2272864566320194107}{9384421237500155}<0, F ( b ) = − 9384421237500155 2272864566320194107 < 0 , F ( μ ∗ ) = − 241993520128384136905733 307445894130701973387 < 0. F(\mu_*)=-\frac{241993520128384136905733}{307445894130701973387}<0. F ( μ ∗ ) = − 307445894130701973387 241993520128384136905733 < 0. Exact arithmetic progressions sum all 507 tail positions at each of the 100 states. As at the other bases, the two endpoint signs use convexity separately on the two sides of μ ∗ \mu_* μ ∗
The base at t = 72 t=72 t = 72 The same parametric lemmas, rather than the uniform theorem, apply with
n = 395 , m = 322 , v = 107 , y = 35 , q = 218 , c = 54 , λ = 213 100 . n=395,\quad m=322,\quad v=107,\quad y=35,\quad q=218,\quad c=54,\quad\lambda=\frac{213}{100}. n = 395 , m = 322 , v = 107 , y = 35 , q = 218 , c = 54 , λ = 100 213 . The ground set satisfies q ≤ m ≤ 5 t + 8 q\le m\le5t+8 q ≤ m ≤ 5 t + 8 m ≥ 4 t − 1 m\ge4t-1 m ≥ 4 t − 1 n ≥ 4 t + 4 n\ge4t+4 n ≥ 4 t + 4 t + 1 ≤ v ≤ 2 t t+1\le v\le2t t + 1 ≤ v ≤ 2 t m = 3 v + 1 m=3v+1 m = 3 v + 1 Lemma A.8 . The cuts give 67 deficit states, and
100 E = 11744277120 , b = 73491 1288 , μ ∗ = 12233622 278369 . 100E=11744277120,\qquad b=\frac{73491}{1288},\qquad\mu_*=\frac{12233622}{278369}. 100 E = 11744277120 , b = 1288 73491 , μ ∗ = 278369 12233622 . The maximizing envelope state is Δ = 400200 \Delta=400200 Δ = 400200
At this smaller base, the two endpoints use different centre branches:
ξ 0 = 5040 107 , θ : = ξ 0 − 2 1 − 2 / v = 4826 105 , 0 < μ ∗ < θ < b ≤ v . \xi_0=\frac{5040}{107},\qquad\theta:=\frac{\xi_0-2}{1-2/v}=\frac{4826}{105},\qquad0<\mu_*<\theta<b\le v. ξ 0 = 107 5040 , θ := 1 − 2/ v ξ 0 − 2 = 105 4826 , 0 < μ ∗ < θ < b ≤ v . Thus ξ ( μ ∗ ) = ξ 0 \xi(\mu_*)=\xi_0 ξ ( μ ∗ ) = ξ 0 ξ ( b ) = ( 1 − 2 / v ) b + 2 \xi(b)=(1-2/v)b+2 ξ ( b ) = ( 1 − 2/ v ) b + 2
F ( b ) = − 3130309743249 147056240800 < 0 , F(b)=-\frac{3130309743249}{147056240800}<0, F ( b ) = − 147056240800 3130309743249 < 0 , F ( μ ∗ ) = − 152269162897357 4649358009660 < 0. F(\mu_*)=-\frac{152269162897357}{4649358009660}<0. F ( μ ∗ ) = − 4649358009660 152269162897357 < 0. The centre join preserves values and slopes, as proved in Lemma A.13 ; hence its passage inside [ μ ∗ , b ] [\mu_*,b] [ μ ∗ , b ] μ ∗ \mu_* μ ∗
The base at t = 49 t=49 t = 49 Use the all-weight envelope E ^ T \widehat{E}_T E T
n = 269 , m = 219 , v = 73 , y = 24 , q = 149 , c = 37 , λ = 1. n=269,\quad m=219,\quad v=73,\quad y=24,\quad q=149,\quad c=37,\quad\lambda=1. n = 269 , m = 219 , v = 73 , y = 24 , q = 149 , c = 37 , λ = 1. Choose every cut of Lemma A.11 with 3 ≤ u ≤ 49 3\le u\le49 3 ≤ u ≤ 49 1 ≤ r ≤ min { u , 16 } 1\le r\le\min\{u,16\} 1 ≤ r ≤ min { u , 16 } ( 1 , 1 , d 0 ) (1,1,d_0) ( 1 , 1 , d 0 ) u = 0 , 1 , 2 , 3 u=0,1,2,3 u = 0 , 1 , 2 , 3
E = E ^ T = 50841725 2 , ρ = ρ 219 , 73 = 217 215 . E=\widehat{E}_T=\frac{50841725}{2},\qquad\rho=\rho_{219,73}=\frac{217}{215}. E = E T = 2 50841725 , ρ = ρ 219 , 73 = 215 217 . The remaining domains are q ≤ m q \le m q ≤ m m ≥ 4 t − 1 m \ge4t - 1 m ≥ 4 t − 1 n ≥ 4 t + 4 n \ge4t + 4 n ≥ 4 t + 4 t + 1 ≤ v ≤ 2 t t + 1 \le v \le2t t + 1 ≤ v ≤ 2 t 0 < ρ < v 0 < \rho< v 0 < ρ < v ρ \rho ρ Lemma A.13 ,
b = 131747 3379 , μ ∗ = 50841725 1703016 , 0 < μ ∗ < b ≤ v , b = \frac{131747}{3379}, \qquad\mu_* = \frac{50841725}{1703016}, \qquad0 < \mu_* < b \le v, b = 3379 131747 , μ ∗ = 1703016 50841725 , 0 < μ ∗ < b ≤ v , and the two certified values of (A.20) are
F ( μ ∗ ) = − 941079953521235 62581832506368 < 0 , F ( b ) = − 80139181023 8649854794 < 0. F(\mu_*) = -\frac{941079953521235}{62581832506368} < 0, \qquad F(b) = -\frac{80139181023}{8649854794} < 0. F ( μ ∗ ) = − 62581832506368 941079953521235 < 0 , F ( b ) = − 8649854794 80139181023 < 0. The centre is evaluated as the displayed maximum at each endpoint. The proof uses convexity on each side of μ ∗ \mu_* μ ∗
Proof of Theorem A.2. First suppose ν ( F ) = t \nu(\mathcal{F}) = t ν ( F ) = t
η t = min { − F ( μ ∗ ) μ ∗ , − F ( b ) b } > 0. \eta_t = \min\left\{-\frac{F(\mu_*)}{\mu_*},-\frac{F(b)}{b}\right\} > 0. η t = min { − μ ∗ F ( μ ∗ ) , − b F ( b ) } > 0. On each of the two intervals, F ′ ( μ ) + η t μ F'(\mu) + \eta_t\mu F ′ ( μ ) + η t μ
d t ( F ) ≥ η t ∣ A ∣ , γ t ( F ) ≤ ( c + 1 ) ∣ A ∣ ≤ c + 1 η t d t ( F ) . d_t(\mathcal{F}) \ge\eta_t|\mathcal{A}|,\qquad\gamma_t(\mathcal{F}) \le(c+1)|\mathcal{A}| \le\frac{c+1}{\eta_t}d_t(\mathcal{F}). d t ( F ) ≥ η t ∣ A ∣ , γ t ( F ) ≤ ( c + 1 ) ∣ A ∣ ≤ η t c + 1 d t ( F ) . The case A = ∅ \mathcal{A} = \varnothing A = ∅ γ t ( F ) = 0 \gamma_t(\mathcal{F}) = 0 γ t ( F ) = 0 t = 3480 t = 3480 t = 3480
max t c + 1 η t = 3445298291203325575600158052000 734432834661303950523791651 < 4692. \max_t \frac{c+1}{\eta_t} = \frac{3445298291203325575600158052000}{734432834661303950523791651} < 4692. t max η t c + 1 = 734432834661303950523791651 3445298291203325575600158052000 < 4692. For the additional base t = 2904 t = 2904 t = 2904
η 2904 = 206897019088563628476145569 135409701523544000906870000 , \eta_{2904} = \frac{206897019088563628476145569}{135409701523544000906870000}, η 2904 = 135409701523544000906870000 206897019088563628476145569 , 2179 η 2904 = 295057739619802377976069730000 206897019088563628476145569 < 1427. \frac{2179}{\eta_{2904}} = \frac{295057739619802377976069730000}{206897019088563628476145569} < 1427. η 2904 2179 = 206897019088563628476145569 295057739619802377976069730000 < 1427. At t = 888 t = 888 t = 888
η 888 = 21670567755141894005923 19500026868548619183900 , \eta_{888} = \frac{21670567755141894005923}{19500026868548619183900}, η 888 = 19500026868548619183900 21670567755141894005923 , 667 η 888 = 13006517921321928995661300 21670567755141894005923 < 601. \frac{667}{\eta_{888}} = \frac{13006517921321928995661300}{21670567755141894005923} < 601. η 888 667 = 21670567755141894005923 13006517921321928995661300 < 601. At t = 360 t = 360 t = 360
η 360 = 757621522106731369 889567883357596850 , \eta_{360} = \frac{757621522106731369}{889567883357596850}, η 360 = 889567883357596850 757621522106731369 , 271 η 360 = 241072896389908746350 757621522106731369 < 319. \frac{271}{\eta_{360}} = \frac{241072896389908746350}{757621522106731369} < 319. η 360 271 = 757621522106731369 241072896389908746350 < 319. At t = 72 t = 72 t = 72
η 72 = 1043436581083 2796922927700 , \eta_{72} = \frac{1043436581083}{2796922927700}, η 72 = 2796922927700 1043436581083 , 55 η 72 = 153830761023500 1043436581083 < 148. \frac{55}{\eta_{72}} = \frac{153830761023500}{1043436581083} < 148. η 72 55 = 1043436581083 153830761023500 < 148. At t = 49 t = 49 t = 49
η 49 = 7285380093 30659754622 , \eta_{49} = \frac{7285380093}{30659754622}, η 49 = 30659754622 7285380093 , 38 η 49 = 1165070675636 7285380093 < 160. \frac{38}{\eta_{49}} = \frac{1165070675636}{7285380093} < 160. η 49 38 = 7285380093 1165070675636 < 160. Lemma 2.1 extends each estimate to ν ( F ) ≤ t \nu(\mathcal{F}) \le t ν ( F ) ≤ t 1 + 2 K 1 + 2K 1 + 2 K
Lemma A.14 (Propagation from a cover base). Let t ≥ 33 t \ge33 t ≥ 33 a ≥ 4 t + 4 a \ge4t + 4 a ≥ 4 t + 4 n = a n = a n = a t t t n ≥ a n \ge a n ≥ a
Proof. Shift a family on n ≥ a + 1 n \ge a + 1 n ≥ a + 1 t t t t + 1 t + 1 t + 1 n − 1 − 3 ( t + 1 ) ≥ t + 1 n - 1 - 3(t + 1) \ge t + 1 n − 1 − 3 ( t + 1 ) ≥ t + 1 n n n n n n
∣ F ∣ ≤ B 4 ( n − 1 , t ) + B 3 ( n − 1 , t ) = B 4 ( n , t ) . |\mathcal{F}| \le B_4(n - 1,t) + B_3(n - 1,t) = B_4(n,t). ∣ F ∣ ≤ B 4 ( n − 1 , t ) + B 3 ( n − 1 , t ) = B 4 ( n , t ) . Proposition A.15 (Quantitative propagation). Let t ≥ 33 t \ge33 t ≥ 33 a ≥ 4 t + 4 a \ge4t + 4 a ≥ 4 t + 4 K ≥ 0 K \ge0 K ≥ 0 [ a ] [a] [ a ] t t t γ t ≤ K d t \gamma_t \le Kd_t γ t ≤ K d t n ≥ a n \ge a n ≥ a F \mathcal{F} F [ n ] [n] [ n ]
γ t ( F ) ≤ K ( n − t 4 ) ( a − t 4 ) d t ( F ) . \gamma_t(\mathcal{F}) \le K \frac{\binom{n-t}{4}}{\binom{a-t}{4}} d_t(\mathcal{F}). γ t ( F ) ≤ K ( 4 a − t ) ( 4 n − t ) d t ( F ) . Proof. For a ≤ j ≤ n a \le j \le n a ≤ j ≤ n F j = F ∩ ( [ j ] 4 ) \mathcal{F}_j = \mathcal{F} \cap\binom{[j]}{4} F j = F ∩ ( 4 [ j ] ) d j = B 4 ( j , t ) − ∣ F j ∣ d_j = B_4(j,t) - |\mathcal{F}_j| d j = B 4 ( j , t ) − ∣ F j ∣ γ j = ∣ F j ∖ C [ t ] ( j ) ∣ \gamma_j = |\mathcal{F}_j \setminus\mathcal{C}[t](j)| γ j = ∣ F j ∖ C [ t ] ( j ) ∣ t t t Lemma A.14 supplies its cover bound.
For j > a j > a j > a L j L_j L j j j j t t t t + 1 t + 1 t + 1 t + 1 t + 1 t + 1 j j j j − 1 − 3 ( t + 1 ) ≥ t + 1 j - 1 - 3(t + 1) \ge t + 1 j − 1 − 3 ( t + 1 ) ≥ t + 1
d j − d j − 1 = B 3 ( j − 1 , t ) − ∣ L j ∣ ≥ 0. d_j - d_{j-1} = B_3(j - 1,t) - |L_j| \ge0. d j − d j − 1 = B 3 ( j − 1 , t ) − ∣ L j ∣ ≥ 0. Let ℓ j \ell_j ℓ j L j L_j L j [ t ] [t] [ t ] T T T x ∈ [ j − 1 ] ∖ ( [ t ] ∪ T ) x \in[j - 1] \setminus([t] \cup T) x ∈ [ j − 1 ] ∖ ([ t ] ∪ T ) T ∪ { x } ∈ F j − 1 T \cup\{x\} \in\mathcal{F}_{j-1} T ∪ { x } ∈ F j − 1 j − t − 4 j - t - 4 j − t − 4 x x x
( j − t − 4 ) ℓ j ≤ 4 γ j − 1 , γ j = γ j − 1 + ℓ j ≤ j − t j − t − 4 γ j − 1 . (j - t - 4)\ell_j \le4\gamma_{j-1}, \qquad\gamma_j = \gamma_{j-1} + \ell_j \le\frac{j - t}{j - t - 4}\gamma_{j-1}. ( j − t − 4 ) ℓ j ≤ 4 γ j − 1 , γ j = γ j − 1 + ℓ j ≤ j − t − 4 j − t γ j − 1 . Multiplication from j = a + 1 j = a + 1 j = a + 1 n n n
γ n ≤ ( n − t 4 ) ( a − t 4 ) γ a ≤ K ( n − t 4 ) ( a − t 4 ) d a ≤ K ( n − t 4 ) ( a − t 4 ) d n . \gamma_n \le\frac{\binom{n-t}{4}}{\binom{a-t}{4}}\gamma_a \le K\frac{\binom{n-t}{4}}{\binom{a-t}{4}}d_a \le K\frac{\binom{n-t}{4}}{\binom{a-t}{4}}d_n. γ n ≤ ( 4 a − t ) ( 4 n − t ) γ a ≤ K ( 4 a − t ) ( 4 n − t ) d a ≤ K ( 4 a − t ) ( 4 n − t ) d n . The case n = a n = a n = a t t t
Applying Proposition A.15 to Theorems A.1 –A.2 proves Corollary A.4 ; the symmetric-difference identity is Lemma A.6. No new certificate is needed for this step.
Exact extremizers above the bases
Lemma A.16 (Propagation of shifted equality). Let t ≥ 33 t \ge33 t ≥ 33 a ≥ 4 t + 4 a \ge4t + 4 a ≥ 4 t + 4 t t t n ≥ a n \ge a n ≥ a C t \mathcal{C}_t C t t t t B 4 ( a , t ) B_4(a,t) B 4 ( a , t )
Proof. Induct on n > a n>a n > a F \mathcal{F} F ν ( F ) = t \nu(\mathcal{F})=t ν ( F ) = t ∣ F ∣ = B 4 ( n , t ) |\mathcal{F}|=B_4(n,t) ∣ F ∣ = B 4 ( n , t ) F 0 = F ∩ ( [ n − 1 ] 4 ) \mathcal{F}_0=\mathcal{F}\cap\binom{[n-1]}{4} F 0 = F ∩ ( 4 [ n − 1 ] ) L L L n n n ν ( F 0 ) = t \nu(\mathcal{F}_0)=t ν ( F 0 ) = t t t t n n n n > 4 t n>4t n > 4 t ν ( L ) ≤ t \nu(L)\le t ν ( L ) ≤ t
∣ F 0 ∣ + ∣ L ∣ ≤ B 4 ( n − 1 , t ) + B 3 ( n − 1 , t ) = B 4 ( n , t ) . |\mathcal{F}_0|+|L|\le B_4(n-1,t)+B_3(n-1,t)=B_4(n,t). ∣ F 0 ∣ + ∣ L ∣ ≤ B 4 ( n − 1 , t ) + B 3 ( n − 1 , t ) = B 4 ( n , t ) . Both inequalities must be equalities, so induction identifies F 0 \mathcal{F}_0 F 0 [ t ] [t] [ t ] E ∈ F E\in\mathcal{F} E ∈ F [ t ] [t] [ t ] n n n 3 t 3t 3 t [ n − 1 ] ∖ ( [ t ] ∪ ( E ∖ { n } ) ) [n-1]\setminus([t]\cup(E\setminus\{n\})) [ n − 1 ] ∖ ([ t ] ∪ ( E ∖ { n })) n ≥ 4 t + 4 n\ge4t+4 n ≥ 4 t + 4 3 t 3t 3 t [ t ] [t] [ t ] t t t F 0 \mathcal{F}_0 F 0 E E E F ⊆ C t \mathcal{F}\subseteq\mathcal{C}_t F ⊆ C t
Proof of Corollary A.3. The cover bound holds at all the stated bases by Theorems A.1–A.2, using shifting for arbitrary families. Lemma A.14 gives it at every larger ground set. At its maximum cardinality, matching number below t t t t t t
Only exact equality is transferred through arbitrary shifts. Quantitative stability for shifted families above a base is supplied by Proposition A.15, with its explicit binomial loss. The constants 2285, 4692, 1427, 601, 319, 148 and 160 remain estimates at their specified bases. These equality arguments use classical shifting and the local cover bounds.
Polynomial details for the uniform range
The two polynomial positivity checks in Proposition A.10 are transparent after translation:
P A ( 2200 + x ) = 3019933 x 3 + 19228355100 x 2 + 40755950097500 x + 28754097993750000 , P J ( 2200 + x ) = 23803113 x 4 + 209384508244 x 3 + 690694581174300 x 2 + 1012615286669630000 x + 556715897678850000000. \begin{aligned}
P_A(2200+x)&=3019933x^3+19228355100x^2\\
&\quad+40755950097500x+28754097993750000,\\
P_J(2200+x)&=23803113x^4+209384508244x^3\\
&\quad+690694581174300x^2+1012615286669630000x\\
&\quad+556715897678850000000.
\end{aligned} P A ( 2200 + x ) P J ( 2200 + x ) = 3019933 x 3 + 19228355100 x 2 + 40755950097500 x + 28754097993750000 , = 23803113 x 4 + 209384508244 x 3 + 690694581174300 x 2 + 1012615286669630000 x + 556715897678850000000. Every coefficient is positive. These are identities in the product extension of binomial coefficients.
The moment-margin derivation can be checked without a symbolic system. For example in the low-density row, y − = 29 t / 50 − 1 y_-=29t/50-1 y − = 29 t /50 − 1 y + = 29 t / 50 y_+=29t/50 y + = 29 t /50 b = 474 t / 625 b=474t/625 b = 474 t /625 w = 3 t / 4 + 3 / 2 w=3t/4+3/2 w = 3 t /4 + 3/2
M w ≥ t y − − w b − 2 t y + b 13 25 = 7 t ( 474 t − 124127 ) 296250 . M_w\ge ty_- -wb-\frac{2ty_+}{b}\frac{13}{25}=\frac{7t(474t-124127)}{296250}. M w ≥ t y − − w b − b 2 t y + 25 13 = 296250 7 t ( 474 t − 124127 ) . The high-density row uses b = 161 t / 200 b=161t/200 b = 161 t /200 w = 23 t / 32 + 1 w=23t/32+1 w = 23 t /32 + 1 155 / 316 155/316 155/316 b t + ( b − 2 t ) y + bt+(b-2t)y_+ b t + ( b − 2 t ) y +
