Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas

DOI10.1016/J.DISC.2018.02.004zbMATH Open1383.05303arXiv1706.05537OpenAlexW2963982428WikidataQ123002608 ScholiaQ123002608MaRDI QIDQ1709533FDOQ1709533

Authors: Peter Borg 

Publication date: 5 April 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A family $mathcalA$ of sets is said to be intersecting if every two sets in $mathcalA$ intersect. Two families $mathcalA$ and $mathcalB$ are said to be cross-intersecting if each set in $mathcalA$ intersects each set in $mathcalB$. For a positive integer $n$, let $[n]=1,dots,n$ and $mathcal{S}_n=Asubseteq[n]colon1inA$. In this note, we extend the ErdH{o}s-Ko-Rado Theorem by showing that if $mathcalA$ and $mathcalB$ are non-empty cross-intersecting families of subsets of $[n]$, $mathcalA$ is intersecting, and $a_0,a_1,dots,a_n,b_0,b_1,dots,b_n$ are non-negative real numbers such that $a_i+b_{i}geq{a}_{n-i}+b_{n-i}$ and $a_{n-i}geq{b}_i$ for each $ileqn/2$, then [sum_{A in mathcal{A}} a_{|A|} + sum_{B in mathcal{B}} b_{|B|} leq sum_{A in mathcal{S}_n} a_{|A|} + sum_{B in mathcal{S}_n} b_{|B|}.] For a graph $G$ and an integer $r$, let ${mathcal{I}_G}^{(r)}$ denote the family of $r$-element independent sets of $G$. Inspired by a problem of Holroyd and Talbot, Feghali, Johnson and Thomas conjectured that if $r<n$ and $G$ is a depth-two claw with $n$ leaves, then $G$ has a vertex $v$ such that $Ain{mathcal{I}_G}^{(r)}colonvinA$ is a largest intersecting subfamily of ${mathcal{I}_G}^{(r)}$. They proved this for $rleqfracn+12$. We use the result above to prove the full conjecture.

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

Recommendations

• On cross-intersecting families of independent sets in graphs
• The maximum product of sizes of cross-intersecting families
• An Erdős-Ko-Rado theorem for cross \(t\)-intersecting families
• Cross-intersecting subfamilies of levels of hereditary families
• Sharp results concerning disjoint cross-intersecting families

zbMATH Keywords

intersecting familycross-intersecting familiesFeghali-Johnson-Thomas conjectureErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complete intersection theorem for systems of finite sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Intersection theorems for systems of finite sets
• Title not available (Why is that?)
• The exact bound in the Erdős-Ko-Rado theorem
• On \(t\)-intersecting families of signed sets and permutations
• An Erdős-Ko-Rado theorem for signed sets
• Erdős-Ko-Rado from Kruskal-Katona
• A simple proof of the Erdős-Chao Ko-Rado theorem
• Erdös–Ko–Rado Theorem—22 Years Later
• A Group-Theoretic Setting for Some Intersecting Sperner Families
• An Erdős-Ko-Rado theorem for the subcubes of a cube
• The Erdős-Ko-Rado properties of various graphs containing singletons
• The Erdős-Ko-Rado properties of set systems defined by double partitions
• Compression and Erdős-Ko-Rado graphs
• Graphs with the Erdős-Ko-Rado property
• Erdős-Ko-Rado theorems for chordal graphs and trees
• Erdős-Ko-Rado theorems for simplicial complexes
• Extremal t -intersecting sub-families of hereditary families
• Title not available (Why is that?)
• The maximum sum and the maximum product of sizes of cross-intersecting families
• A cross‐intersection theorem for subsets of a set
• Invitation to intersection problems for finite sets
• A generalization of Talbot's theorem about King Arthur and his knights of the round table
• The maximum product of weights of cross-intersecting families
• King Arthur and his knights with two round tables
• INTERSECTING FAMILIES OF SEPARATED SETS
• Stars on trees
• The maximum product of sizes of cross-intersecting families
• Erdös-Ko-Rado theorems for a family of trees

Cited In (7)

• Restricted intersecting families on simplicial complex
• \(K_4\)-intersecting families of graphs
• The number of \(s\)-separated \(k\)-sets in various circles
• The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
• Cross‐intersecting couples of graphs
• Towards extending the Ahlswede-Khachatrian theorem to cross \(t\)-intersecting families
• On cross-intersecting families of independent sets in graphs

This page was built for publication: Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas

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