Pith. sign in

REVIEW 4 cited by

Intersection theorems for uniform subfamilies of hereditary families

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2311.02246 v1 pith:LRSIS2GL submitted 2023-11-03 math.CO

classification math.CO
keywords familysetsintersectinghereditarymathcalelementborgcontaining
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

A family $\mathcal C$ of sets is hereditary if whenever $A\in \mathcal C$ and $B\subset A$, we have $B\in \mathcal C$. Chv\'atal conjectured that the largest intersecting subfamily of a hereditary family is the family of all sets containing a fixed element. This is a generalization of the non-uniform Erd\H{o}s-Ko-Rado theorem. A natural uniform variant of this question, which is essentially a generalization for the uniform Erd\H{o}s-Ko-Rado theorem, was suggested by Borg: given a hereditary family $\mathcal C$, in which all maximal sets have size at least $n$, what is the largest intersecting subfamily of the family of all $k$-element sets in $\mathcal C$? The answer, of course, depends on $n$ and $k$, and Borg conjectured that for $n\ge 2k$ the it is again the family of all $k$-element sets containing a singleton. Borg proved this conjecture for $n\ge k^3$. He also considered a $t$-intersecting variant of the question. In this paper, we improve the bound on $n$ for both intersecting and $t$-intersecting cases, showing that for $n\ge Ckt\log^2\frac nk$ and $n\ge Ck\log k$ the largest $t$-intersecting subfamily of the $k$-th layer of a hereditary family with maximal sets of size at least $n$ is the family of all sets containing a fixed $t$-element set. We also prove a stability result.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

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

  1. The Hajnal--Rothschild problem

    math.CO 2025-02 conditional novelty 8.0 of 10

    For large n, every extremal family with no s+1 pairwise <t-intersecting k-sets is a union of s t-intersecting cliques, as predicted by the Ahlswede-Khachatrian analogy.

  2. A complete $t$-intersection theorem for families of spanning trees

    math.CO 2025-07 conditional novelty 7.0 of 10

    For n large and 2≤t≤n−2, every t-intersecting family of spanning trees of K_n has size at most c_{n,t} n^{n−2−t}, with equality exactly for the trivial family containing a balanced fixed forest.

  3. Satisfying sequences for rainbow partite matchings

    math.CO 2025-02 conditional novelty 7.0 of 10

    For k-partite hypergraphs, the paper proves near-optimal asymmetric size thresholds that force rainbow matchings and shows a truncated arithmetic progression is not always satisfying.

  4. Intersecting Families of Spanning Trees

    math.CO 2025-02 conditional novelty 4.0 of 10

    For large n and moderate t, the largest t-intersecting family of spanning trees of K_n is the family of all trees containing a fixed set of t disjoint edges, with stars added when t=1.

Pith tools