Intersection-preserving lexicographic UV-compression

ID: intersection-preserving-lexicographic-uv-compression

Let be disjoint, equally sized, nonempty sets, with . Suppose an intersecting family is unchanged by all such UV-compressions of smaller size. Then its -UV-compression is still an intersecting family. Indeed, a newly moved member can only be disjoint from a retained old member , since two newly moved members share . Here and . If , retaining forces to have been present, contradicting the old intersection property with . Otherwise choose with and . Stability under the smaller -UV-compression forces to be present; this member is disjoint from , again a contradiction. Repeatedly applying a changing UV-compression of smallest size terminates, since the sum of lexicographic order positions decreases. A terminal set family is a lexicographic initial segment: a missing earlier member and present later member would be moved by , .

New to topics? Read the docs here!