On the maximum number of points in a maximal intersecting family of finite sets

preprint2014arXivOpen access

Abstract

Paul Erdős and László Lovász proved in a landmark article that, for any positive integer kk, up to isomorphism there are only finitely many maximal intersecting families of k−k-sets (maximal k−k-cliques). So they posed the problem of determining or estimating the largest number N(k)N(k) of the points in such a family. They also proved by means of an example that N(k)≥2k−2+12(2k−2k−1)N(k)\geq2k-2+\frac{1}{2}\binom{2k-2}{k-1}. Much later, Zsolt Tuza proved that the bound is best possible up to a multiplicative constant by showing that asymptotically N(k)N(k) is at most 44 times this lower bound. In this paper we reduce the gap between the lower and upper bound by showing that asymptotically N(k)N(k) is at most 33 times the Erdős-Lovász lower bound. Conjecturally, the explicit upper bound obtained in this paper is only double the lower bound.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.