An upper bound for the size of a kk-uniform intersecting family with covering number kk

preprint2016arXivOpen access

Abstract

Let r(k)r(k) denote the maximum number of edges in a kk-uniform intersecting family with covering number kk. Erdős and Lovász proved that ⌊k!(e−1)⌋≤r(k)≤kk. \lfloor k! (e-1) \rfloor \leq r(k) \leq k^k. Frankl, Ota, and Tokushige improved the lower bound to r(k)≥(k/2)k−1r(k) \geq \left( k/2 \right)^{k-1}, and Tuza improved the upper bound to r(k)≤(1−e−1+o(1))kkr(k) \leq (1-e^{-1}+o(1))k^k. We establish that r(k)≤(1+o(1))kk−1 r(k) \leq (1 + o(1)) k^{k-1}.

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.