A preliminary result for generalized intersecting families

preprint2021arXivOpen access

Abstract

Intersecting families and blocking sets feature prominently in extremal combinatorics. We examine the following generalization of an intersecting family investigated by Hajnal, Rothschild, and others. If s≥1s \geq 1, k≥2k \geq 2, and u≥1u \geq 1 are integers, then say that an ss-uniform family F\mathcal{F} is (k,u)(k,u)-intersecting if for all A1,A2,⋯ ,Ak∈FA_1, A_2, \cdots, A_k \in \mathcal{F}, ∣Ai∩Aj∣≥u|A_i \cap A_j| \geq u for some 1≤i<j≤k1 \leq i < j \leq k. In this note, we investigate the following parameter. If ss, kk, uu, ℓ\ell are integers satisfying s≥1s \geq 1, k≥2k \geq 2, 1≤u≤s1 \leq u \leq s, and 2≤ℓ<k2 \leq \ell < k, then let Nk,ℓ(u)(s)N^{(u)}_{k,\ell}(s) denote the smallest integer rr, if it exists, such that any (k,u)(k,u)-intersecting ss-uniform family is the union of at most rr families that are (ℓ,u)(\ell,u)-intersecting. Using a Sunflower Lemma type argument, we prove that Nk,ℓ(u)(s)N^{(u)}_{k,\ell}(s) always exists and that the following inequality always holds: $$N^{(u)}_{k,\ell}(s) \; \leq \; \bigg{\lceil} \dfrac{ k - 1 }{\ell - 1} \cdot {s \choose u} \bigg{\rceil}$$

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.