Abstract | ||
---|---|---|
Given a family of r-uniform hypergraphs F (or r-graphs for brevity), the Turan number ex(n, F) of F is the maximum number of edges in an r-graph on n vertices that does not contain any member of F. A pair {u, v} is covered in a hypergraph G if some edge of G contains {u, v}. Given an rgraph F and a positive integer p >= n(F), where n(F) denotes the number of vertices in F, let H-p(F) denote the r-graph obtained as follows. Label the vertices of F as v1,..., v n(F). Add new vertices v(n(F)+1),..., vp. For each pair of vertices v(i), v(j) not covered in F, add a set B-i,(j) of r - 2 new vertices and the edge {v(i), v(j)}U B-i,B- j, where the B-i,B- j are pairwise disjoint over all such pairs {i, j}. We call H-p(F) the expanded p-clique with an embedded F. For a relatively large family of F, we show that for all sufficiently large n, ex(n, H-p(F)) = | T-r(n, p - 1)|, where T-r(n, p - 1) is the balanced complete (p - 1)-partite r-graph on n vertices. We also establish structural stability of near-extremal graphs. Our results generalize or strengthen several earlier results and provide a class of hypergraphs for which the Turan number is exactly determined (for large n). |
Year | DOI | Venue |
---|---|---|
2017 | 10.1017/S0963548316000444 | COMBINATORICS PROBABILITY & COMPUTING |
Field | DocType | Volume |
Integer,Discrete mathematics,Graph,Combinatorics,Disjoint sets,Vertex (geometry),Hypergraph,Constraint graph,Mathematics | Journal | 26 |
Issue | ISSN | Citations |
3 | 0963-5483 | 3 |
PageRank | References | Authors |
0.43 | 10 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
axel brandt | 1 | 3 | 0.43 |
David E. Irwin | 2 | 899 | 98.12 |
Tao Jiang | 3 | 63 | 8.69 |