Sizes of cross-intersecting families
math.CO
Submitted: 2026-10-28
Updated: 2026-10-28
License: http://creativecommons.org/licenses/by/4.0/
The gist: The size of cross-intersecting families F 1,, F d is usually measured by the sum or the product of the sizes F i.
Abstract
The size of cross-intersecting families F 1,, F d is usually measured by the sum or the product of the sizes F i. These two natural size functions have different extremal structures, and different techniques have been developed for them. We introduce the cross-degree of a size function and show that the potential extremal structures of maximum cross-intersecting families are the same for all size functions of finite cross-degree, including the sum and the product. Our main tool is a strengthened form of the generating family method of Ahlswede--Khachatrian, based on standard generating families and on local modifications of cross-intersecting families, which we call mutations. It treats two completely different types of extremal structures in a unified way and, unlike the original method, needs shifting in only one step.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality