An analogue of the Erd{\H o}s matching conjecture for weak compositions
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Let $\mathbb N_0$ be the set of non-negative integers, and let $P(n,k)$ denote the set of all weak compositions of $n$ with $k$ parts, i.e., $P(n,k)=\{ (x_1,x_2,\dots, x_k)\in\mathbb N_0^k : x_1+x_2+\cdots+x_k=n\}$. For any element $\mathbf u=(u_1,u_2,\dots, u_k)\in P(n,k)$, denote its $i$th-coordinate by $\mathbf u(i)$, i.e., $\mathbf u(i)=u_i$. A subset $S\subseteq P(n,k)$ is a matching if $\vert \{ i : \mathbf u(i)=\mathbf v(i)\} \vert=0$ (i.e., $\{ i :\mathbf u(i)=\mathbf v(i)\}=\varnothing$) for all distinct $\mathbf u,\mathbf v\in S$. The matching number of a family $\mathcal A\subseteq P(n,k)$ is denoted by $\nu_w(\mathcal A)$ and is defined to be the maximum size of a matching in $\mathcal A$. In this paper, we determine the maximum size of a family $\mathcal A\subseteq P(n,k)$ subject to the condition $\nu_w(\mathcal A)\leq s$.
Abstract
Let $\mathbb N_0$ be the set of non-negative integers, and let $P(n,k)$ denote the set of all weak compositions of $n$ with $k$ parts, i.e., $P(n,k)=\{ (x_1,x_2,\dots, x_k)\in\mathbb N_0^k : x_1+x_2+\cdots+x_k=n\}$. For any element $\mathbf u=(u_1,u_2,\dots, u_k)\in P(n,k)$, denote its $i$th-coordinate by $\mathbf u(i)$, i.e., $\mathbf u(i)=u_i$. A subset $S\subseteq P(n,k)$ is a matching if $\vert \{ i : \mathbf u(i)=\mathbf v(i)\} \vert=0$ (i.e., $\{ i :\mathbf u(i)=\mathbf v(i)\}=\varnothing$) for all distinct $\mathbf u,\mathbf v\in S$. The matching number of a family $\mathcal A\subseteq P(n,k)$ is denoted by $\nu_w(\mathcal A)$ and is defined to be the maximum size of a matching in $\mathcal A$. In this paper, we determine the maximum size of a family $\mathcal A\subseteq P(n,k)$ subject to the condition $\nu_w(\mathcal A)\leq s$.