Transversals and colorings of simplicial spheres

DOI10.1007/S00454-023-00520-1arXiv2111.06560OpenAlexW3211691555MaRDI QIDQ6151037FDOQ6151037

Authors: Joseph Briggs, Michael Gene Dobbins, Seunghun Lee 

Publication date: 9 February 2024

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

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.

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

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

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)

Cites Work

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

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)