Erd\H{o}s-Ko-Rado Theorem for Bounded Multisets

DOI10.1016/J.JCTA.2024.105888OpenAlexW4392797078MaRDI QIDQ6429243FDOQ6429243

Authors Jia Qi Liao, Zequn Lv, Mengyu Cao, Mei Lu

Publication date 12 March 2023

Full work available at URL https://doi.org/10.1016/j.jcta.2024.105888

Extremal set theory (05D05) Graph theory (05Cxx) Enumerative combinatorics (05Axx)

Abstract: Let

k, m, n

be positive integers with

k g e q 2

. A

k

-multiset of

[n]_{m}

is a collection of

k

integers from the set

1, 2, l d o t s, n

in which the integers can appear more than once but at most

m

times. A family of such

k

-multisets is called an intersecting family if every pair of

k

-multisets from the family have non-empty intersection. A finite sequence of real numbers

a_{1}, a_{2}, l d o t s, a_{n}

is said to be unimodal if there is some

k i n 1, 2, l d o t s, n

, such that

a_{1} l e q a_{2} l e q l d o t s l e q a_{k - 1} l e q a_{k} g e q a_{k + 1} g e q l d o t s g e q a_{n}

. Given

m, n, k

, denote

C_{k, l}

as the coefficient of

x^{k}

in the generating function

(s u m_{i = 1}^{m} x^{i})^{l}

, where

1 l e q l l e q n

. In this paper, we first show that the sequence of

C_{k, 1}, C_{k, 2}, l d o t s, C_{k, n}

is unimodal. Then we use this as a tool to prove that the intersecting family in which every

k

-multiset contains a fixed element attains the maximum cardinality for

n g e q k + l c e i l k / m c e i l

. In the special case when

m = 1

and

m = i n f t y

, our result gives rise to the famous ErdH{o}s-Ko-Rado Theorem and an unbounded multiset version for this problem given by Meagher and Purdy, respectively. The main result in this paper can be viewed as a bounded multiset version of the ErdH{o}s-Ko-Rado Theorem.

Recommendations

Cited In (1)

Intersecting families of polynomials over finite fields

This page was built for publication: Erd\H{o}s-Ko-Rado Theorem for Bounded Multisets

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