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

DOI10.1016/J.JCTA.2024.105888arXiv2303.06647OpenAlexW4392797078MaRDI QIDQ6429243FDOQ6429243

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

Publication date: 12 March 2023

Abstract: Let $k,m,n$ be positive integers with $kgeq2$. A $k$-multiset of $[n{]}_m$ is a collection of $k$ integers from the set $1,2,ldots,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,ldots,a_n$ is said to be unimodal if there is some $kin1,2,ldots,n$, such that $a_{1}leq{a}_{2}leqldotsleq{a}_{k-1}leq{a}_{k}geq{a}_{k+1}geqldotsgeq{a}_n$. Given $m,n,k$, denote $C_{k,l}$ as the coefficient of $x^k$ in the generating function $(su{m}_{i=1}^m{x}^i{)}^l$, where $1leqlleqn$. In this paper, we first show that the sequence of $C_{k,1},C_{k,2},ldots,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 $ngeqk+lceilk/mceil$. In the special case when $m=1$ and $m=infty$, 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.

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

Recommendations

• scientific article; zbMATH DE number 3487529
• scientific article; zbMATH DE number 3080938
• scientific article; zbMATH DE number 3407754
• Eine Bemerkung zum Satz von Vitali über Konvergenz von Funktionenfolgen: Dem stets hilftsbereiten Herrn Kollegen H. L. Schmid, gewidmet
• scientific article; zbMATH DE number 1839786
• Holomorphic mappings of complex manifolds
• scientific article; zbMATH DE number 5593209
• On \(\varepsilon\)-representations
• scientific article

Mathematics Subject Classification ID

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

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)