pith. sign in

arxiv: 2502.06699 · v1 · pith:XWW4N5QCnew · submitted 2025-02-10 · 🧮 math.CO · cs.DM

The Hajnal--Rothschild problem

classification 🧮 math.CO cs.DM
keywords mathcalfamilylargestldotsthereapproximationconstructionsextremal
0
0 comments X
read the original abstract

For a family $\mathcal F$ define $\nu(\mathcal F,t)$ as the largest $s$ for which there exist $A_1,\ldots, A_{s}\in \mathcal F$ such that for $i\ne j$ we have $|A_i\cap A_j|< t$. What is the largest family $\mathcal F\subset{[n]\choose k}$ with $\nu(\mathcal F,t)\le s$? This question goes back to a paper Hajnal and Rothschild from 1973. We show that, for some absolute $C$ and $n>2k+Ct^{4/5}s^{1/5}(k-t)\log_2^4n$, $n>2k+Cs(k-t)\log_2^4 n$ the largest family with $\nu(\mathcal F,t)\le s$ has the following structure: there are sets $X_1,\ldots, X_s$ of sizes $t+2x_1,\ldots, t+2x_s$, such that for any $A\in \mathcal F$ there is $i\in [s]$ such that $|A\cap X_i|\ge t+x_i$. That is, the extremal constructions are unions of the extremal constructions in the Complete $t$-Intersection Theorem. For the proof, we enhance the spread approximation technique of Zakharov and the second author. In particular, we introduce the idea of iterative spread approximation.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A Complete Intersection Theorem for Large Permutation Groups

    math.CO 2026-07 unverdicted novelty 8.0

    Proves that for sufficiently large n the maximum t-intersecting families in S_n are the fixed-point families F_{n,t,r}, resolving the Deza-Frankl problem asymptotically.

  2. Forbidden Intersection Theorems for Matrix Spaces

    math.CO 2026-06 unverdicted novelty 7.0

    For t < c n the only maximal (t-1)-intersection-free families in GL(n,q) are the t-umvirates and their duals.

  3. Matchings in permutations

    math.CO 2026-05 unverdicted novelty 4.0

    Largest s-matching-free families of permutations are characterized, with a Hilton-Milner type theorem and results for derangements.