Abstract:A family of sets is intersecting if every pair of its members has an element in common. Such a family of sets is called a star if some element is in every set of the family. Given a graph $G$, let $\mu(G)$ denote the size of the smallest maximal independent set of $G$. In 2005, Holroyd and Talbot conjectured the following generalization of the Erdős-Ko-Rado Theorem: for $1\le r\le \mu(G)/2$, there is a maximum size intersecting family of independent $r$-sets that is a star. In this paper we present the history of this conjecture and survey the results that have supported it over the last 20 years.
From: Glenn Hurlbert [view email]
[v1]
Mon, 27 Jan 2025 15:37:40 UTC (22 KB)
[v2]
Sun, 9 Feb 2025 02:24:35 UTC (22 KB)
[v3]
Sun, 8 Jun 2025 17:36:32 UTC (23 KB)
[v4]
Sat, 22 Aug 2026 23:09:31 UTC (23 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。