Quadruple systems with independent neighborhoods

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:115

Article

Furedi, Zoltan^1,2  Mubayi, Dhruv³  Pikhurko, Oleg⁴ 

[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[2] Hungarian Acad Sci, Renyi Inst Math, Budapest, Hungary

[3] Univ Illinois, Dept Math Stat & Comp Sci, Chicago, IL 60607 USA

[4] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

关键词: k-Graph;    Turan problem;    Independent neighborhoods;   

DOI  :  10.1016/j.jcta.2008.01.008

来源: Elsevier

【 摘 要 】

A 4-graph is odd if its vertex set can be partitioned into two sets so that every edge intersects both parts in an odd number of points. Let [GRAPHICS] denote the maximum number of edges in an n-vertex odd 4-graph. Let n be sufficiently large, and let G be an n-vertex 4-graph such that for every triple xyz of vertices, the neighborhood N(xyz) = {w:wxyz is an element of G} is independent. We prove that the number of edges of G is at most b(n). Equality holds only if G is odd with the maximum number of edges. We also prove that there is epsilon > 0 such that if the 4-graph G has minimum degree at least (1/2 - epsilon) ((n)(3)), then G is 2-colorable. Our results can be considered as a generalization of Mantel's theorem about triangle-free graphs, and we pose a conjecture about k-graphs for larger k as well. Published by Elsevier Inc.

【 授权许可】

Free