Source author record

Cheng Yeaw Ku

Cheng Yeaw Ku appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

9works
1topics
3close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2014arXiv

An Erd{\H o}s-Ko-Rado theorem for permutations with fixed number of cycles

Let $S_{n}$ denote the set of permutations of $[n]=\{1,2,\dots, n\}$. For a positive integer $k$, define $S_{n,k}$ to be the set of all permutations of $[n]$ with exactly $k$ disjoint cycles, i.e., \[ S_{n,k} = \{π\in S_{n}: π= c_{1}c_{2} \cdots c_{k}\},\] where $c_1,c_2,\dots ,c_k$ are disjoint cycles. The size of $S_{n,k}$ is given by $\left [ \begin{matrix}n\\ k \end{matrix}\right]=(-1)^{n-k}s(n,k)$, where $s(n,k)$ is the Stirling number of the first kind. A family $\mathcal{A} \subseteq S_{n,k}$ is said to be $t$-{\em intersecting} if any two elements of $\mathcal{A}$ have at least $t$ common cycles. In this paper, we show that, given any positive integers $k,t$ with $k\geq t+1$, there exists an integer $n_0=n_0(k,t)$, such that for all $n\geq n_0$, if $\mathcal{A} \subseteq S_{n,k}$ is $t$-intersecting, then \[ |\mathcal{A}| \le \left [ \begin{matrix}n-t\\ k-t \end{matrix}\right],\] with equality if and only if $\mathcal{A}$ is the stabiliser of $t$ fixed points.

preprint2014arXiv

Cayley Graph on Symmetric Group Generated by Elements Fixing $k$ Points

Let $\mathcal{S}_{n}$ be the symmetric group on $[n]=\{1, \ldots, n\}$. The $k$-point fixing graph $\mathcal{F}(n,k)$ is defined to be the graph with vertex set $\mathcal{S}_{n}$ and two vertices $g$, $h$ of $\mathcal{F}(n,k)$ are joined if and only if $gh^{-1}$ fixes exactly $k$ points. In this paper, we derive a recurrence formula for the eigenvalues of $\mathcal{F}(n,k)$. Then we apply our result to determine the sign of the eigenvalues of $\mathcal{F}(n,1)$.

preprint2013arXiv

A generalization of the extremal function of the Davenport-Schinzel sequences

Let $[n]=\{1, \ldots, n\}$. A sequence $u=a_1a_2\dots a_l$ over $[n]$ is called $k$-sparse if $a_i = a_j$, $i > j$ implies $i-j\geq k$. In other words, every consecutive subsequence of $u$ of length at most $k$ does not have letters in common. Let $u,v$ be two sequences. We say that $u$ is $v$-free, if $u$ does not contain a subsequence isomorphic to $v$. Suppose there are only $k$ letters appearing in $v$. The extremal function Ex$(v,n)$ is defined as the maximum length of all the $v$-free and $k$-sparse sequences. In this paper, we study a generalization of the extremal function Ex$(v,n)$.

preprint2013arXiv

