On the ratio of maximum and minimum degree in maximal intersecting families

DOI10.1016/J.DISC.2012.10.007MaRDI QIDQ1928459zbMATH OpenOpenAlexFDO

Authors Zoltán Lóránt Nagy, Lale Özkahya, Balázs Patkós, Máté Vizer

Publication date 3 January 2013

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

blocking setsintersecting familiesmaximum and minimum degree

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Abstract: To study how balanced or unbalanced a maximal intersecting family $$ is we consider the ratio $mathcalR(mathcalF)=fracDelta(mathcalF)delta(mathcalF)$ of its maximum and minimum degree. We determine the order of magnitude of the function $m(n,r)$, the minimum possible value of $mathcalR(mathcalF)$, and establish some lower and upper bounds on the function $M(n,r)$, the maximum possible value of $mathcalR(mathcalF)$. To obtain constructions that show the bounds on $m(n,r)$ we use a theorem of Blokhuis on the minimum size of a non-trivial blocking set in projective planes.

Recommendations

• The unbalance of set systems
• Intersecting balanced families of sets
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• Maximal intersecting families
• Multiply-intersecting families

Cited in

(1)

• The unbalance of set systems

This page was built for publication: On the ratio of maximum and minimum degree in maximal intersecting families

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