DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.59

Ramsey Properties of Randomly Perturbed Hypergraphs

Authors: Elad Aigner-Horev, Dan Hefetz, and Mathias Schacht

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

Abstract

We study Ramsey properties of randomly perturbed 3-uniform hypergraphs. For t ≥ 2, write K^(3)_t to denote the 3-uniform expanded clique hypergraph obtained from the complete graph K_t by expanding each of the edges of the latter with a new additional vertex. For an even integer t ≥ 4, let M denote the asymmetric maximal density of the pair (K^(3)_t, K^(3)_{t/2}). We prove that adding a set F of random hyperedges satisfying |F| ≫ n^{3-1/M} to a given n-vertex 3-uniform hypergraph H with non-vanishing edge density asymptotically almost surely results in a perturbed hypergraph enjoying the Ramsey property for K^(3)_t and two colours. We conjecture that this result is asymptotically best possible with respect to the size of F whenever t ≥ 6 is even. The key tools of our proof are a new variant of the hypergraph regularity lemma accompanied with a tuple lemma providing appropriate control over joint link graphs. Our variant combines the so called strong and the weak hypergraph regularity lemmata.

Cite as

Elad Aigner-Horev, Dan Hefetz, and Mathias Schacht. Ramsey Properties of Randomly Perturbed Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aignerhorev_et_al:LIPIcs.APPROX/RANDOM.2024.59,
  author =	{Aigner-Horev, Elad and Hefetz, Dan and Schacht, Mathias},
  title =	{{Ramsey Properties of Randomly Perturbed Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{59:1--59:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.59},
  URN =		{urn:nbn:de:0030-drops-210528},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.59},
  annote =	{Keywords: Ramsey Theory, Smoothed Analysis, Random Hypergraphs}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2018.35

Spanning-Tree Games

Authors: Dan Hefetz, Orna Kupferman, Amir Lellouche, and Gal Vardi

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract

We introduce and study a game variant of the classical spanning-tree problem. Our spanning-tree game is played between two players, min and max, who alternate turns in jointly constructing a spanning tree of a given connected weighted graph G. Starting with the empty graph, in each turn a player chooses an edge that does not close a cycle in the forest that has been generated so far and adds it to that forest. The game ends when the chosen edges form a spanning tree in G. The goal of min is to minimize the weight of the resulting spanning tree and the goal of max is to maximize it. A strategy for a player is a function that maps each forest in G to an edge that is not yet in the forest and does not close a cycle. We show that while in the classical setting a greedy approach is optimal, the game setting is more complicated: greedy strategies, namely ones that choose in each turn the lightest (min) or heaviest (max) legal edge, are not necessarily optimal, and calculating their values is NP-hard. We study the approximation ratio of greedy strategies. We show that while a greedy strategy for min guarantees nothing, the performance of a greedy strategy for max is satisfactory: it guarantees that the weight of the generated spanning tree is at least w(MST(G))/2, where w(MST(G)) is the weight of a maximum spanning tree in G, and its approximation ratio with respect to an optimal strategy for max is 1.5+1/w(MST(G)), assuming weights in [0,1]. We also show that these bounds are tight. Moreover, in a stochastic setting, where weights for the complete graph K_n are chosen at random from [0,1], the expected performance of greedy strategies is asymptotically optimal. Finally, we study some variants of the game and study an extension of our results to games on general matroids.

Cite as

Dan Hefetz, Orna Kupferman, Amir Lellouche, and Gal Vardi. Spanning-Tree Games. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hefetz_et_al:LIPIcs.MFCS.2018.35,
  author =	{Hefetz, Dan and Kupferman, Orna and Lellouche, Amir and Vardi, Gal},
  title =	{{Spanning-Tree Games}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.35},
  URN =		{urn:nbn:de:0030-drops-96171},
  doi =		{10.4230/LIPIcs.MFCS.2018.35},
  annote =	{Keywords: Algorithms, Games, Minimum/maximum spanning tree, Greedy algorithms}
}

Search Results

Documents authored by Hefetz, Dan

Ramsey Properties of Randomly Perturbed Hypergraphs

Abstract

Cite as

Spanning-Tree Games

Abstract

Cite as

Thanks for your feedback!

Could not send message