On the Holroyd-Talbot conjecture for sparse graphs

DOI10.1016/J.DISC.2023.113742MaRDI QIDQ6056471zbMATH OpenFDO

Authors Peter Frankl, Glenn H. Hurlbert

Publication date 30 October 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.01661

zbMATH Keywords

Erdős-Ko-Rado theoremHolroyd-Talbot conjectureintersecting family

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Extremal set theory (05D05)

Abstract: Given a graph $G$, let $mu(G)$ denote the size of the smallest maximal independent set in $G$. A family of subsets is called a star if some element is in every set of the family. A split vertex has degree at least 3. Holroyd and Talbot conjectured the following ErdH{o}s-Ko-Rado type statement about intersecting families of independent sets in graphs: if $1lerlemu(G)/2$ then there is an intersecting family of independent $r$-sets of maximum size that is a star. In this paper we prove similar statements for sparse graphs on $n$ vertices: roughly, for graphs of bounded average degree with $rleO(n^{1/3})$, for graphs of bounded degree with $rleO(n^{1/2})$, and for trees having a bounded number of split vertices with $rleO(n^{1/2})$.

Recommendations

• Erdös-Ko-Rado theorems for a family of trees
• On intersecting families of independent sets in trees
• The Erdős-Ko-Rado properties of various graphs containing singletons
• An Erdős-Ko-Rado theorem for unions of length 2 paths
• Very well-covered graphs with the Erdős-Ko-Rado property

Cites work

• A new result on Chvátal's conjecture
• An Erdős-Ko-Rado theorem for signed sets
• An Erdős-Ko-Rado theorem for unions of length 2 paths
• An intersection theorem for weighted sets
• Compression and Erdős-Ko-Rado graphs
• Erdös-Ko-Rado theorems for a family of trees
• Erdös–Ko–Rado Theorem—22 Years Later
• Erdős-Ko-Rado theorems for chordal graphs and trees
• Extremal t -intersecting sub-families of hereditary families
• Graphs with the Erdős-Ko-Rado property
• scientific article; zbMATH DE number 3477225 (Why is no real title available?)
• INTERSECTING FAMILIES OF SEPARATED SETS
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Maximum degree and diversity in intersecting hypergraphs
• On intersecting families of independent sets in trees
• On stars in caterpillars and lobsters
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Stars on trees
• The Erdős-Ko-Rado properties of set systems defined by double partitions
• The Erdős-Ko-Rado properties of various graphs containing singletons

This page was built for publication: On the Holroyd-Talbot conjecture for sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6056471)