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
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.
Forward citations
Cited by 4 Pith papers
-
The Hajnal--Rothschild problem
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.
-
A complete $t$-intersection theorem for families of spanning trees
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.
-
Satisfying sequences for rainbow partite matchings
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.
-
Intersecting Families of Spanning Trees
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.
Discussion (0). Continue with ORCID to comment.