Name
Abstract | ||
|---|---|---|
Given a family of 3-graphs F, we define its codegree threshold coex(n, F) to be the largest number d = d(n) such that there exists an n-vertex 3-graph in which every pair of vertices is contained in at least d 3-edges but which contains no member of F as a subgraph. Let F-3,F-2 be the 3-graph on {a, b, c, d, e} with 3-edges abc, abd, abe, and cde. In this paper, we give two proofs that coex(n, {F-3,F-2}) = - (1/3 + o(1))n, the first by a direct combinatorial argument and the second via a flag algebra computation. Information extracted from the latter proof is then used to obtain a stability result, from which in turn we derive the exact codegree threshold for all sufficiently large n: coex(n, {F-3,F-2}) = [n/3] - 1 if n is congruent to 1 modulo 3, and [n/3] otherwise. In addition we determine the set of codegree-extremal configurations for all sufficiently large n. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1137/130926997 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
codegree,Turan density,Turan function,3-graphs | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Modulo,Congruence (geometry),Mathematics | Journal |
Volume | Issue | ISSN |
29 | 3 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Victor Falgas-Ravry | 1 | 28 | 7.46 |
| Edward Marchant | 2 | 0 | 0.34 |
| Oleg Pikhurko | 3 | 318 | 47.03 |
| Emil R. Vaughan | 4 | 40 | 3.49 |