5 Search Results for "Holmsen, Andreas"

Document
DOI: 10.4230/LIPIcs.SoCG.2022.50
An (ℵ₀,k+2)-Theorem for k-Transversals

Authors: Chaya Keller and Micha A. Perles

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

Abstract
A family ℱ of sets satisfies the (p,q)-property if among every p members of ℱ, some q can be pierced by a single point. The celebrated (p,q)-theorem of Alon and Kleitman asserts that for any p ≥ q ≥ d+1, any family ℱ of compact convex sets in ℝ^d that satisfies the (p,q)-property can be pierced by a finite number c(p,q,d) of points. A similar theorem with respect to piercing by (d-1)-dimensional flats, called (d-1)-transversals, was obtained by Alon and Kalai. In this paper we prove the following result, which can be viewed as an (ℵ₀,k+2)-theorem with respect to k-transversals: Let ℱ be an infinite family of sets in ℝ^d such that each A ∈ ℱ contains a ball of radius r and is contained in a ball of radius R, and let 0 ≤ k < d. If among every ℵ₀ elements of ℱ, some k+2 can be pierced by a k-dimensional flat, then ℱ can be pierced by a finite number of k-dimensional flats. This is the first (p,q)-theorem in which the assumption is weakened to an (∞,⋅) assumption. Our proofs combine geometric and topological tools.
Cite as

