2 Search Results for "Frieze, Alan M."

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.36
On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs

Authors: Michael Anastos and Alan Frieze

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

Abstract
Let Omega_q=Omega_q(H) denote the set of proper [q]-colorings of the hypergraph H. Let Gamma_q be the graph with vertex set Omega_q where two vertices are adjacent iff the corresponding colorings differ in exactly one vertex. We show that if H=H_{n,m;k}, k >= 2, the random k-uniform hypergraph with V=[n] and m=dn/k hyperedges then w.h.p. Gamma_q is connected if d is sufficiently large and q >~ (d/log d)^{1/(k-1)}. This is optimal to the first order in d. Furthermore, with a few more colors, we find that the diameter of Gamma_q is O(n) w.h.p, where the hidden constant depends on d. So, with this choice of d,q, the natural Glauber Dynamics Markov Chain on Omega_q is ergodic w.h.p.
Cite as

Michael Anastos and Alan Frieze. On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 36:1-36:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{anastos_et_al:LIPIcs.APPROX-RANDOM.2019.36,
  author =	{Anastos, Michael and Frieze, Alan},
  title =	{{On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{36:1--36:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  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.2019.36},
  URN =		{urn:nbn:de:0030-drops-112513},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.36},
  annote =	{Keywords: Random Graphs, Colorings, Ergodicity}
}
Document
DOI: 10.4230/DagRep.1.6.24
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241)

Authors: Martin Dyer, Uriel Feige, Alan M. Frieze, and Marek Karpinski

Published in: Dagstuhl Reports, Volume 1, Issue 6 (2011)

Abstract
The Dagstuhl Seminar on ``Design and Analysis of Randomized and Approximation Algorithms'' (Seminar 11241) was held at Schloss Dagstuhl between June 13--17, 2011. There were 26 regular talks and several informal and open problem session contributions presented during this seminar. Abstracts of the presentations have been put together in this seminar proceedings document together with some links to extended abstracts and full papers.
Cite as

Martin Dyer, Uriel Feige, Alan M. Frieze, and Marek Karpinski. Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). In Dagstuhl Reports, Volume 1, Issue 6, pp. 24-53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{dyer_et_al:DagRep.1.6.24,
  author =	{Dyer, Martin and Feige, Uriel and Frieze, Alan M. and Karpinski, Marek},
  title =	{{Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241)}},
  pages =	{24--53},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{6},
  editor =	{Dyer, Martin and Feige, Uriel and Frieze, Alan M. and Karpinski, Marek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.6.24},
  URN =		{urn:nbn:de:0030-drops-32585},
  doi =		{10.4230/DagRep.1.6.24},
  annote =	{Keywords: Randomized Algorithms, Approximation Algorithms, Probabilistically Checkable Proofs, Approximation Hardness, Optimization Problems, Counting Problems, Streaming Algorithms, Random Graphs, Hypergraphs, Probabilistic Method, Networks, Linear Programs, Semidefinite Programs}
}
  • Refine by Author
  • 1 Anastos, Michael
  • 1 Dyer, Martin
  • 1 Feige, Uriel
  • 1 Frieze, Alan
  • 1 Frieze, Alan M.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation

  • Refine by Keyword
  • 2 Random Graphs
  • 1 Approximation Algorithms
  • 1 Approximation Hardness
  • 1 Colorings
  • 1 Counting Problems
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2011
  • 1 2019

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