Quadruple systems with independent neighborhoods (Q958757): Difference between revisions

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_\alpha\left\{\alpha{n-\alpha\choose 3}+(n-\alpha){\alpha\choose 3}\right\}=\left(\tfrac12+o(1)\right){n\choose 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(xyz)=\{w:wxyz\in 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 \(\varepsilon >0\) such that if the 4-graph \(G\) has minimum degree at least \((1/2-\varepsilon){n\choose 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.