## A tale of stars and cliques

### Authors:

- Tomasz Łuczak,
- Joanna Polcyn-Lewandowska,
- Christian Reiher

### 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=rt^{2} for some r≥1 and t≥2, and I is chosen in some special way, the densest graphs in A(rt^{2},I,n) are either dominated by stars of large degree, or basically, they are ‘t-thick’ rt^{2}-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(rt^{2},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(rt^{2},I,n). Namely, we show that each such hypergraph can be decomposed into a t-thick graph H_{T}, a special collection H_{S} of stars, and a sparse ‘left-over’ graph H_{R}.

- Record ID
- UAM1c156d2520b7466b9718a2791f0480b4
- Author
- Journal series
- Journal of Combinatorial Theory Series A, ISSN 0097-3165
- Issue year
- 2018
- Vol
- 160
- Pages
- 111-135
- Publication size in sheets
- 1.20
- ASJC Classification
- ; ;
- DOI
- DOI:10.1016/j.jcta.2018.06.009 opening in a new tab
- Language
- en English
- Score (nominal)
- 35
- Score source
- journalList
- Score
- = 35.0, 07-08-2020, ArticleFromJournal
- Publication indicators
- = 0; : 2018 = 1.410; : 2018 = 0.958 (2) - 2018=1.071 (5)

- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM1c156d2520b7466b9718a2791f0480b4/

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perishopening in a new tab system.