EKR-Type Theorems for Pendant Graph Constructions
Michael Carrion, Melissa M. Fuentes, Zaphenath Joseph, Alexander Nappo · 2025
Read EKR-Type Theorems for Pendant Graph Constructions by Michael Carrion, Melissa M. Fuentes, Zaphenath Joseph, Alexander Nappo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22103.txt.
Description
Michael Carrion, Melissa M. Fuentes, Zaphenath Joseph, and Alexander Nappo revisit a classic question about families that all overlap. The Erdős–Ko–Rado theorem caps the size of a family of same-sized subsets that pairwise share an element. The team asks the analogous question for independent sets inside pendant graphs, networks made by hanging a clique of chosen size off every vertex of a base graph.
They give a fresh, purely combinatorial proof, using shifting and shadow arguments, that the pendant complete graph meets the bound whenever the base is at least twice the set size. Strictly so beyond that, then extend the result to pendants whose attached cliques vary in size. For pendant paths the story flips: careful constructions show the property fails in several ranges. The paper maps where the classical behavior survives decoration and where it breaks.
Catalog record
| CREATOR | Michael Carrion, Melissa M. Fuentes, Zaphenath Joseph, Alexander Nappo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-22103