An Analogue of the Hilton-Milner Theorem for weak compositions

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)\in\mathbb N_0^l\ :\ x_1+x_2+\cdots+x_l=n\}$. For any element $\mathbf u=(u_1,u_2,\dots, u_l)\in P(n,l)$, denote its $i$th-coordinate by $\mathbf u(i)$, i.e., $\mathbf u(i)=u_i$. A family $\mathcal A\subseteq P(n,l)$ is said to be $t$-intersecting if $\vert \{ i \ :\ \mathbf u(i)=\mathbf v(i)\} \vert\geq t$ for all $\mathbf u,\mathbf v\in \mathcal A$. A family $\mathcal A\subseteq P(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\in \mathbb N_0$ ($s\in T$) such that $\mathcal{A}= \{\mathbf u\in P(n,l)\ :\ \mathbf u(j)=y_j\ {\rm for all}\ j\in T\}$. We prove that given any positive integers $l,t$ with $l\geq 2t+3$, there exists a constant $n_0(l,t)$ depending only on $l$ and $t$, such that for all $n\geq n_0(l,t)$, if $\mathcal{A} \subseteq P(n,l)$ is non-trivially $t$-intersecting then \begin{equation} \vert \mathcal{A} \vert\leq {n+l-t-1 \choose l-t-1}-{n-1 \choose l-t-1}+t.\notag \end{equation} Moreover, equality holds if and only if there is a $t$-set $T$ of $\{1,2,\dots,l\}$ such that \begin{equation} \mathcal A=\bigcup_{s\in \{1,2,\dots, l\}\setminus T} \mathcal A_s\cup \left\{ \mathbf q_i\ :\ i\in T \right\},\notag \end{equation} where \begin{align} \mathcal{A}_s & =\{\mathbf u\in P(n,l)\ :\ \mathbf u(j)=0\ {\rm for all}\ j\in T\ {\rm and}\ \mathbf u(s)=0\}\notag \end{align} and $\mathbf q_i\in P(n,l)$ with $\mathbf q_i(j)=0$ for all $j\in \{1,2,\dots, l\}\setminus \{i\}$ and $\mathbf q_i(i)=n$.

preprint2013arXiv

On $r$-cross $t$-intersecting families for weak compositions

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)\in\mathbb N_0^l\ :\ x_1+x_2+\cdots+x_l=n\}$. For any element $\mathbf u=(u_1,u_2,\dots, u_l)\in P(n,l)$, denote its $i$th-coordinate by $\mathbf u(i)$, i.e., $\mathbf u(i)=u_i$. Let $l=\min(l_1,l_2,\dots, l_r)$. Families $\mathcal A_j\subseteq P(n_j,l_j)$ ($j=1,2,\dots, r$) are said to be $r$-cross $t$-intersecting if $\vert \{ i\in [l] \ :\ \mathbf u_1(i)=\mathbf u_2(i)=\cdots=\mathbf u_r(i)\} \vert\geq t$ for all $\mathbf u_j\in \mathcal A_j$. Suppose that $l\geq t+2$. We prove that there exists a constant $n_0=n_0(l_1,l_2,\dots,l_r,t)$ depending only on $l_j$'s and $t$, such that for all $n_j\geq n_0$, if the families $\mathcal A_j\subseteq P(n_j,l_j)$ ($j=1,2,\dots, r$) are $r$-cross $t$-intersecting, then \begin{equation} \prod_{j=1}^r \vert \mathcal{A}_j \vert\leq \prod_{j=1}^r {n_j+l_j-t-1 \choose l_j-t-1}.\notag \end{equation} Moreover, equality holds if and only if there is a $t$-set $T$ of $\{1,2,\dots,l\}$ such that $\mathcal{A}_j=\{\mathbf u\in P(n_j,l_j)\ :\ \mathbf u(i)=0\ {\rm for\ all}\ i\in T\}$ for $j=1,2,\dots, r$.

preprint2012arXiv

Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph

We give a new recurrence formula for the eigenvalues of the derangement graph. Consequently, we provide a simpler proof of the Alternating Sign Property of the derangement graph. Moreover, we prove that the absolute value of the eigenvalue decreases whenever the corresponding partition decreases in the dominance order. In particular, this settles affirmatively a conjecture of Ku and Wales (J. of Combin. Theory, Series A 117 (2010) 289--312) regarding the lower and upper bound for the absolute values of these eigenvalues.

preprint2011arXiv

An Analogue of Hilton-Milner Theorem for Set Partitions

Let $\mathcal{B}(n)$ denote the collection of all set partitions of $[n]$. Suppose $\mathcal{A} \subseteq \mathcal{B}(n)$ is a non-trivial $t$-intersecting family of set partitions i.e. any two members of $\A$ have at least $t$ blocks in common, but there is no fixed $t$ blocks of size one which belong to all of them. It is proved that for sufficiently large $n$ depending on $t$, \[ |\mathcal{A}| \le B_{n-t}-\tilde{B}_{n-t}-\tilde{B}_{n-t-1}+t \] where $B_{n}$ is the $n$-th Bell number and $\tilde{B}_{n}$ is the number of set partitions of $[n]$ without blocks of size one. Moreover, equality holds if and only if $\mathcal{A}$ is equivalent to \[ \{P \in \mathcal{B}(n): \{1\}, \{2\},..., \{t\}, \{i\} \in P \textnormal{for some} i \not = 1,2,..., t,n \}\cup \{Q(i,n)\ :\ 1\leq i\leq t\} \] where $Q(i,n)=\{\{i,n\}\}\cup\{\{j\}\ :\ j\in [n]\setminus \{i,n\}\}$. This is an analogue of the Hilton-Milner theorem for set partitions.