Petruska's question on planar convex sets

DOI10.1016/J.DISC.2020.111956MaRDI QIDQ776273zbMATH OpenOpenAlexFDO

Authors Adam S. Jobson, André E. Kézdy, Timothy J. Pervenecki, Géza Tóth, Jeno Lehel

Publication date 8 July 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

convex setsHelly's theoremset systems2-representable hypergraphsErdős's arrow problems

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph representations (geometric and intersection representations, etc.) (05C62) Hypergraphs (05C65)

Abstract: Given $2k-1$ convex sets in $R^2$ such that no point of the plane is covered by more than $k$ of the sets, is it true that there are two among the convex sets whose union contains all $k$-covered points of the plane? This question due to Gy. Petruska has an obvious affirmative answer for $k=1,2,3$; we show here that the claim is also true for $k=4$, and we present a counterexample for $k=5$. We explain how Petruska's geometry question fits into the classical hypergraph extremal problems, called arrow problems, proposed by P. ErdH{o}s.

Recommendations

• Convex sets in the plane with three of every four meeting
• On Erdős-Szekeres-type problems for \(k\)-convex point sets
• Eckhoff's problem on convex sets in the plane
• On Erdős-Szekeres-type problems for \(k\)-convex point sets
• A note on convex subsets of \(\mathbb Z^k\)

Cites work

• scientific article; zbMATH DE number 3150463 (Why is no real title available?)
• scientific article; zbMATH DE number 3155986 (Why is no real title available?)
• scientific article; zbMATH DE number 3472051 (Why is no real title available?)
• scientific article; zbMATH DE number 480237 (Why is no real title available?)
• scientific article; zbMATH DE number 3333195 (Why is no real title available?)
• A Theorem on k-Saturated Graphs
• A generalization of Caratheodory's theorem
• Characterization of f-vectors of families of convex sets in \({\mathbb{R}}^ d\). I: Necessity of Eckhoff's conditions
• Characterization of f-vectors of families of convex sets in \({\mathbb{R}}^ d\). II: Sufficiency of Eckhoff's conditions
• Critical hypergraphs and interesting set-pair systems
• Intersection Patterns of Convex Sets via Simplicial Complexes: A Survey
• On Certain Intersection Properties of Convex Sets
• Upper bound on the order of tau-critical hypergraphs
• d-collapsing and nerves of families of convex sets

Cited in

(5)

• Exact hyperplane covers for subsets of the hypercube
• The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform \(\tau\)-critical hypergraphs
• Eckhoff's problem on convex sets in the plane
• Orientation of convex sets
• The Szemerédi-Petruska conjecture for a few small values

This page was built for publication: Petruska's question on planar convex sets

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