Point frequencies for generators with large incidence girth

What Lean checks

The all-point high-girth bound is checked for every k ≥ 3: incidence girth at least 16 and exactly three generators through each point imply frequency at least 518208/1000000 among distinct unions. The k ≥ 15 linear-family bound is also checked with frequency 657/1000. Both include the empty union. The complete Vaughan shortcut, small-cycle cases, local checker semantics, and conditional all-period assembly are checked. The remaining cyclic span-four graph/transport certificates and unconditional assembly are still being verified.

This entry is a partial result on an open problem. It does not claim a solution of the general conjecture.

Let each generator be a kk-element set, with k≥3k\ge3, and let each ground point occur in exactly three generators. Form their bipartite incidence graph, with an edge for membership. If its shortest cycle has length at least 16, every point belongs to at least 0.518208 of the distinct unions. The empty union is included. Omitting it can only increase the frequencies. For k≥15k\ge15 it suffices that two different generators intersect in at most one point, and the lower bound improves to 0.657.

Counting unions by tree recursion for small generators

For a union UU, take the points outside UU and all generators contained in UU. They form a maximal independent set of the incidence graph. Conversely, maximality forces every generator avoiding the selected points to be selected itself, and every unselected point to belong to at least one selected generator. These maps are inverse. A point is absent from a uniformly chosen union exactly when it is occupied in the uniform maximal independent set. Bruhn, Charbit, Schaudt and Telle develop this correspondence and prove the existential statement for subcubic bipartite graphs, which includes the cubic case here. Our bound in that case applies separately to each point under the girth hypothesis. Bruhn, Charbit, Schaudt and Telle

Fix a point as root. Its radius-seven ball is a tree, since an extra edge or a second shortest path would give a cycle of length at most 15. Condition on the occupied vertices at distances seven and greater in any configuration that extends to a maximal independent set. A boundary vertex has one of three forced states: occupied, unoccupied and already dominated from outside, or unoccupied and requiring its parent. These correspond respectively to the coordinate rays of (a,b,c)(a,b,c). Conditioning also fixes whether every exterior vertex is dominated. Branch counts therefore multiply.

In an interior branch let aa count the choices with the top vertex occupied, bb the unoccupied choices dominated by children, and cc the unoccupied choices that require the parent. If the child triples are (ai,bi,ci)(a_i,b_i,c_i), then

a=∏i(bi+ci),b=∏i(ai+bi)−∏ibi,c=∏ibi.a=\prod_i(b_i+c_i),\quad b=\prod_i(a_i+b_i)-\prod_i b_i,\quad c=\prod_i b_i.

At the actual root the probability of occupation is a/(a+b)a/(a+b) because no parent is available.

Starting with the three boundary rays, propagate cones of possible triples for six levels. Points below the root have two children and generators have k−1k-1. For each child form (u,v,w)=(b+c,a+b,b)(u,v,w)=(b+c,a+b,b) and multiply these transformed vectors coordinate by coordinate. The product is linear in each input when the others are fixed, so all products are contained in the cone generated by products of extreme rays. Taking the cone after each multiplication preserves this containment. Finally map a product (p,q,r)(p,q,r) to (p,q−r,r)(p,q-r,r). The verifier normalizes rays by coordinate sum and finds their planar convex hull using integer determinants.

Let PP be the resulting generator-side cone at distance one. For each extreme ray take

(b+c)3(b+c)3+(a+b)3−b3,\frac{(b+c)^3}{(b+c)^3+(a+b)^3-b^3},

and let RR be the maximum. The checker uses positive denominators. This bounds occupation even for three different children: on every ray, ((1−R)u3+Rw3)1/3≤R1/3v((1-R)u^3+Rw^3)^{1/3}\le R^{1/3}v. The triangle inequality for the weighted ℓ3\ell^3 norm extends the inequality to the cone. Hölder's inequality applied to the three two-entry vectors then gives (1−R)∏iui+R∏iwi≤R∏ivi(1-R)\prod_i u_i+R\prod_i w_i\le R\prod_i v_i, precisely the bound on root occupation. Averaging over exterior configurations preserves the bound.

For k=3,…,14k=3,\ldots,14, the upper bounds in millionths, rounded upwards, are 481792, 478679, 461724, 426826, 385225, 343032, 303914, 269665, 240799, 217078, 197903 and 182564. The largest gives the stated lower bound on frequency. Exact cone computation

Counting by canonical generator selections for large generators

Independently select each generator with probability 1/21/2. For a generator ee let BeB_e be the event that ee was omitted but is covered by the selected union. Avoiding all these events makes the selected generators exactly those contained in their union. Each distinct union has precisely one such selection, hence the conditional distribution on unions is uniform.

Suppose different generators meet in at most one point. Conditional on omitting ee, its kk points each have two other incident generators and are independently covered with probability 3/43/4. Thus p=Pr(Be)=12(3/4)kp=\Pr(B_e)=\frac12(3/4)^k. Give BeB_e as neighbors the at most D=2kD=2k events indexed by generators meeting ee.

For any collection of nonneighbors, conditioning on their avoidance cannot increase Pr(Be)\Pr(B_e). To see this, first fix the bits outside the support of BeB_e. Nonneighbor avoidance is independent of the bit of ee and decreases in the other support bits: those bits can cover a nonneighbor but never index one in the collection. After averaging over the bit of ee, the probability of BeB_e increases in those same coordinates. Oppositely monotone functions of independent bits have nonpositive covariance (by induction on the coordinates). Integrate over the fixed outside bits, which do not change the unconditional probability of BeB_e.

If p≤x(1−x)Dp\le x(1-x)^D, it follows by induction on the conditioning set that Pr(Be∣avoid any other events)≤x\Pr(B_e\mid\text{avoid any other events})\le x. Indeed first condition on the nonneighbors, bound the numerator by pp, and lower-bound the probability of also avoiding the neighbors by the product of their conditional avoidance probabilities, each at least 1−x1-x by the smaller-set induction. When there are no neighbors in the set, the preceding monotonicity bound applies directly. All conditioning events have positive probability because selecting all generators avoids every bad event.

Take x=2/(7D)x=2/(7D). Bernoulli's inequality gives (1−x)D≥5/7(1-x)^D\ge5/7. The sufficient test D(3/4)k≤20/49D(3/4)^k\le20/49 holds at k=15k=15 by exact arithmetic and decreases thereafter since the ratio is 3(k+1)/(4k)<13(k+1)/(4k)<1. Before conditioning, a fixed point is absent with probability 1/81/8. Only events reading one of its three incident bits affect this query, at most 3[1+2(k−1)]≤3D3[1+2(k-1)]\le3D in total. Condition first on avoiding the remaining events, which are jointly independent of the three bits. Avoiding the events that do read those bits has conditional probability at least (1−x)3D(1-x)^{3D} by the induction. Dividing gives an absence probability of at most (1/8)(7/5)3=343/1000(1/8)(7/5)^3=343/1000.

Incidence girth at least 16 implies the pairwise intersection condition since two common points give a 4-cycle. The two arguments cover all k≥3k\ge3. Arbitrary union-closed families need not have generators with either of the regularity assumptions used here.