Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
| Autor: | Borg, Peter |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A family $\mathcal{A}$ of sets is said to be intersecting if every two sets in $\mathcal{A}$ intersect. Two families $\mathcal{A}$ and $\mathcal{B}$ are said to be cross-intersecting if each set in $\mathcal{A}$ intersects each set in $\mathcal{B}$. For a positive integer $n$, let $[n] = \{1, \dots, n\}$ and $\mathcal{S}_n = \{A \subseteq [n] \colon 1 \in A\}$. In this note, we extend the Erd\H{o}s-Ko-Rado Theorem by showing that if $\mathcal{A}$ and $\mathcal{B}$ are non-empty cross-intersecting families of subsets of $[n]$, $\mathcal{A}$ 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 $i \leq n/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 $\{A \in {\mathcal{I}_G}^{(r)} \colon v \in A\}$ is a largest intersecting subfamily of ${\mathcal{I}_G}^{(r)}$. They proved this for $r \leq \frac{n+1}{2}$. We use the result above to prove the full conjecture. Comment: 8 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|