23 Search Results for "Wagner, Uli"

Document
DOI: 10.4230/LIPIcs.ITP.2025.9
Algebra Is Half the Battle: Verifying Presentations of Graded Unipotent Chevalley Groups

Authors: Eric Wang, Arohee Bhoja, Cayden Codel, and Noah G. Singer

Published in: LIPIcs, Volume 352, 16th International Conference on Interactive Theorem Proving (ITP 2025)

Abstract
Graded unipotent Chevalley groups are an important family of groups on matrices with polynomial entries over a finite field. Using the Lean theorem prover, we verify that three such groups, namely, the A₃- and the two B₃-type groups, satisfy a useful group-theoretic condition. Specifically, these groups are defined by a set of equations called Steinberg relations, and we prove that a certain canonical "smaller" set of Steinberg relations suffices to derive the rest. Our work is motivated by an application for building topologically-interesting objects called higher-dimensional expanders (HDXs). In the past decade, HDXs have formed the basis for many new results in theoretical computer science, such as in quantum error correction and in property testing. Yet despite the increasing prevalence of HDXs, only two methods of constructing them are known. One such method builds an HDX from groups that satisfy the aforementioned property, and the Chevalley groups we use are (essentially) the only ones currently known to satisfy it.
Cite as

Eric Wang, Arohee Bhoja, Cayden Codel, and Noah G. Singer. Algebra Is Half the Battle: Verifying Presentations of Graded Unipotent Chevalley Groups. In 16th International Conference on Interactive Theorem Proving (ITP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 352, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ITP.2025.9,
  author =	{Wang, Eric and Bhoja, Arohee and Codel, Cayden and Singer, Noah G.},
  title =	{{Algebra Is Half the Battle: Verifying Presentations of Graded Unipotent Chevalley Groups}},
  booktitle =	{16th International Conference on Interactive Theorem Proving (ITP 2025)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-396-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{352},
  editor =	{Forster, Yannick and Keller, Chantal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2025.9},
  URN =		{urn:nbn:de:0030-drops-246071},
  doi =		{10.4230/LIPIcs.ITP.2025.9},
  annote =	{Keywords: Group presentations, term rewriting, metaprogramming, proof automation, the Lean theorem prover}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.7
Sparser Abelian High Dimensional Expanders

Authors: Yotam Dikstein, Siqi Liu, and Avi Wigderson

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
The focus of this paper is the development of new elementary techniques for the construction and analysis of high dimensional expanders. Specifically, we present two new explicit constructions of Cayley high dimensional expanders (HDXs) over the abelian group 𝔽₂ⁿ. Our expansion proofs use only linear algebra and combinatorial arguments. The first construction gives local spectral HDXs of any constant dimension and subpolynomial degree exp(n^ε) for every ε > 0, improving on a construction by Golowich [Golowich, 2023] which achieves ε = 1/2. [Golowich, 2023] derives these HDXs by sparsifying the complete Grassmann poset of subspaces. The novelty in our construction is the ability to sparsify any expanding Grassmann posets, leading to iterated sparsification and much smaller degrees. The sparse Grassmannian (which is of independent interest in the theory of HDXs) serves as the generating set of the Cayley graph. Our second construction gives a 2-dimensional HDX of any polynomial degree exp(ε n) for any constant ε > 0, which is simultaneously a spectral expander and a coboundary expander. To the best of our knowledge, this is the first such non-trivial construction. We name it the Johnson complex, as it is derived from the classical Johnson scheme, whose vertices serve as the generating set of this Cayley graph. This construction may be viewed as a derandomization of the recent random geometric complexes of [Liu et al., 2023]. Establishing coboundary expansion through Gromov’s "cone method" and the associated isoperimetric inequalities is the most intricate aspect of this construction. While these two constructions are quite different, we show that they both share a common structure, resembling the intersection patterns of vectors in the Hadamard code. We propose a general framework of such "Hadamard-like" constructions in the hope that it will yield new HDXs.
Cite as

Yotam Dikstein, Siqi Liu, and Avi Wigderson. Sparser Abelian High Dimensional Expanders. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 7:1-7:98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dikstein_et_al:LIPIcs.CCC.2025.7,
  author =	{Dikstein, Yotam and Liu, Siqi and Wigderson, Avi},
  title =	{{Sparser Abelian High Dimensional Expanders}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{7:1--7:98},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.7},
  URN =		{urn:nbn:de:0030-drops-237013},
  doi =		{10.4230/LIPIcs.CCC.2025.7},
  annote =	{Keywords: Local spectral expander, coboundary expander, Grassmannian expander}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.169
Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings

Authors: Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, and Stanislav Živný

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Using the algebraic approach to promise constraint satisfaction problems, we establish complexity classifications of three natural variants of hypergraph colourings: standard nonmonochromatic colourings, conflict-free colourings, and linearly-ordered colourings. Firstly, we show that finding an 𝓁-colouring of a k-colourable r-uniform hypergraph is NP-hard for all constant 2 ≤ k ≤ 𝓁 and r ≥ 3. This provides a shorter proof of a celebrated result by Dinur et al. [FOCS'02/Combinatorica'05]. Secondly, we show that finding an 𝓁-conflict-free colouring of an r-uniform hypergraph that admits a k-conflict-free colouring is NP-hard for all constant 2 ≤ k ≤ 𝓁 and r ≥ 4, except for r = 4 and k = 2 (and any 𝓁); this case is solvable in polynomial time. The case of r = 3 is the standard nonmonochromatic colouring, and the case of r = 2 is the notoriously difficult open problem of approximate graph colouring. Thirdly, we show that finding an 𝓁-linearly-ordered colouring of an r-uniform hypergraph that admits a k-linearly-ordered colouring is NP-hard for all constant 3 ≤ k ≤ 𝓁 and r ≥ 4, thus improving on the results of Nakajima and Živný [ICALP'22/ACM TocT'23].
Cite as

Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, and Stanislav Živný. Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 169:1-169:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nakajima_et_al:LIPIcs.ICALP.2025.169,
  author =	{Nakajima, Tamio-Vesa and Verwimp, Zephyr and Wrochna, Marcin and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{169:1--169:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.169},
  URN =		{urn:nbn:de:0030-drops-235460},
  doi =		{10.4230/LIPIcs.ICALP.2025.169},
  annote =	{Keywords: hypergraph colourings, conflict-free colourings, unique-maximum colourings, linearly-ordered colourings}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.12
Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework

Authors: Sang Won Bae, Nicolau Oliver, and Evanthia Papadopoulou

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Given a set S of n colored sites, each s ∈ S associated with a distance-to-site function δ_s : ℝ² → ℝ, we consider two distance-to-color functions for each color: one takes the minimum of δ_s for sites s ∈ S in that color and the other takes the maximum. These two sets of distance functions induce two families of higher-order Voronoi diagrams for colors in the plane, namely, the minimal and maximal order-k color Voronoi diagrams, which include various well-studied Voronoi diagrams as special cases. In this paper, we derive an exact upper bound 4k(n-k)-2n on the total number of vertices in both the minimal and maximal order-k color diagrams for a wide class of distance functions δ_s that satisfy certain conditions, including the case of point sites S under convex distance functions and the L_p metric for any 1 ≤ p ≤ ∞. For the L_1 (or, L_∞) metric, and other convex polygonal metrics, we show that the order-k minimal diagram of point sites has O(min{k(n-k), (n-k)²}) complexity, while its maximal counterpart has O(min{k(n-k), k²}) complexity. To obtain these combinatorial results, we extend the Clarkson-Shor framework to colored objects, and demonstrate its application to several fundamental geometric structures, including higher-order color Voronoi diagrams, colored j-facets, and levels in the arrangements of piecewise linear/algebraic curves/surfaces. We also present iterative algorithms to compute higher-order color Voronoi diagrams.
Cite as

Sang Won Bae, Nicolau Oliver, and Evanthia Papadopoulou. Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bae_et_al:LIPIcs.SoCG.2025.12,
  author =	{Bae, Sang Won and Oliver, Nicolau and Papadopoulou, Evanthia},
  title =	{{Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.12},
  URN =		{urn:nbn:de:0030-drops-231647},
  doi =		{10.4230/LIPIcs.SoCG.2025.12},
  annote =	{Keywords: higher-order Voronoi diagrams, color Voronoi diagrams, Hausdorff Voronoi diagrams, colored j-facets, arrangements, Clarkson-Shor technique}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.63
The Maximum Clique Problem in a Disk Graph Made Easy

Authors: J. Mark Keil and Debajyoti Mondal

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
A disk graph is an intersection graph of disks in ℝ². Determining the computational complexity of finding a maximum clique in a disk graph is a long-standing open problem. In 1990, Clark, Colbourn, and Johnson gave a polynomial-time algorithm for computing a maximum clique in a unit disk graph. However, finding a maximum clique when disks are of arbitrary size is widely believed to be a challenging open problem. In this paper, we provide a new perspective to examine adjacencies in a disk graph that helps obtain the following results. - We design an 𝒪^*(n^{2k})-time algorithm, where 𝒪^* hides a polynomial factor, to find a maximum clique in a n-vertex disk graph with k different sizes of radii. This is polynomial for every fixed k, and thus settles the open question for the case when k = 2. - Given a set of n unit disks, we show how to compute a maximum clique inside each possible axis-aligned rectangle determined by the disk centers in O(n⁵log n)-time. This is at least a factor of n^{4/3} faster than applying the fastest known algorithm for finding a maximum clique in a unit disk graph for each rectangle independently. - We give an 𝒪^*(n^{2rk})-time algorithm to find a maximum clique in a n-vertex ball graph with k different sizes of radii where the ball centers lie on r parallel planes. This is polynomial for every fixed k and r, and thus contrasts the previously known NP-hardness result for finding a maximum clique in an arbitrary ball graph. - We design an 𝒪^*(n^{2k})-time algorithm to find a maximum clique in the intersection graph of a set S of n L-visible convex polygons, where k is the number of distinct shapes in S. This contrasts the known hardness result on finding a maximum clique in the intersection graph of unit disks and axis-aligned rectangles.
Cite as

J. Mark Keil and Debajyoti Mondal. The Maximum Clique Problem in a Disk Graph Made Easy. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 63:1-63:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{keil_et_al:LIPIcs.SoCG.2025.63,
  author =	{Keil, J. Mark and Mondal, Debajyoti},
  title =	{{The Maximum Clique Problem in a Disk Graph Made Easy}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{63:1--63:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.63},
  URN =		{urn:nbn:de:0030-drops-232155},
  doi =		{10.4230/LIPIcs.SoCG.2025.63},
  annote =	{Keywords: Geometric Intersection Graphs, Disk Graphs, Ball Graphs, Maximum Clique}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.19
Polychromatic Coloring of Tuples in Hypergraphs

Authors: Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, and Miloš Stojaković

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
A hypergraph H consists of a set V of vertices and a set E of hyperedges that are subsets of V. A t-tuple of H is a subset of t vertices of V. A t-tuple k-coloring of H is a mapping of its t-tuples into k colors. A coloring is called (t,k,f)-polychromatic if each hyperedge of E that has at least f vertices contains tuples of all the k colors. Let f_H(t,k) be the minimum f such that H has a (t,k,f)-polychromatic coloring. For a family of hypergraphs ℋ let f_H(t,k) be the maximum f_H(t,k) over all hypergraphs H in H. Determining f_H(t,k) has been an active research direction in recent years. This is challenging even for t = 1. We present several new results in this direction for t ≥ 2. - Let H be the family of hypergraphs H that is obtained by taking any set P of points in ℝ², setting V: = P and E: = {d ∩ P: d is a disk in ℝ²}. We prove that f_ H(2,k) ≤ 3.7^k, that is, the pairs of points (2-tuples) can be k-colored such that any disk containing at least 3.7^k points has pairs of all colors. We generalize this result to points and balls in higher dimensions. - For the family H of hypergraphs that are defined by grid vertices and axis-parallel rectangles in the plane, we show that f_H(2,k) ≤ √{ck ln k} for some constant c. We then generalize this to higher dimensions, to other shapes, and to tuples of larger size. - For the family H of shrinkable hypergraphs of VC-dimension at most d we prove that f_ H(d+1,k) ≤ c^k for some constant c = c(d). Towards this bound, we obtain a result of independent interest: Every hypergraph with n vertices and with VC-dimension at most d has a (d+1)-tuple T of depth at least n/c, i.e., any hyperedge that contains T also contains n/c other vertices. - For the relationship between t-tuple coloring and vertex coloring in any hypergraph H we establish the inequality 1/e⋅ tk^{1/t} ≤ f_H(t,k) ≤ f_H(1,tk^{1/t}). For the special case of k = 2, referred to as the bichromatic coloring, we prove that t+1 ≤ f_H(t,2) ≤ max{f_H(1,2), t+1}; this improves upon the previous best known upper bound. - We study the relationship between tuple coloring and epsilon nets. In particular we show that if f_H(1,k) = O(k) for a hypergraph H with n vertices, then for any 0 < ε < 1 the t-tuples of H can be partitioned into Ω((εn/t)^t) ε-t-nets. This bound is tight when t is a constant.
Cite as

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, and Miloš Stojaković. Polychromatic Coloring of Tuples in Hypergraphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SoCG.2025.19,
  author =	{Biniaz, Ahmad and De Carufel, Jean-Lou and Maheshwari, Anil and Smid, Michiel and Smorodinsky, Shakhar and Stojakovi\'{c}, Milo\v{s}},
  title =	{{Polychromatic Coloring of Tuples in Hypergraphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.19},
  URN =		{urn:nbn:de:0030-drops-231718},
  doi =		{10.4230/LIPIcs.SoCG.2025.19},
  annote =	{Keywords: Hypergraph Coloring, Polychromatic Coloring, Geometric Hypergraphs, Cover Decomposable Hypergraphs, Epsilon Nets}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.43
On Spheres with k Points Inside

Authors: Herbert Edelsbrunner, Alexey Garber, and Morteza Saghafian

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We generalize a classical result by Boris Delaunay that introduced Delaunay triangulations. In particular, we prove that for a locally finite and coarsely dense generic point set A in ℝ^d, every generic point of ℝ^d belongs to exactly binom(d+k,d) simplices whose vertices belong to A and whose circumspheres enclose exactly k points of A. We extend this result to the cases in which the points are weighted, and when A contains only finitely many points in ℝ^d or in 𝕊^d. Furthermore, we use the result to give a new geometric proof for the fact that volumes of hypersimplices are Eulerian numbers.
Cite as

Herbert Edelsbrunner, Alexey Garber, and Morteza Saghafian. On Spheres with k Points Inside. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 43:1-43:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2025.43,
  author =	{Edelsbrunner, Herbert and Garber, Alexey and Saghafian, Morteza},
  title =	{{On Spheres with k Points Inside}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{43:1--43:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.43},
  URN =		{urn:nbn:de:0030-drops-231951},
  doi =		{10.4230/LIPIcs.SoCG.2025.43},
  annote =	{Keywords: Triangulations, higher-order Delaunay triangulations, hypertriangulations, Delone sets, k-sets, Worpitzky’s identity, hypersimplices}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.75
Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers

Authors: Elizaveta Streltsova and Uli Wagner

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
A long-standing conjecture of Eckhoff, Linhart, and Welzl, which would generalize McMullen’s Upper Bound Theorem for polytopes and refine asymptotic bounds due to Clarkson, asserts that for k ⩽ ⌊(n-d-2)/2⌋, the complexity of the (⩽ k)-level in a simple arrangement of n hemispheres in S^d is maximized for arrangements that are polar duals of neighborly d-polytopes. We prove this conjecture in the case n = d+4. By Gale duality, this implies the following result about crossing numbers: In every spherical arc drawing of K_n in S² (given by a set V ⊂ S² of n unit vectors connected by spherical arcs), the number of crossings is at least 1/4 ⌊n/2⌋ ⌊(n-1)/2⌋ ⌊(n-2)/2⌋ ⌊(n-3)/2⌋. This lower bound is attained if every open linear halfspace contains at least ⌊(n-2)/2⌋ of the vectors in V. Moreover, we determine the space of all linear and affine relations that hold between the face numbers of levels in simple arrangements of n hemispheres in S^d. This completes a long line of research on such relations, answers a question posed by Andrzejak and Welzl in 2003, and generalizes the classical fact that the Dehn-Sommerville relations generate all linear relations between the face numbers of simple polytopes (which correspond to the 0-level). To prove these results, we introduce the notion of the g-matrix, which encodes the face numbers of levels in an arrangement and generalizes the classical g-vector of a polytope.
Cite as

Elizaveta Streltsova and Uli Wagner. Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{streltsova_et_al:LIPIcs.SoCG.2025.75,
  author =	{Streltsova, Elizaveta and Wagner, Uli},
  title =	{{Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{75:1--75:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.75},
  URN =		{urn:nbn:de:0030-drops-232276},
  doi =		{10.4230/LIPIcs.SoCG.2025.75},
  annote =	{Keywords: Levels in arrangements, k-sets, k-facets, convex polytopes, f-vector, h-vector, g-vector, Dehn-Sommerville relations, Radon partitions, Gale duality, g-matrix}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.8
Eight-Partitioning Points in 3D, and Efficiently Too

Authors: Boris Aronov, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner

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

Abstract
An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}).
Cite as

Boris Aronov, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner. Eight-Partitioning Points in 3D, and Efficiently Too. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2024.8,
  author =	{Aronov, Boris and Basit, Abdul and Ramesh, Indu and Tasinato, Gianluca and Wagner, Uli},
  title =	{{Eight-Partitioning Points in 3D, and Efficiently Too}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{8:1--8:15},
  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.8},
  URN =		{urn:nbn:de:0030-drops-199538},
  doi =		{10.4230/LIPIcs.SoCG.2024.8},
  annote =	{Keywords: Mass partitions, partitions of points in three dimensions, Borsuk-Ulam Theorem, Ham-Sandwich Theorem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.34
Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs

Authors: Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the "linearly ordered chromatic number" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).
Cite as

Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{filakovsky_et_al:LIPIcs.STACS.2024.34,
  author =	{Filakovsk\'{y}, Marek and Nakajima, Tamio-Vesa and Opr\v{s}al, Jakub and Tasinato, Gianluca and Wagner, Uli},
  title =	{{Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{34:1--34:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.34},
  URN =		{urn:nbn:de:0030-drops-197445},
  doi =		{10.4230/LIPIcs.STACS.2024.34},
  annote =	{Keywords: constraint satisfaction problem, hypergraph colouring, promise problem, topological methods}
}
Document
Position
DOI: 10.4230/TGDK.1.1.5
Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities

Authors: Jiaoyan Chen, Hang Dong, Janna Hastings, Ernesto Jiménez-Ruiz, Vanessa López, Pierre Monnin, Catia Pesquita, Petr Škoda, and Valentina Tamma

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
The term life sciences refers to the disciplines that study living organisms and life processes, and include chemistry, biology, medicine, and a range of other related disciplines. Research efforts in life sciences are heavily data-driven, as they produce and consume vast amounts of scientific data, much of which is intrinsically relational and graph-structured. The volume of data and the complexity of scientific concepts and relations referred to therein promote the application of advanced knowledge-driven technologies for managing and interpreting data, with the ultimate aim to advance scientific discovery. In this survey and position paper, we discuss recent developments and advances in the use of graph-based technologies in life sciences and set out a vision for how these technologies will impact these fields into the future. We focus on three broad topics: the construction and management of Knowledge Graphs (KGs), the use of KGs and associated technologies in the discovery of new knowledge, and the use of KGs in artificial intelligence applications to support explanations (explainable AI). We select a few exemplary use cases for each topic, discuss the challenges and open research questions within these topics, and conclude with a perspective and outlook that summarizes the overarching challenges and their potential solutions as a guide for future research.
Cite as

Jiaoyan Chen, Hang Dong, Janna Hastings, Ernesto Jiménez-Ruiz, Vanessa López, Pierre Monnin, Catia Pesquita, Petr Škoda, and Valentina Tamma. Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 5:1-5:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{chen_et_al:TGDK.1.1.5,
  author =	{Chen, Jiaoyan and Dong, Hang and Hastings, Janna and Jim\'{e}nez-Ruiz, Ernesto and L\'{o}pez, Vanessa and Monnin, Pierre and Pesquita, Catia and \v{S}koda, Petr and Tamma, Valentina},
  title =	{{Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{5:1--5:33},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.5},
  URN =		{urn:nbn:de:0030-drops-194791},
  doi =		{10.4230/TGDK.1.1.5},
  annote =	{Keywords: Knowledge graphs, Life science, Knowledge discovery, Explainable AI}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.10
Enclosing Depth and Other Depth Measures

Authors: Patrick Schnider

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We study families of depth measures defined by natural sets of axioms. We show that any such depth measure is a constant factor approximation of Tukey depth. We further investigate the dimensions of depth regions, showing that the Cascade conjecture, introduced by Kalai for Tverberg depth, holds for all depth measures which satisfy our most restrictive set of axioms, which includes Tukey depth. Along the way, we introduce and study a new depth measure called enclosing depth, which we believe to be of independent interest, and show its relation to a constant-fraction Radon theorem on certain two-colored point sets.
Cite as

Patrick Schnider. Enclosing Depth and Other Depth Measures. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{schnider:LIPIcs.ISAAC.2021.10,
  author =	{Schnider, Patrick},
  title =	{{Enclosing Depth and Other Depth Measures}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.10},
  URN =		{urn:nbn:de:0030-drops-154431},
  doi =		{10.4230/LIPIcs.ISAAC.2021.10},
  annote =	{Keywords: Depth measures, Tukey depth, Tverberg theorem, Combinatorial Geometry}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.62
Barycentric Cuts Through a Convex Body

Authors: Zuzana Patáková, Martin Tancer, and Uli Wagner

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

Abstract
Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p₀ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n ≥ 2, there are always at least three distinct barycentric cuts through the point p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3.
Cite as

Zuzana Patáková, Martin Tancer, and Uli Wagner. Barycentric Cuts Through a Convex Body. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{patakova_et_al:LIPIcs.SoCG.2020.62,
  author =	{Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli},
  title =	{{Barycentric Cuts Through a Convex Body}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{62:1--62:16},
  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.62},
  URN =		{urn:nbn:de:0030-drops-122201},
  doi =		{10.4230/LIPIcs.SoCG.2020.62},
  annote =	{Keywords: convex body, barycenter, Tukey depth, smooth manifold, critical points}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.67
Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)

Authors: Uli Wagner and Emo Welzl

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

Abstract
Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a non-extreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity. For sets P of n points in general position, we show that the bistellar flip graph is (n-3)-connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction).
Cite as

Uli Wagner and Emo Welzl. Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 67:1-67:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wagner_et_al:LIPIcs.SoCG.2020.67,
  author =	{Wagner, Uli and Welzl, Emo},
  title =	{{Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{67:1--67:16},
  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.67},
  URN =		{urn:nbn:de:0030-drops-122259},
  doi =		{10.4230/LIPIcs.SoCG.2020.67},
  annote =	{Keywords: triangulation, flip graph, graph connectivity, associahedron, subdivision, convex decomposition, flippable edge, flip complex, regular triangulation, bistellar flip graph, secondary polytope, polyhedral subdivision}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.38
The Crossing Tverberg Theorem

Authors: Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner

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

Abstract
The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.
Cite as

Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. The Crossing Tverberg Theorem. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fulek_et_al:LIPIcs.SoCG.2019.38,
  author =	{Fulek, Radoslav and G\"{a}rtner, Bernd and Kupavskii, Andrey and Valtr, Pavel and Wagner, Uli},
  title =	{{The Crossing Tverberg Theorem}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{38:1--38:13},
  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.38},
  URN =		{urn:nbn:de:0030-drops-104423},
  doi =		{10.4230/LIPIcs.SoCG.2019.38},
  annote =	{Keywords: Discrete geometry, Tverberg theorem, Crossing Tverberg theorem}
}
  • Refine by Type
  • 23 Document/PDF
  • 9 Document/HTML

  • Refine by Publication Year
  • 8 2025
  • 2 2024
  • 1 2023
  • 1 2021
  • 2 2020
  • Show More...

  • Refine by Author
  • 14 Wagner, Uli
  • 4 Patáková, Zuzana
  • 4 Tancer, Martin
  • 3 Goaoc, Xavier
  • 3 Paták, Pavel
  • Show More...

  • Refine by Series/Journal
  • 22 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 10 Theory of computation → Computational geometry
  • 2 Mathematics of computing → Discrete mathematics
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Applied computing → Life and medical sciences
  • 1 Computing methodologies → Knowledge representation and reasoning
  • Show More...

  • Refine by Keyword
  • 2 Tukey depth
  • 2 Tverberg theorem
  • 2 k-sets
  • 1 3-manifold
  • 1 Ball Graphs
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact