Search Results

Documents authored by Suk, Andrew

Document
DOI: 10.4230/LIPIcs.GD.2024.4
Enumeration of Intersection Graphs of x-Monotone Curves

Authors: Jacob Fox, János Pach, and Andrew Suk

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
A curve in the plane is x-monotone if every vertical line intersects it at most once. A family of curves are called pseudo-segments if every pair of them have at most one point in common. We construct 2^Ω(n^{4/3}) families, each consisting of n labelled x-monotone pseudo-segments such that their intersection graphs are different. On the other hand, we show that the number of such intersection graphs is at most 2^O(n^{3/2-ε}), where ε > 0 is a suitable constant. Our proof uses an upper bound on the number of set systems of size m on a ground set of size n, with VC-dimension at most d. Much better upper bounds are obtained if we only count bipartite intersection graphs, or, in general, intersection graphs with bounded chromatic number.
Cite as

Jacob Fox, János Pach, and Andrew Suk. Enumeration of Intersection Graphs of x-Monotone Curves. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.GD.2024.4,
  author =	{Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
  title =	{{Enumeration of Intersection Graphs of x-Monotone Curves}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.4},
  URN =		{urn:nbn:de:0030-drops-212887},
  doi =		{10.4230/LIPIcs.GD.2024.4},
  annote =	{Keywords: Enumeration, intersection graphs, pseudo-segments, x-monotone}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.59
A Structure Theorem for Pseudo-Segments and Its Applications

Authors: Jacob Fox, János Pach, and Andrew Suk

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We prove a far-reaching strengthening of Szemerédi’s regularity lemma for intersection graphs of pseudo-segments. It shows that the vertex set of such graphs can be partitioned into a bounded number of parts of roughly the same size such that almost all of the bipartite graphs between pairs of parts are complete or empty. We use this to get an improved bound on disjoint edges in simple topological graphs, showing that every n-vertex simple topological graph with no k pairwise disjoint edges has at most n(log n)^O(log k) edges.
Cite as

Jacob Fox, János Pach, and Andrew Suk. A Structure Theorem for Pseudo-Segments and Its Applications. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 59:1-59:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.SoCG.2024.59,
  author =	{Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
  title =	{{A Structure Theorem for Pseudo-Segments and Its Applications}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{59:1--59:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.59},
  URN =		{urn:nbn:de:0030-drops-200040},
  doi =		{10.4230/LIPIcs.SoCG.2024.59},
  annote =	{Keywords: Regularity lemma, pseudo-segments, intersection graphs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.41
Disjoint Faces in Drawings of the Complete Graph and Topological Heilbronn Problems

Authors: Alfredo Hubard and Andrew Suk

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Given a complete simple topological graph G, a k-face generated by G is the open bounded region enclosed by the edges of a non-self-intersecting k-cycle in G. Interestingly, there are complete simple topological graphs with the property that every odd face it generates contains the origin. In this paper, we show that every complete n-vertex simple topological graph generates at least Ω(n^{1/3}) pairwise disjoint 4-faces. As an immediate corollary, every complete simple topological graph on n vertices drawn in the unit square generates a 4-face with area at most O(n^{-1/3}). Finally, we investigate a ℤ₂ variant of Heilbronn’s triangle problem for not necessarily simple complete topological graphs.
Cite as

Alfredo Hubard and Andrew Suk. Disjoint Faces in Drawings of the Complete Graph and Topological Heilbronn Problems. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hubard_et_al:LIPIcs.SoCG.2023.41,
  author =	{Hubard, Alfredo and Suk, Andrew},
  title =	{{Disjoint Faces in Drawings of the Complete Graph and Topological Heilbronn Problems}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{41:1--41:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.41},
  URN =		{urn:nbn:de:0030-drops-178917},
  doi =		{10.4230/LIPIcs.SoCG.2023.41},
  annote =	{Keywords: Disjoint faces, simple topological graphs, topological Heilbronn problems}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.59
On Higher Dimensional Point Sets in General Position

Authors: Andrew Suk and Ji Zeng

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
A finite point set in ℝ^d is in general position if no d + 1 points lie on a common hyperplane. Let α_d(N) be the largest integer such that any set of N points in ℝ^d with no d + 2 members on a common hyperplane, contains a subset of size α_d(N) in general position. Using the method of hypergraph containers, Balogh and Solymosi showed that α₂(N) < N^{5/6 + o(1)}. In this paper, we also use the container method to obtain new upper bounds for α_d(N) when d ≥ 3. More precisely, we show that if d is odd, then α_d(N) < N^{1/2 + 1/(2d) + o(1)}, and if d is even, we have α_d(N) < N^{1/2 + 1/(d-1) + o(1)}. We also study the classical problem of determining the maximum number a(d,k,n) of points selected from the grid [n]^d such that no k + 2 members lie on a k-flat. For fixed d and k, we show that a(d,k,n)≤ O(n^{d/{2⌊(k+2)/4⌋}(1- 1/{2⌊(k+2)/4⌋d+1})}), which improves the previously best known bound of O(n^{d/⌊(k + 2)/2⌋}) due to Lefmann when k+2 is congruent to 0 or 1 mod 4.
Cite as

Andrew Suk and Ji Zeng. On Higher Dimensional Point Sets in General Position. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{suk_et_al:LIPIcs.SoCG.2023.59,
  author =	{Suk, Andrew and Zeng, Ji},
  title =	{{On Higher Dimensional Point Sets in General Position}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{59:1--59:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.59},
  URN =		{urn:nbn:de:0030-drops-179097},
  doi =		{10.4230/LIPIcs.SoCG.2023.59},
  annote =	{Keywords: independent sets, hypergraph container method, generalised Sidon sets}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.62
A Positive Fraction Erdős-Szekeres Theorem and Its Applications

Authors: Andrew Suk and Ji Zeng

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
A famous theorem of Erdős and Szekeres states that any sequence of n distinct real numbers contains a monotone subsequence of length at least √n. Here, we prove a positive fraction version of this theorem. For n > (k-1)², any sequence A of n distinct real numbers contains a collection of subsets A_1,…, A_k ⊂ A, appearing sequentially, all of size s = Ω(n/k²), such that every subsequence (a_1,…, a_k), with a_i ∈ A_i, is increasing, or every such subsequence is decreasing. The subsequence S = (A_1,…, A_k) described above is called block-monotone of depth k and block-size s. Our theorem is asymptotically best possible and follows from a more general Ramsey-type result for monotone paths, which we find of independent interest. We also show that for any positive integer k, any finite sequence of distinct real numbers can be partitioned into O(k²log k) block-monotone subsequences of depth at least k, upon deleting at most (k-1)² entries. We apply our results to mutually avoiding planar point sets and biarc diagrams in graph drawing.
Cite as

Andrew Suk and Ji Zeng. A Positive Fraction Erdős-Szekeres Theorem and Its Applications. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{suk_et_al:LIPIcs.SoCG.2022.62,
  author =	{Suk, Andrew and Zeng, Ji},
  title =	{{A Positive Fraction Erd\H{o}s-Szekeres Theorem and Its Applications}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.62},
  URN =		{urn:nbn:de:0030-drops-160703},
  doi =		{10.4230/LIPIcs.SoCG.2022.62},
  annote =	{Keywords: Erd\H{o}s-Szekeres, block-monotone, monotone biarc diagrams, mutually avoiding sets}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.37
Sunflowers in Set Systems of Bounded Dimension

Authors: Jacob Fox, János Pach, and Andrew Suk

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Given a family F of k-element sets, S₁,…,S_r ∈ F form an r-sunflower if S_i ∩ S_j = S_{i'} ∩ S_{j'} for all i ≠ j and i' ≠ j'. According to a famous conjecture of Erdős and Rado (1960), there is a constant c = c(r) such that if |F| ≥ c^k, then F contains an r-sunflower. We come close to proving this conjecture for families of bounded Vapnik-Chervonenkis dimension, VC-dim(F) ≤ d. In this case, we show that r-sunflowers exist under the slightly stronger assumption |F| ≥ 2^{10k(dr)^{2log^{*} k}}. Here, log^* denotes the iterated logarithm function. We also verify the Erdős-Rado conjecture for families F of bounded Littlestone dimension and for some geometrically defined set systems.
Cite as

Jacob Fox, János Pach, and Andrew Suk. Sunflowers in Set Systems of Bounded Dimension. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.SoCG.2021.37,
  author =	{Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
  title =	{{Sunflowers in Set Systems of Bounded Dimension}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{37:1--37:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.37},
  URN =		{urn:nbn:de:0030-drops-138366},
  doi =		{10.4230/LIPIcs.SoCG.2021.37},
  annote =	{Keywords: Sunflower, VC-dimension, Littlestone dimension, pseudodisks}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.46
Bounded VC-Dimension Implies the Schur-Erdős Conjecture

Authors: Jacob Fox, János Pach, and Andrew Suk

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

Abstract
In 1916, Schur introduced the Ramsey number r(3;m), which is the minimum integer n > 1 such that for any m-coloring of the edges of the complete graph K_n, there is a monochromatic copy of K₃. He showed that r(3;m) ≤ O(m!), and a simple construction demonstrates that r(3;m) ≥ 2^Ω(m). An old conjecture of Erdős states that r(3;m) = 2^Θ(m). In this note, we prove the conjecture for m-colorings with bounded VC-dimension, that is, for m-colorings with the property that the set system induced by the neighborhoods of the vertices with respect to each color class has bounded VC-dimension.
Cite as

Jacob Fox, János Pach, and Andrew Suk. Bounded VC-Dimension Implies the Schur-Erdős Conjecture. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 46:1-46:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.SoCG.2020.46,
  author =	{Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
  title =	{{Bounded VC-Dimension Implies the Schur-Erd\H{o}s Conjecture}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{46:1--46:8},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.46},
  URN =		{urn:nbn:de:0030-drops-122046},
  doi =		{10.4230/LIPIcs.SoCG.2020.46},
  annote =	{Keywords: Ramsey theory, VC-dimension, Multicolor Ramsey numbers}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.36
Semi-Algebraic Colorings of Complete Graphs

Authors: Jacob Fox, János Pach, and Andrew Suk

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We consider m-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The case m = 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type results for intersection graphs of geometric objects and for other graphs arising in computational geometry. Considering larger values of m is relevant, e.g., to problems concerning the number of distinct distances determined by a point set. For p >= 3 and m >= 2, the classical Ramsey number R(p;m) is the smallest positive integer n such that any m-coloring of the edges of K_n, the complete graph on n vertices, contains a monochromatic K_p. It is a longstanding open problem that goes back to Schur (1916) to decide whether R(p;m)=2^{O(m)}, for a fixed p. We prove that this is true if each color class is defined semi-algebraically with bounded complexity, and that the order of magnitude of this bound is tight. Our proof is based on the Cutting Lemma of Chazelle et al., and on a Szemerédi-type regularity lemma for multicolored semi-algebraic graphs, which is of independent interest. The same technique is used to address the semi-algebraic variant of a more general Ramsey-type problem of Erdős and Shelah.
Cite as

Jacob Fox, János Pach, and Andrew Suk. Semi-Algebraic Colorings of Complete Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 36:1-36:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.SoCG.2019.36,
  author =	{Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
  title =	{{Semi-Algebraic Colorings of Complete Graphs}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{36:1--36:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.36},
  URN =		{urn:nbn:de:0030-drops-104401},
  doi =		{10.4230/LIPIcs.SoCG.2019.36},
  annote =	{Keywords: Semi-algebraic graphs, Ramsey theory, regularity lemma}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.50
On Grids in Point-Line Arrangements in the Plane

Authors: Mozhgan Mirzaei and Andrew Suk

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
The famous Szemerédi-Trotter theorem states that any arrangement of n points and n lines in the plane determines O(n^{4/3}) incidences, and this bound is tight. In this paper, we prove the following Turán-type result for point-line incidence. Let L_a and L_b be two sets of t lines in the plane and let P={l_a cap l_b : l_a in L_a, l_b in L_b} be the set of intersection points between L_a and L_b. We say that (P, L_a cup L_b) forms a natural t x t grid if |P| =t^2, and conv(P) does not contain the intersection point of some two lines in L_a and does not contain the intersection point of some two lines in L_b. For fixed t > 1, we show that any arrangement of n points and n lines in the plane that does not contain a natural t x t grid determines O(n^{4/3- epsilon}) incidences, where epsilon = epsilon(t)>0. We also provide a construction of n points and n lines in the plane that does not contain a natural 2 x 2 grid and determines at least Omega(n^{1+1/14}) incidences.
Cite as

Mozhgan Mirzaei and Andrew Suk. On Grids in Point-Line Arrangements in the Plane. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 50:1-50:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mirzaei_et_al:LIPIcs.SoCG.2019.50,
  author =	{Mirzaei, Mozhgan and Suk, Andrew},
  title =	{{On Grids in Point-Line Arrangements in the Plane}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{50:1--50:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.50},
  URN =		{urn:nbn:de:0030-drops-104541},
  doi =		{10.4230/LIPIcs.SoCG.2019.50},
  annote =	{Keywords: Szemer\'{e}di-Trotter Theorem, Grids, Sidon sets}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.43
Erdös-Hajnal Conjecture for Graphs with Bounded VC-Dimension

Authors: Jacob Fox, János Pach, and Andrew Suk

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
The Vapnik-Chervonenkis dimension (in short, VC-dimension) of a graph is defined as the VC-dimension of the set system induced by the neighborhoods of its vertices. We show that every n-vertex graph with bounded VC-dimension contains a clique or an independent set of size at least e^{(log n)^{1 - o(1)}}. The dependence on the VC-dimension is hidden in the o(1) term. This improves the general lower bound, e^{c sqrt{log n}}, due to Erdos and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our result is almost optimal and nearly matches the celebrated Erdos-Hajnal conjecture, according to which one can always find a clique or an independent set of size at least e^{Omega(log n)}. Our results partially explain why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties. Our main tool is a partitioning result found by Lovasz-Szegedy and Alon-Fischer-Newman, which is called the "ultra-strong regularity lemma" for graphs with bounded VC-dimension. We extend this lemma to k-uniform hypergraphs, and prove that the number of parts in the partition can be taken to be (1/epsilon)^{O(d)}, improving the original bound of (1/epsilon)^{O(d^2)} in the graph setting. We show that this bound is tight up to an absolute constant factor in the exponent. Moreover, we give an O(n^k)-time algorithm for finding a partition meeting the requirements in the k-uniform setting.
Cite as

Jacob Fox, János Pach, and Andrew Suk. Erdös-Hajnal Conjecture for Graphs with Bounded VC-Dimension. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.SoCG.2017.43,
  author =	{Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
  title =	{{Erd\"{o}s-Hajnal Conjecture for Graphs with Bounded VC-Dimension}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.43},
  URN =		{urn:nbn:de:0030-drops-72246},
  doi =		{10.4230/LIPIcs.SoCG.2017.43},
  annote =	{Keywords: VC-dimension, Ramsey theory, regularity lemma}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.59
Semi-algebraic Ramsey Numbers

Authors: Andrew Suk

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
Given a finite set P of points from R^d, a k-ary semi-algebraic relation E on P is the set of k-tuples of points in P, which is determined by a finite number of polynomial equations and inequalities in kd real variables. The description complexity of such a relation is at most t if the number of polynomials and their degrees are all bounded by t. The Ramsey number R^{d,t}_k(s,n) is the minimum N such that any N-element point set P in R^d equipped with a k-ary semi-algebraic relation E, such that E has complexity at most t, contains s members such that every k-tuple induced by them is in E, or n members such that every k-tuple induced by them is not in E. We give a new upper bound for R^{d,t}_k(s,n) for k=3 and s fixed. In particular, we show that for fixed integers d,t,s, R^{d,t}_3(s,n)=2^{n^{o(1)}}, establishing a subexponential upper bound on R^{d,t}_3(s,n). This improves the previous bound of 2^{n^C} due to Conlon, Fox, Pach, Sudakov, and Suk, where C is a very large constant depending on d,t, and s. As an application, we give new estimates for a recently studied Ramsey-type problem on hyperplane arrangements in R^d. We also study multi-color Ramsey numbers for triangles in our semi-algebraic setting, achieving some partial results.
Cite as

Andrew Suk. Semi-algebraic Ramsey Numbers. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 59-73, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{suk:LIPIcs.SOCG.2015.59,
  author =	{Suk, Andrew},
  title =	{{Semi-algebraic Ramsey Numbers}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{59--73},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.59},
  URN =		{urn:nbn:de:0030-drops-50955},
  doi =		{10.4230/LIPIcs.SOCG.2015.59},
  annote =	{Keywords: Ramsey theory, semi-algebraic relation, one-sided hyperplanes, Schur numbers}
}
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 About DROPS Imprint Privacy Contact