> Detailanzeige

Krivelevich, Michael; Loh, Po‐Shen; Sudakov, Benny

Avoiding small subgraphs in Achlioptas processes

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: E-Artikel
  • Titel: Avoiding small subgraphs in Achlioptas processes
  • Beteiligte: Krivelevich, Michael; Loh, Po‐Shen; Sudakov, Benny
  • Erschienen: Wiley, 2009
  • Erschienen in: Random Structures & Algorithms
  • Sprache: Englisch
  • DOI: 10.1002/rsa.20254
  • ISSN: 1042-9832; 1098-2418
  • Schlagwörter: Applied Mathematics ; Computer Graphics and Computer-Aided Design ; General Mathematics ; Software
  • Entstehung:
  • Anmerkungen:
  • Beschreibung: <jats:title>Abstract</jats:title><jats:p>For a fixed integer <jats:italic>r</jats:italic>, consider the following random process. At each round, one is presented with <jats:italic>r</jats:italic> random edges from the edge set of the complete graph on <jats:italic>n</jats:italic> vertices, and is asked to choose one of them. The selected edges are collected into a graph, which thus grows at the rate of one edge per round. This is a natural generalization of what is known in the literature as an Achlioptas process (the original version has <jats:italic>r</jats:italic> = 2), which has been studied by many researchers, mainly in the context of delaying or accelerating the appearance of the giant component.</jats:p><jats:p>In this article, we investigate the small subgraph problem for Achlioptas processes. That is, given a fixed graph <jats:italic>H</jats:italic>, we study whether there is an online algorithm that substantially delays or accelerates a typical appearance of <jats:italic>H</jats:italic>, compared to its threshold of appearance in the random graph <jats:italic>G</jats:italic>(<jats:italic>n, M</jats:italic>). It is easy to see that one cannot accelerate the appearance of any fixed graph by more than the constant factor <jats:italic>r</jats:italic>, so we concentrate on the task of avoiding <jats:italic>H</jats:italic>. We determine thresholds for the avoidance of all cycles <jats:italic>C</jats:italic><jats:sub><jats:italic>t</jats:italic></jats:sub>, cliques <jats:italic>K</jats:italic><jats:sub><jats:italic>t</jats:italic></jats:sub>, and complete bipartite graphs <jats:italic>K</jats:italic><jats:sub><jats:italic>t,t</jats:italic></jats:sub>, in every Achlioptas process with parameter <jats:italic>r</jats:italic> ge 2. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009</jats:p>