Chaya Keller and Micha A. Perles. An (ℵ₀,k+2)-Theorem for k-Transversals. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{keller_et_al:LIPIcs.SoCG.2022.50,
  author =	{Keller, Chaya and Perles, Micha A.},
  title =	{{An (\aleph₀,k+2)-Theorem for k-Transversals}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{50:1--50:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.50},
  URN =		{urn:nbn:de:0030-drops-160581},
  doi =		{10.4230/LIPIcs.SoCG.2022.50},
  annote =	{Keywords: convexity, (p,q)-theorem, k-transversal, infinite (p,q)-theorem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.40
A Stepping-Up Lemma for Topological Set Systems

Authors: Xavier Goaoc, Andreas F. Holmsen, and Zuzana Patáková

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

Abstract
Intersection patterns of convex sets in ℝ^d have the remarkable property that for d+1 ≤ k ≤ 𝓁, in any sufficiently large family of convex sets in ℝ^d, if a constant fraction of the k-element subfamilies have nonempty intersection, then a constant fraction of the 𝓁-element subfamilies must also have nonempty intersection. Here, we prove that a similar phenomenon holds for any topological set system ℱ in ℝ^d. Quantitatively, our bounds depend on how complicated the intersection of 𝓁 elements of ℱ can be, as measured by the maximum of the ⌈d/2⌉ first Betti numbers. As an application, we improve the fractional Helly number of set systems with bounded topological complexity due to the third author, from a Ramsey number down to d+1. We also shed some light on a conjecture of Kalai and Meshulam on intersection patterns of sets with bounded homological VC dimension. A key ingredient in our proof is the use of the stair convexity of Bukh, Matoušek and Nivasch to recast a simplicial complex as a homological minor of a cubical complex.
Cite as

Xavier Goaoc, Andreas F. Holmsen, and Zuzana Patáková. A Stepping-Up Lemma for Topological Set Systems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SoCG.2021.40,
  author =	{Goaoc, Xavier and Holmsen, Andreas F. and Pat\'{a}kov\'{a}, Zuzana},
  title =	{{A Stepping-Up Lemma for Topological Set Systems}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{40:1--40:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.40},
  URN =		{urn:nbn:de:0030-drops-138396},
  doi =		{10.4230/LIPIcs.SoCG.2021.40},
  annote =	{Keywords: Helly-type theorem, Topological combinatorics, Homological minors, Stair convexity, Cubical complexes, Homological VC dimension, Ramsey-type theorem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.60
Radon Numbers Grow Linearly

Authors: Dömötör Pálvölgyi

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

Abstract
Define the k-th Radon number r_k of a convexity space as the smallest number (if it exists) for which any set of r_k points can be partitioned into k parts whose convex hulls intersect. Combining the recent abstract fractional Helly theorem of Holmsen and Lee with earlier methods of Bukh, we prove that r_k grows linearly, i.e., r_k ≤ c(r₂)⋅ k.
Cite as

Dömötör Pálvölgyi. Radon Numbers Grow Linearly. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 60:1-60:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{palvolgyi:LIPIcs.SoCG.2020.60,
  author =	{P\'{a}lv\"{o}lgyi, D\"{o}m\"{o}t\"{o}r},
  title =	{{Radon Numbers Grow Linearly}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{60:1--60:5},
  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.60},
  URN =		{urn:nbn:de:0030-drops-122183},
  doi =		{10.4230/LIPIcs.SoCG.2020.60},
  annote =	{Keywords: discrete geometry, convexity space, Radon number}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.40
An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting

Authors: Xavier Goaoc, Andreas Holmsen, and Cyril Nicaud

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

Abstract
We study the problem of deciding if a given triple of permutations can be realized as geometric permutations of disjoint convex sets in R^3. We show that this question, which is equivalent to deciding the emptiness of certain semi-algebraic sets bounded by cubic polynomials, can be "lifted" to a purely combinatorial problem. We propose an effective algorithm for that problem, and use it to gain new insights into the structure of geometric permutations.
Cite as

Xavier Goaoc, Andreas Holmsen, and Cyril Nicaud. An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SoCG.2019.40,
  author =	{Goaoc, Xavier and Holmsen, Andreas and Nicaud, Cyril},
  title =	{{An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{40:1--40:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.40},
  URN =		{urn:nbn:de:0030-drops-104442},
  doi =		{10.4230/LIPIcs.SoCG.2019.40},
  annote =	{Keywords: Geometric permutation, Emptiness testing of semi-algebraic sets, Computer-aided proof}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.599
Realization Spaces of Arrangements of Convex Bodies

Authors: Michael Gene Dobbins, Andreas Holmsen, and Alfredo Hubard

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

Abstract
We introduce combinatorial types of arrangements of convex bodies, extending order types of point sets to arrangements of convex bodies, and study their realization spaces. Our main results witness a trade-off between the combinatorial complexity of the bodies and the topological complexity of their realization space. On one hand, we show that every combinatorial type can be realized by an arrangement of convex bodies and (under mild assumptions) its realization space is contractible. On the other hand, we prove a universality theorem that says that the restriction of the realization space to arrangements of convex polygons with a bounded number of vertices can have the homotopy type of any primary semialgebraic set.
Cite as

Michael Gene Dobbins, Andreas Holmsen, and Alfredo Hubard. Realization Spaces of Arrangements of Convex Bodies. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 599-614, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dobbins_et_al:LIPIcs.SOCG.2015.599,
  author =	{Dobbins, Michael Gene and Holmsen, Andreas and Hubard, Alfredo},
  title =	{{Realization Spaces of Arrangements of Convex Bodies}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{599--614},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.599},
  URN =		{urn:nbn:de:0030-drops-51020},
  doi =		{10.4230/LIPIcs.SOCG.2015.599},
  annote =	{Keywords: Oriented matroids, Convex sets, Realization spaces, Mnev’s universality theorem}
}
  • Refine by Author
  • 2 Goaoc, Xavier
  • 2 Holmsen, Andreas
  • 1 Dobbins, Michael Gene
  • 1 Holmsen, Andreas F.
  • 1 Hubard, Alfredo
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Computational geometry
  • 1 Computing methodologies → Combinatorial algorithms
  • 1 Mathematics of computing → Hypergraphs

  • Refine by Keyword
  • 1 (p,q)-theorem
  • 1 Computer-aided proof
  • 1 Convex sets
  • 1 Cubical complexes
  • 1 Emptiness testing of semi-algebraic sets
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2015
  • 1 2019
  • 1 2020
  • 1 2021
  • 1 2022

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