2025/10/25 by Carrion, Michael, Fuentes, Melissa M., Joseph, Zaphenath +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2510.22103
The classical Erdős--Ko--Rado (EKR) theorem characterizes the maximum size of intersecting families of r-element subsets of an n-element set. We study EKR-type questions for independent r-sets in pendant graph constructions, obtained by attaching to each base vertex a clique of prescribed size. Our contributions are threefold. We give an alternate and purely combinatorial proof (via shifting and shadows) that the pendant complete graph Kn* is r-EKR for n ≥ 2r, and strictly so for n>2r, recovering a result of De Silva, Dionne, Dunkelberg, and Harris. We extend this to generalized pendant complete graphs, where every base vertex in the clique supports a clique of arbitrary size, proving that that generalized pendant complete graphs are r-EKR whenever n ≥ 2r. For pendant paths Pn*, we provide elementary constructions showing that Pn* is not (n-k)-EKR when n ≥ 3k+2 for k≥ 2, not (n-1)-EKR for n≥ 6, and not n-EKR for n≥ 4. These results fit naturally into the Holroyd--Talbot perspective relating r-EKR thresholds to independence parameters and supply tools for further pendant constructions.