License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.14
URN: urn:nbn:de:0030-drops-126171
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12617/
Go to the corresponding LIPIcs Volume Portal

Dreier, Jan ; Kuinke, Philipp ; Rossmanith, Peter

Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size

pdf-format:
LIPIcs-APPROX14.pdf (0.5 MB)

Abstract

Preferential attachment graphs are random graphs designed to mimic properties of real word networks. They are constructed by a random process that iteratively adds vertices and attaches them preferentially to vertices that already have high degree. We prove various structural asymptotic properties of this graph model. In particular, we show that the size of the largest r-shallow clique minor in Gⁿ_m is at most log(n)^{O(r²)}m^{O(r)}. Furthermore, there exists a one-subdivided clique of size log(n)^{1/4}. Therefore, preferential attachment graphs are asymptotically almost surely somewhere dense and algorithmic techniques developed for structurally sparse graph classes are not directly applicable. However, they are just barely somewhere dense. The removal of just slightly more than a polylogarithmic number of vertices asymptotically almost surely yields a graph with locally bounded treewidth.

BibTeX - Entry

@InProceedings{dreier_et_al:LIPIcs:2020:12617,
  author =	{Jan Dreier and Philipp Kuinke and Peter Rossmanith},
  title =	{{Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Jaros{\l}aw Byrka and Raghu Meka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12617},
  URN =		{urn:nbn:de:0030-drops-126171},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.14},
  annote =	{Keywords: Random Graphs, Preferential Attachment, Sparsity, Somewhere Dense}
}

Keywords: Random Graphs, Preferential Attachment, Sparsity, Somewhere Dense
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Issue Date: 2020
Date of publication: 11.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI