Unavoidable subhypergraphs: a-clusters

Fueredi Z. , Oezkahya L.

JOURNAL OF COMBINATORIAL THEORY SERIES A, cilt.118, sa.8, ss.2246-2256, 2011 (SCI İndekslerine Giren Dergi) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 118 Konu: 8
  • Basım Tarihi: 2011
  • Doi Numarası: 10.1016/j.jcta.2011.05.002
  • Sayfa Sayıları: ss.2246-2256


One of the central problems of extremal hypergraph theory is the description of unavoidable subhypergraphs, in other words, the Turan problem. Let a = (a(1), ... , a(p)) be a sequence of positive integers, k = a(1) + ... + a(p). An a-partition of a k-set F is a partition in the form F = A(1) boolean OR ... boolean OR A(p) with vertical bar A(i)vertical bar = a(i) for 1 <= i <= p. An a-cluster A with host F(0) is a family of k-sets {F(0), ... , F(p)} such that for some a-partition of F(0), F(0) boolean AND F(i) = F(0) \ A(i) for 1 <= i <= p and the sets F(1) \ F(0) are pairwise disjoint. The family A has 2k vertices and it is unique up to isomorphisms. With an intensive use of the delta-system method we prove that for k > p and sufficiently large n, if F is a k-uniform family on n vertices with vertical bar F vertical bar exceeding the Erdos-Ko-Rado bound ((n-1)(k-1)), then,F contains an a-cluster. The only extremal family consists of all the k-subsets containing a given element. Published by Elsevier Inc.