An analogue of the Hilton-Milner theorem for weak compositions

DOI10.4134/BKMS.2015.52.3.1007MaRDI QIDQ5265572zbMATH OpenFDO

Authors Cheng Yeaw Ku, K. B. Wong

Publication date 28 July 2015

Published in Bulletin of the Korean Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.1592, http://www.mathnet.or.kr/mathnet/kms_content.php?no=412677

zbMATH Keywords

weak compositionscross-intersecting familyHilton-MilnerErdös-Ko-Rado

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: Let $mathbb{N}_0$ be the set of non-negative integers, and let $P(n,l)$ denote the set of all weak compositions of $n$ with $l$ parts, i.e., $P(n,l)=(x_1,x_2,dots,x_l)inmathbb{N}_0^l:x_1+x_2+cdots+x_l=n$. For any element $mathbfu=(u_1,u_2,dots,u_l)inP(n,l)$, denote its $i$th-coordinate by $mathbfu(i)$, i.e., $mathbfu(i)=u_i$. A family $mathcalAsubseteqP(n,l)$ is said to be $t$-intersecting if $verti:mathbfu(i)=mathbfv(i)vertgeqt$ for all $mathbfu,mathbfvinmathcalA$. A family $mathcalAsubseteqP(n,l)$ is said to be trivially $t$-intersecting if there is a $t$-set $T$ of $1,2,dots,l$ and elements $y_{s}inmathbb{N}_0$ ($sinT$) such that $mathcalA=mathbfuinP(n,l):mathbfu(j)=y_{j}mforalljinT$. We prove that given any positive integers $l,t$ with $lgeq2t+3$, there exists a constant $n_0(l,t)$ depending only on $l$ and $t$, such that for all $ngeq{n}_0(l,t)$, if $mathcalAsubseteqP(n,l)$ is non-trivially $t$-intersecting then �egin{equation} vert mathcal{A} vertleq {n+l-t-1 choose l-t-1}-{n-1 choose l-t-1}+t.

otag end{equation} Moreover, equality holds if and only if there is a $t$-set $T$ of $1,2,dots,l$ such that �egin{equation} mathcal A=�igcup_{sin {1,2,dots, l}setminus T} mathcal A_scup left{ mathbf q_i : iin T ight}, otag end{equation} where �egin{align} mathcal{A}_s & ={mathbf uin P(n,l) : mathbf u(j)=0 { m for all} jin T { m and} mathbf u(s)=0}

otag end{align} and $mathbf{q}_{i}inP(n,l)$ with $mathbf{q}_i(j)=0$ for all $jin1,2,dots,lsetminusi$ and $mathbf{q}_i(i)=n$.

Recommendations

• An analogue of the Erdős-Ko-Rado theorem for weak compositions
• On \(r\)-cross \(t\)-intersecting families for weak compositions
• An analogue of the Hilton-Milner theorem for set partitions
• A short proof of an Erdős-Ko-Rado theorem for compositions
• Non-trivial intersecting families

Cited in

(12)

• The Hilton-Milner theorem for finite affine spaces
• Non-trivial \(t\)-intersection in the function lattice
• The Hilton-Milner theorem for attenuated spaces
• Diversity and intersecting theorems for weak compositions
• Erdős-Ko-Rado theorems for set partitions with certain block size
• An analogue of the Hilton-Milner theorem for set partitions
• An analogue of the Erdős-Ko-Rado theorem for weak compositions
• On \(r\)-cross \(t\)-intersecting families for weak compositions
• A non-trivial intersection theorem for permutations with fixed number of cycles
• A Deza-Frankl type theorem for set partitions
• On diversity of certain \(t\)-intersecting families
• The Hilton-Milner theorem for the distance-regular graphs of bilinear forms

This page was built for publication: An analogue of the Hilton-Milner theorem for weak compositions

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