Quadruple systems with independent neighborhoods

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 b ( n ) = max α { α ( n − α 3 ) + ( n − α ) ( α 3 ) } = ( 1 2 + o ( 1 ) ) ( n 4 ) 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 ( x y z ) = { w : w x y z ∈ 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 ε > 0 such that if the 4-graph G has minimum degree at least ( 1 / 2 − ε ) ( n 3 ) , then G is 2-colorable. sults 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.