Nerves, minors, and piercing numbers

DOI10.1090/TRAN/7608zbMATH Open1414.05202arXiv1706.05181OpenAlexW2645992437WikidataQ129580878 ScholiaQ129580878MaRDI QIDQ5380512FDOQ5380512

Authors: Seunghun Lee, Andreas Holmsen, Min-Ki Kim 

Publication date: 5 June 2019

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Abstract: We make the first step towards a "nerve theorem" for graphs. Let $G$ be a simple graph and let $mathcalF$ be a family of induced subgraphs of $G$ such that the intersection of any members of $mathcalF$ is either empty or connected. We show that if the nerve complex of $mathcalF$ has non-vanishing homology in dimension three, then $G$ contains the complete graph on five vertices as a minor. As a consequence we confirm a conjecture of Goaoc concerning an extension of the planar $(p,q)$ theorem due to Alon and Kleitman: Let $mathcalF$ be a finite family of open connected sets in the plane such that the intersection of any members of $mathcalF$ is either empty or connected. If among any $pgeq3$ members of $mathcalF$ there are some three that intersect, then there is a set of $C$ points which intersects every member of $mathcalF$, where $C$ is a constant depending only on $p$.

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

Recommendations

• Nerve complexes of circular arcs
• Intersection patterns of planar sets
• Multinerves and Helly numbers of acyclic families
• Bounding the piercing number
• Transversal numbers for hypergraphs arising in geometry

zbMATH Keywords

nerve theorem for graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Helly-type theorems and geometric transversal theory (52A35)

Cites Work

• Title not available (Why is that?)
• Graph minors. XX: Wagner's conjecture
• A generalization of Caratheodory's theorem
• Über eine Eigenschaft der ebenen Komplexe
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph theory
• On the imbedding of systems of compacta in simplicial complexes
• An upper-bound theorem for families of convex sets
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Transversal numbers for hypergraphs arising in geometry
• Helly-type theorems for the diameter
• A note on the colorful fractional Helly theorem
• A Problem of Geometry in R n
• Intersection patterns of convex sets
• Über eine Variante zum Hellyschen Satz
• Supersaturated graphs and hypergraphs
• A fractional Helly theorem for convex lattice sets
• On a minor-monotone graph invariant
• Convex sets in the plane with three of every four meeting
• Point Selections and Weak ε-Nets for Convex Hulls
• Leray numbers of projections and a topological Helly-type theorem
• The clique complex and hypergraph matching
• Nerves, fibers and homotopy groups
• Intersection Patterns of Convex Sets via Simplicial Complexes: A Survey
• A variation on the homological nerve theorem
• A topological colorful Helly theorem
• Helly numbers of acyclic families
• Bounding the piercing number
• Bounding Helly numbers via Betti numbers
• Title not available (Why is that?)
• A minor-monotone graph parameter based on oriented matroids
• An approximate nerve theorem
• Title not available (Why is that?)

Cited In (3)

• Nerve complexes of circular arcs
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• The Longest Shortest Piercing

This page was built for publication: Nerves, minors, and piercing numbers

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