A generalization of Talbot's theorem about King Arthur and his Knights of the Round Table

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:116

Article

Hilton, A. J. W.^1,2  Spencer, C. L.² 

[1] Queen Mary Univ London, Sch Math Sci, London E1 4NS, England

[2] Univ Reading, Dept Math, Reading RG6 6AX, Berks, England

关键词: Finite sets;    Erdos-Ko-Rado;    Intersection theorem;    Cycles;    Graph theory;    Independent sets;    King Arthur;    Round Table;   

DOI  :  10.1016/j.jcta.2009.02.001

来源: Elsevier

【 摘 要 】

Let G be a graph consisting of powers of disjoint cycles and let A be an intersecting family of independent r-sets of vertices. Provided that G satisfies a further condition related to the clique numbers of the powers of the cycles, then vertical bar A vertical bar will be as large as possible if it consists of all independent r-sets containing one vertex from a specified cycle. Here r can take any value, 1 <= r <= alpha(G), where alpha(G) is the independence number of G. This generalizes a theorem of Talbot dealing with the case when G consists of a cycle of order n raised to the power k. Talbot showed that vertical bar A vertical bar <= (n-kr-1 r-1). (C) 2009 Elsevier Inc. All rights reserved.

【 授权许可】

Free