Petruska's question on planar convex sets

DOI10.1016/J.DISC.2020.111956zbMATH Open1443.05133arXiv1912.08080OpenAlexW3029998997MaRDI QIDQ776273FDOQ776273

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)

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.

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

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\)

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)

Cites Work

• Title not available (Why is that?)
• 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
• d-collapsing and nerves of families of convex sets
• Critical hypergraphs and interesting set-pair systems
• A Theorem on k-Saturated Graphs
• Title not available (Why is that?)
• Intersection Patterns of Convex Sets via Simplicial Complexes: A Survey
• On Certain Intersection Properties of Convex Sets
• Title not available (Why is that?)
• Upper bound on the order of tau-critical hypergraphs
• Title not available (Why is that?)
• Title not available (Why is that?)

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)