Name
Abstract | ||
|---|---|---|
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. Letb(n)=maxα{α(n−α3)+(n−α)(α3)}=(12+o(1))(n4) 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∈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−ε)(n3), then G is 2-colorable. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.jcta.2008.01.008 | Journal of Combinatorial Theory, Series A |
Keywords | Field | DocType |
k-Graph,Turán problem,Independent neighborhoods | Discrete mathematics,Graph,Combinatorics,Monad (category theory),Vertex (geometry),Parity (mathematics),Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
115 | 8 | 0097-3165 |
Citations | PageRank | References |
8 | 0.65 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zoltan Füredi | 1 | 31 | 2.75 |
| Dhruv Mubayi | 2 | 579 | 73.95 |
| Oleg Pikhurko | 3 | 318 | 47.03 |