An analogue of the Hilton-Milner theorem for weak compositions

DOI10.4134/BKMS.2015.52.3.1007zbMATH Open1318.05086arXiv1311.1592MaRDI QIDQ5265572FDOQ5265572

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)

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$.

Full work available at URL: https://arxiv.org/abs/1311.1592

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cited In (9)

• The Hilton-Milner theorem for attenuated spaces
• Non-trivial \(t\)-intersection in the function lattice
• Title not available (Why is that?)
• The Hilton-Milner theorem for finite affine spaces
• A Deza-Frankl type theorem for set partitions
• Erdős-Ko-Rado theorems for set partitions with certain block size
• A non-trivial intersection theorem for permutations with fixed number of cycles
• Diversity and intersecting theorems for weak compositions
• 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)