Transversals and colorings of simplicial spheres

DOI10.1007/S00454-023-00520-1MaRDI QIDQ6151037zbMATH OpenOpenAlexFDO

Authors Joseph Briggs, Michael Gene Dobbins, Seunghun Lee

Publication date 9 February 2024

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.06560

zbMATH Keywords

polytopestransversalschromatic numbersgeometric hypergraphssimplicial spheres

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Transversal (matching) theory (05D15) Helly-type theorems and geometric transversal theory (52A35)

Abstract: Motivated from the surrounding property of a point set in $mathbb{R}^d$ introduced by Holmsen, Pach and Tverberg, we consider the transversal number and chromatic number of a simplicial sphere. As an attempt to give a lower bound for the maximum transversal ratio of simplicial $d$-spheres, we provide two infinite constructions. The first construction gives infintely many $(d+1)$-dimensional simplicial polytopes with the transversal ratio exactly $frac2d+2$ for every $dgeq2$. In the case of $d=2$, this meets the previously well-known upper bound $1/2$ tightly. The second gives infinitely many simplicial 3-spheres with the transversal ratio greater than $1/2$. This was unexpected from what was previously known about the surrounding property. Moreover, we show that, for $dgeq3$, the facet hypergraph $mathcalF(mathsfK)$ of a $d$-dimensional simplicial sphere $mathsfK$ has the chromatic number $chi(mathcalF(mathsfK))inO(n^{fraclceild/2ceil-1d})$, where $n$ is the number of vertices of $mathsfK$. This slightly improves the upper bound previously obtained by Heise, Panagiotou, Pikhurko, and Taraz.

Recommendations

• Transversal numbers of stacked spheres
• Chromatic numbers of simplicial manifolds
• Many triangulated 3-spheres
• On the chromatic number of 2-dimensional spheres
• Empty monochromatic simplices

Cites work

• scientific article; zbMATH DE number 17653 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 3303053 (Why is no real title available?)
• 2-Isomorphic Graphs
• Coloring \(d\)-embeddable \(k\)-uniform hypergraphs
• Coloring face-hypergraphs of graphs on surfaces
• Enumerating neighborly polytopes and oriented matroids
• Every planar map is four colorable
• Extremal problems for geometric hypergraphs
• Lectures on Polytopes
• Many neighborly spheres
• Neighborly 4-polytopes with 9 vertices
• On the independence ratio of a graph
• Oriented Matroids
• Points surrounding the origin
• Realization spaces of polytopes
• The Upper Bound Conjecture and Cohen-Macaulay Rings
• The classification of simplicial 3-spheres with nine vertices into polytopes and nonpolytopes
• The maximum numbers of faces of a convex polytope
• The number of faces of a simplicial convex polytope
• The probabilistic method

Cited in

(1)

• Transversal numbers of stacked spheres

This page was built for publication: Transversals and colorings of simplicial spheres

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6151037)