2 Search Results for "Angel, Omer"

Document
DOI: 10.4230/LIPIcs.SoCG.2020.65
Dense Graphs Have Rigid Parts

Authors: Orit E. Raz and József Solymosi

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
While the problem of determining whether an embedding of a graph G in ℝ² is infinitesimally rigid is well understood, specifying whether a given embedding of G is rigid or not is still a hard task that usually requires ad hoc arguments. In this paper, we show that every embedding (not necessarily generic) of a dense enough graph (concretely, a graph with at least C₀n^{3/2}(log n)^β edges, for some absolute constants C₀>0 and β), which satisfies some very mild general position requirements (no three vertices of G are embedded to a common line), must have a subframework of size at least three which is rigid. For the proof we use a connection, established in Raz [Discrete Comput. Geom., 2017], between the notion of graph rigidity and configurations of lines in ℝ³. This connection allows us to use properties of line configurations established in Guth and Katz [Annals Math., 2015]. In fact, our proof requires an extended version of Guth and Katz result; the extension we need is proved by János Kollár in an Appendix to our paper. We do not know whether our assumption on the number of edges being Ω(n^{3/2}log n) is tight, and we provide a construction that shows that requiring Ω(n log n) edges is necessary.
Cite as

Orit E. Raz and József Solymosi. Dense Graphs Have Rigid Parts. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{raz_et_al:LIPIcs.SoCG.2020.65,
  author =	{Raz, Orit E. and Solymosi, J\'{o}zsef},
  title =	{{Dense Graphs Have Rigid Parts}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.65},
  URN =		{urn:nbn:de:0030-drops-122236},
  doi =		{10.4230/LIPIcs.SoCG.2020.65},
  annote =	{Keywords: Graph rigidity, line configurations in 3D}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.26
The String of Diamonds Is Tight for Rumor Spreading

Authors: Omer Angel, Abbas Mehrabian, and Yuval Peres

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

Abstract
For a rumor spreading protocol, the spread time is defined as the first time that everyone learns the rumor. We compare the synchronous push&pull rumor spreading protocol with its asynchronous variant, and show that for any n-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by O(n^{1/3} log^{2/3} n). This improves the O(sqrt n) upper bound of Giakkoupis, Nazari, and Woelfel (in Proceedings of ACM Symposium on Principles of Distributed Computing, 2016). Our bound is tight up to a factor of O(log n), as illustrated by the string of diamonds graph.
Cite as

Omer Angel, Abbas Mehrabian, and Yuval Peres. The String of Diamonds Is Tight for Rumor Spreading. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 26:1-26:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{angel_et_al:LIPIcs.APPROX-RANDOM.2017.26,
  author =	{Angel, Omer and Mehrabian, Abbas and Peres, Yuval},
  title =	{{The String of Diamonds Is Tight for Rumor Spreading}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{26:1--26:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  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.2017.26},
  URN =		{urn:nbn:de:0030-drops-75754},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.26},
  annote =	{Keywords: randomized rumor spreading, push\&pull protocol, asynchronous time model, string of diamonds}
}
  • Refine by Author
  • 1 Angel, Omer
  • 1 Mehrabian, Abbas
  • 1 Peres, Yuval
  • 1 Raz, Orit E.
  • 1 Solymosi, József

  • Refine by Classification
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Graph theory

  • Refine by Keyword
  • 1 Graph rigidity
  • 1 asynchronous time model
  • 1 line configurations in 3D
  • 1 push&pull protocol
  • 1 randomized rumor spreading
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 1 2020

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