10 Search Results for "Fox, Jacob"

Document
DOI: 10.4230/LIPIcs.SEA.2024.8
Practical Computation of Graph VC-Dimension

Authors: David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
For any set system ℋ = (V,ℛ), ℛ ⊆ 2^V, a subset S ⊆ V is called shattered if every S' ⊆ S results from the intersection of S with some set in ℛ. The VC-dimension of ℋ is the size of a largest shattered set in V. In this paper, we focus on the problem of computing the VC-dimension of graphs. In particular, given a graph G = (V,E), the VC-dimension of G is defined as the VC-dimension of (V, N), where N contains each subset of V that can be obtained as the closed neighborhood of some vertex v ∈ V in G. Our main contribution is an algorithm for computing the VC-dimension of any graph, whose effectiveness is shown through experiments on various types of practical graphs, including graphs with millions of vertices. A key aspect of its efficiency resides in the fact that practical graphs have small VC-dimension, up to 8 in our experiments. As a side-product, we present several new bounds relating the graph VC-dimension to other classical graph theoretical notions. We also establish the W[1]-hardness of the graph VC-dimension problem by extending a previous result for arbitrary set systems.
Cite as

David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot. Practical Computation of Graph VC-Dimension. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{coudert_et_al:LIPIcs.SEA.2024.8,
  author =	{Coudert, David and Csik\'{o}s, M\'{o}nika and Ducoffe, Guillaume and Viennot, Laurent},
  title =	{{Practical Computation of Graph VC-Dimension}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.8},
  URN =		{urn:nbn:de:0030-drops-203731},
  doi =		{10.4230/LIPIcs.SEA.2024.8},
  annote =	{Keywords: VC-dimension, graph, algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.30
Õptimal Dynamic Time Warping on Run-Length Encoded Strings

Authors: Itai Boneh, Shay Golan, Shay Mozes, and Oren Weimann

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Dynamic Time Warping (DTW) distance is the optimal cost of matching two strings when extending runs of letters is for free. Therefore, it is natural to measure the time complexity of DTW in terms of the number of runs n (rather than the string lengths N). In this paper, we give an Õ(n²) time algorithm for computing the DTW distance. This matches (up to log factors) the known (conditional) lower bound, and should be compared with the previous fastest O(n³) time exact algorithm and the Õ(n²) time approximation algorithm. Our method also immediately implies an Õ(nk) time algorithm when the distance is bounded by k. This should be compared with the previous fastest O(n²k) and O(Nk) time exact algorithms and the Õ(nk) time approximation algorithm.
Cite as

Itai Boneh, Shay Golan, Shay Mozes, and Oren Weimann. Õptimal Dynamic Time Warping on Run-Length Encoded Strings. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boneh_et_al:LIPIcs.ICALP.2024.30,
  author =	{Boneh, Itai and Golan, Shay and Mozes, Shay and Weimann, Oren},
  title =	{{\~{O}ptimal Dynamic Time Warping on Run-Length Encoded Strings}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.30},
  URN =		{urn:nbn:de:0030-drops-201730},
  doi =		{10.4230/LIPIcs.ICALP.2024.30},
  annote =	{Keywords: Dynamic time warping, Fr\'{e}chet distance, edit distance, run-length encoding}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.95
Fully Dynamic Strongly Connected Components in Planar Digraphs

Authors: Adam Karczmarz and Marcin Smulewicz

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In this paper we consider maintaining strongly connected components (SCCs) of a directed planar graph subject to edge insertions and deletions. We show a data structure maintaining an implicit representation of the SCCs within Õ(n^{6/7}) worst-case time per update. The data structure supports, in O(log²{n}) time, reporting vertices of any specified SCC (with constant overhead per reported vertex) and aggregating vertex information (e.g., computing the maximum label) over all the vertices of that SCC. Furthermore, it can maintain global information about the structure of SCCs, such as the number of SCCs, or the size of the largest SCC. To the best of our knowledge, no fully dynamic SCCs data structures with sublinear update time have been previously known for any major subclass of digraphs. Our result should be contrasted with the n^{1-o(1)} amortized update time lower bound conditional on SETH, which holds even for dynamically maintaining whether a general digraph has more than two SCCs.
Cite as

Adam Karczmarz and Marcin Smulewicz. Fully Dynamic Strongly Connected Components in Planar Digraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{karczmarz_et_al:LIPIcs.ICALP.2024.95,
  author =	{Karczmarz, Adam and Smulewicz, Marcin},
  title =	{{Fully Dynamic Strongly Connected Components in Planar Digraphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{95:1--95:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.95},
  URN =		{urn:nbn:de:0030-drops-202388},
  doi =		{10.4230/LIPIcs.ICALP.2024.95},
  annote =	{Keywords: dynamic strongly connected components, dynamic strong connectivity, dynamic reachability, planar graphs}
}
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.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.ICALP.2018.55
Finding Cliques in Social Networks: A New Distribution-Free Model

Authors: Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We propose a new distribution-free model of social networks. Our definitions are motivated by one of the most universal signatures of social networks, triadic closure - the property that pairs of vertices with common neighbors tend to be adjacent. Our most basic definition is that of a c-closed graph, where for every pair of vertices u,v with at least c common neighbors, u and v are adjacent. We study the classic problem of enumerating all maximal cliques, an important task in social network analysis. We prove that this problem is fixed-parameter tractable with respect to c on c-closed graphs. Our results carry over to weakly c-closed graphs, which only require a vertex deletion ordering that avoids pairs of non-adjacent vertices with c common neighbors. Numerical experiments show that well-studied social networks tend to be weakly c-closed for modest values of c.
Cite as

Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein. Finding Cliques in Social Networks: A New Distribution-Free Model. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.ICALP.2018.55,
  author =	{Fox, Jacob and Roughgarden, Tim and Seshadhri, C. and Wei, Fan and Wein, Nicole},
  title =	{{Finding Cliques in Social Networks: A New Distribution-Free Model}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.55},
  URN =		{urn:nbn:de:0030-drops-90596},
  doi =		{10.4230/LIPIcs.ICALP.2018.55},
  annote =	{Keywords: Graph algorithms, social networks, fixed-parameter tractability}
}
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
Invited Talk
DOI: 10.4230/LIPIcs.SoCG.2016.2
Discrete Geometry, Algebra, and Combinatorics (Invited Talk)

Authors: Jacob Fox

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Many problems in discrete and computational geometry can be viewed as finding patterns in graphs or hypergraphs which arise from geometry or algebra. Famous Ramsey, Turán, and Szemerédi-type results prove the existence of certain patterns in graphs and hypergraphs under mild assumptions. We survey recent results which show much stronger/larger patterns for graphs and hypergraphs that arise from geometry or algebra. We further discuss whether the stronger results in these settings are due to geometric, algebraic, combinatorial, or topological properties of the graphs.
Cite as

Jacob Fox. Discrete Geometry, Algebra, and Combinatorics (Invited Talk). In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fox:LIPIcs.SoCG.2016.2,
  author =	{Fox, Jacob},
  title =	{{Discrete Geometry, Algebra, and Combinatorics}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.2},
  URN =		{urn:nbn:de:0030-drops-58948},
  doi =		{10.4230/LIPIcs.SoCG.2016.2},
  annote =	{Keywords: discrete geometry, extremal combinatorics, regularity lemmas, Ramsey theory}
}
  • Refine by Author
  • 7 Fox, Jacob
  • 5 Pach, János
  • 5 Suk, Andrew
  • 1 Boneh, Itai
  • 1 Coudert, David
  • Show More...

  • Refine by Classification
  • 3 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Fixed parameter tractability
  • Show More...

  • Refine by Keyword
  • 4 Ramsey theory
  • 4 VC-dimension
  • 2 regularity lemma
  • 1 Dynamic time warping
  • 1 Fréchet distance
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 4 2024
  • 1 2016
  • 1 2017
  • 1 2018
  • 1 2019
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact