A tale of stars and cliques

Link:
Autor/in:
Erscheinungsjahr:
2018
Medientyp:
Text
Schlagworte:
  • Article
  • Article
Beschreibung:
  • We show that for infinitely many natural numbers k there are k-uniform hypergraphs which admit a `resealing 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 oft 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. (C) 2018 Elsevier Inc. All rights reserved.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/92b970a1-cf28-4d9d-b00f-386adcd3c0ef