2 Search Results for "Perarnau, Guillem"

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.26
Local Convergence and Stability of Tight Bridge-Addable Graph Classes

Authors: Guillaume Chapuy and Guillem Perarnau

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
A class of graphs is bridge-addable if given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. The authors recently proved a conjecture of McDiarmid, Steger, and Welsh stating that if G is bridge-addable and G_n is a uniform n-vertex graph from G, then G_n is connected with probability at least (1+o(1))e^{-1/2}. The constant e^{-1/2} is best possible since it is reached for the class of forests. In this paper we prove a form of uniqueness in this statement: if G is a bridge-addable class and the random graph G_n is connected with probability close to e^{-1/2}, then G_n is asymptotically close to a uniform forest in some "local" sense. For example, if the probability converges to e^{-1/2}, then G_n converges for the Benjamini-Schramm topology, to the uniform infinite random forest F_infinity. This result is reminiscent of so-called "stability results" in extremal graph theory, with the difference that here the "stable" extremum is not a graph but a graph class.
Cite as

Guillaume Chapuy and Guillem Perarnau. Local Convergence and Stability of Tight Bridge-Addable Graph Classes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 26:1-26:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chapuy_et_al:LIPIcs.APPROX-RANDOM.2016.26,
  author =	{Chapuy, Guillaume and Perarnau, Guillem},
  title =	{{Local Convergence and Stability of Tight Bridge-Addable Graph Classes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{26:1--26:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.26},
  URN =		{urn:nbn:de:0030-drops-66494},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.26},
  annote =	{Keywords: bridge-addable classes, random graphs, stability, local convergence, random forests}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.408
On the treewidth and related parameters of random geometric graphs

Authors: Dieter Mitsche and Guillem Perarnau

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We give asymptotically exact values for the treewidth tw(G) of a random geometric graph G(n,r) in [0,sqrt(n)]^2. More precisely, we show that there exists some c_1 > 0, such that for any constant 0 < r < c_1, tw(G)=Theta(log(n)/loglog(n)), and also, there exists some c_2 > c_1, such that for any r=r(n)> c_2, tw(G)=Theta(r sqrt(n)). Our proofs show that for the corresponding values of r the same asymptotic bounds also hold for the pathwidth and treedepth of a random geometric graph.
Cite as

Dieter Mitsche and Guillem Perarnau. On the treewidth and related parameters of random geometric graphs. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 408-419, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{mitsche_et_al:LIPIcs.STACS.2012.408,
  author =	{Mitsche, Dieter and Perarnau, Guillem},
  title =	{{On the treewidth and related parameters of random geometric graphs}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{408--419},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.408},
  URN =		{urn:nbn:de:0030-drops-34280},
  doi =		{10.4230/LIPIcs.STACS.2012.408},
  annote =	{Keywords: Random geometric graphs, treewidth, treedepth}
}
  • Refine by Author
  • 2 Perarnau, Guillem
  • 1 Chapuy, Guillaume
  • 1 Mitsche, Dieter

  • Refine by Classification

  • Refine by Keyword
  • 1 Random geometric graphs
  • 1 bridge-addable classes
  • 1 local convergence
  • 1 random forests
  • 1 random graphs
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2012
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact