Abstract | ||
---|---|---|
We show that for infinitely many natural numbers k there are k-uniform hypergraphs which admit a ‘rescaling phenomenon’ as described in [10]. More precisely, let A(k,I,n) denote the class of k-graphs on n vertices in which the sizes of all pairwise intersections of edges belong to a set I. We show that if k=rt2 for some r≥1 and t≥2, and I is chosen in some special way, the densest graphs in A(rt2,I,n) are either dominated by stars of large degree, or basically, they are ‘t-thick’ rt2-graphs in which vertices are partitioned into groups of t vertices each and every edge is a union of tr such groups. It is easy to see that, unlike in stars, the maximum degree of t-thick graphs is of a lower order than the number of its edges. Thus, if we study the graphs from A(rt2,I,n) with a prescribed number of edges m which minimise the maximum degree, around the value of m which is the number of edges of the largest t-thick graph, a rapid, discontinuous phase transition can be observed. Interestingly, these two types of k-graphs determine the structure of all hypergraphs in A(rt2,I,n). Namely, we show that each such hypergraph can be decomposed into a t-thick graph HT, a special collection HS of stars, and a sparse ‘left-over’ graph HR. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1016/j.jcta.2018.06.009 | Journal of Combinatorial Theory, Series A |
Keywords | Field | DocType |
Hypergraphs,Decomposition,Intersection,Extremal set theory,Phase transition | Discrete mathematics,Natural number,Combinatorics,Phase transition,Vertex (geometry),Stars,Hypergraph,Constraint graph,Degree (graph theory),Mathematics,Path graph | Journal |
Volume | ISSN | Citations |
160 | 0097-3165 | 0 |
PageRank | References | Authors |
0.34 | 4 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tomasz Łuczak | 1 | 225 | 40.26 |
joanna polcyn | 2 | 10 | 5.79 |
Christian Reiher | 3 | 3 | 4.49 |