Transversal numbers of stacked spheres

DOI10.1016/J.DISC.2024.114061MaRDI QIDQ6436658zbMATH OpenOpenAlexFDO

Authors Min Ho Cho, Jinha Kim

Publication date 15 May 2023

Full work available at URL https://doi.org/10.1016/j.disc.2024.114061

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Transversal (matching) theory (05D15) Combinatorial aspects of simplicial complexes (05E45) Helly-type theorems and geometric transversal theory (52A35) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Abstract: A stacked $d$-sphere $S$ is the boundary complex of a stacked $(d+1)$-ball, which is obtained by taking cone over a free $d$-face repeatedly from a $(d+1)$-simplex. A stacked sphere $S$ is called linear if every cone is taken over a face added in the previous step. In this paper, we study the transversal number of facets of stacked $d$-spheres, denoted by $au(S)$, which is the minimum number of vertices intersecting with all facets. Briggs, Dobbins and Lee showed that the transversal ratio of a stacked $d$-sphere is bounded above by $frac2d+2+o(1)$ and can be as large as $frac2d+3$. We improve the lower bound by constructing linear stacked $d$-spheres with transversal ratio $frac63d+8$ and general stacked $d$-spheres with transversal ratio $frac2d+3(d+2{)}^2$. Finally, we show that $frac63d+8$ is optimal for linear stacked $2$-spheres, that is, the transversal ratio is at most $frac37+o(1)$ for linear stacked $2$-spheres.

Recommendations

• Transversals and colorings of simplicial spheres
• The Threshold for Stacked Triangulations
• Separation index of graphs and stacked 2-spheres
• Many triangulated spheres
• On k-stellated and k-stacked spheres

Cited in

(2)

• Transversals and colorings of simplicial spheres
• On colorings of hypergraphs embeddable in \(\mathbb{R}^d\)

This page was built for publication: Transversal numbers of stacked spheres

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