Source author record

Mengyu Cao

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

8works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

$r$ -cross $t$ -intersecting families for vector spaces

Let $V$ be an $n$ -dimensional vector space over the finite field $\mathbb{F}_q$ , and ${V\brack k}$ denote the family of all $k$ -dimensional subspaces of $V$ . The families $\mathcal{F}_1\subseteq{V\brack k_1},\mathcal{F}_2\subseteq{V\brack k_2},\ldots,\mathcal{F}_r\subseteq{V\brack k_r}$ are said to be $r$ -cross $t$ -intersecting if $\dim(F_1\cap F_2\cap\cdots\cap F_r)\geq t$ for all $F_i\in\mathcal{F}_i,\ 1\leq i\leq r.$ The $r$ -cross $t$ -intersecting families $\mathcal{F}_1$ , $\mathcal{F}_2,\ldots,\mathcal{F}_r$ are said to be non-trivial if $\dim(\cap_{1\leq i\leq r}\cap_{F\in\mathcal{F}_i}F)<t$ . In this paper, we first determine the structure of $r$ -cross $t$ -intersecting families with maximum product of their sizes. As a consequence, we partially prove one of Frankl and Tokushige's conjectures about $r$ -cross $1$ -intersecting families for vector spaces. Then we describe the structure of non-trivial $r$ -cross $t$ -intersecting families $\mathcal{F}_1$ , $\mathcal{F}_2,\ldots,\mathcal{F}_r$ with maximum product of their sizes under the assumptions $r=2$ and $\mathcal{F}_1=\mathcal{F}_2=\cdots=\mathcal{F}_r=\mathcal{F}$ , respectively, where the $\mathcal{F}$ in the latter assumption is well known as $r$ -wise $t$ -intersecting family. Meanwhile, stability results for non-trivial $r$ -wise $t$ -intersecting families are also been proved.

preprint2022arXiv

Edge pancyclic derangement graphs

We consider the derangement graph in which the vertices are permutations of $\{ 1,\ldots, n\}$ . Two vertices are joined by an edge if the corresponding permutations differ in every position. The derangement graph is known to be Hamiltonian and Hamilton-connected. In this note, we show that the derangement graph is edge pancyclic if $n\ge 4$ .

preprint2022arXiv

On the $P_3$ -hull numbers of $q$ -Kneser graphs and Grassmann graphs

Let $S$ be an $n$ -dimensional vector space over the finite field $\mathbb{F}_q$ , where $q$ is necessarily a prime power. Denote $K_q(n,k)$ (resp. $J_q(n,k)$ ) to be the \emph{ $q$ -Kneser graph} (resp. \emph{Grassmann graph}) for $k\geq 1$ whose vertices are the $k$ -dimensional subspaces of $S$ and two vertices $v_1$ and $v_2$ are adjacent if $\dim(v_1\cap v_2)=0$ (resp. $\dim(v_1\cap v_2)=k-1$ ). We consider the infection spreading in the $q$ -Kneser graphs and the Grassmann graphs: a vertex gets infected if it has at least two infected neighbors. In this paper, we compute the $P_3$ -hull numbers of $K_q(n,k)$ and $J_q(n,k)$ respectively, which is the minimum size of a vertex set that eventually infects the whole graph.

preprint2022arXiv

Some intersection theorems for finite sets

Let $n$ , $r$ , $k_1,\ldots,k_r$ and $t$ be positive integers with $r\geq 2$ , and $\mathcal{F}_i\ (1\leq i\leq r)$ a family of $k_i$ -subsets of an $n$ -set $V$ . The families $\mathcal{F}_1,\ \mathcal{F}_2,\ldots,\mathcal{F}_r$ are said to be $r$ -cross $t$ -intersecting if $|F_1\cap F_2\cap\cdots\cap F_r|\geq t$ for all $F_i\in\mathcal{F}_i\ (1\leq i\leq r),$ and said to be non-trivial if $|\cap_{1\leq i\leq r}\cap_{F\in\mathcal{F}_i}F|<t$ . If the $r$ -cross $t$ -intersecting families $\mathcal{F}_1,\ldots,\mathcal{F}_r$ satisfy $\mathcal{F}_1=\cdots=\mathcal{F}_r=\mathcal{F}$ , then $\mathcal{F}$ is well known as $r$ -wise $t$ -intersecting family. In this paper, we describe the structure of non-trivial $r$ -wise $t$ -intersecting families with maximum size, and give a stability result for these families. We also determine the structure of non-trivial $2$ -cross $t$ -intersecting families with maximum product of their sizes.

preprint2022arXiv

Triangles in r-wise t-intersecting families

Let $t$ , $r$ , $k$ and $n$ be positive integers and $\mathcal{F}$ a family of $k$ -subsets of an $n$ -set $V$ . The family $ \CF $ is $r$ -wise $t$ -intersecting if for any $ F_1, \ldots, F_r \in \CF $, we have $ \abs{\cap_{i = 1}^{r}F_i}\gs t $. An $r$ -wise $t$ -intersecting family of $r + 1$ sets $\{T_1, \ldots, T_{r + 1}\}$ is called an $(r + 1,t)$ -triangle if $ |T_1 \cap \cdots \cap T_{r + 1}| \ls t - 1 $. In this paper, we prove that if $ n \gs n_0(r, t, k) $, then the $r$ -wise $t$ -intersecting family $ \CF \subseteq \binom{[n]}{k} $ containing the most $(r + 1,t)$ -triangles is isomorphic to $ \curlybraces{F \in \binom{[n]}{k}: \abs{F \cap [r + t]} \gs r + t - 1} $. This can also be regarded as a generalized Turán type result.

preprint2021arXiv

Treewidth of the $q$ -Kneser graphs

Let $V$ be an $n$ -dimensional vector space over a finite field $\mathbb{F}_q$ , where $q$ is a prime power. Define the \emph{generalized $q$ -Kneser graph} $K_q(n,k,t)$ to be the graph whose vertices are the $k$ -dimensional subspaces of $V$ and two vertices $F_1$ and $F_2$ are adjacent if $\dim(F_1\cap F_2)<t$ . Then $K_q(n,k,1)$ is the well-known $q$ -Kneser graph. In this paper, we determine the treewidth of $K_q(n,k,t)$ for $n\geq 2t(k-t+1)+k+1$ and $t\ge 1$ exactly. Note that $K_q(n,k,k-1)$ is the complement of the Grassmann graph $G_q(n,k)$ . We give a more precise result for the treewidth of $\overline{G_q(n,k)}$ for any possible $n$ , $k$ and $q$ .

preprint2020arXiv

Extremal even-cycle-free subgraphs of the complete transposition graphs

Given graphs $G$ and $H$ , the generalized Turán number ${\rm ex}(G,H)$ is the maximum number of edges in an $H$ -free subgraph of $G$ . In this paper, we obtain an asymptotic upper bound on ${\rm ex}(CT_n,C_{2l})$ for any $n \ge 3$ and $l\geq2$ , where $C_{2l}$ is the cycle of length $2l$ and $CT_n$ is the complete transposition graph which is defined as the Cayley graph on the symmetric group ${\rm S}_n$ with respect to the set of all transpositions of ${\rm S}_n$ .

preprint2020arXiv

Non-trivial $t$ -intersecting families for vector spaces

Let $V$ be an $n$ -dimensional vector space over a finite field $\mathbb{F}_q$ . In this paper we describe the structure of maximal non-trivial $t$ -intersecting families of $k$ -dimensional subspaces of $V$ with large size. We also determine the non-trivial $t$ -intersecting families with maximum size. In the special case when $t=1$ our result gives rise to the well-known Hilton-Milner Theorem for vector spaces.

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.

Mengyu Cao

Research overview

Is this your work?

8 publications

$r$ -cross $t$ -intersecting families for vector spaces

Edge pancyclic derangement graphs

On the $P_3$ -hull numbers of $q$ -Kneser graphs and Grassmann graphs

Some intersection theorems for finite sets

Triangles in r-wise t-intersecting families

Treewidth of the $q$ -Kneser graphs

Extremal even-cycle-free subgraphs of the complete transposition graphs

Non-trivial $t$ -intersecting families for vector spaces

See the researcher in context

Building this map preview

Mengyu Cao

Research overview

Is this your work?

8 publications

rrr-cross ttt-intersecting families for vector spaces

Edge pancyclic derangement graphs

On the P3 P_3 P3​-hull numbers of q q q-Kneser graphs and Grassmann graphs

Some intersection theorems for finite sets

Triangles in r-wise t-intersecting families

Treewidth of the qqq-Kneser graphs

Extremal even-cycle-free subgraphs of the complete transposition graphs

Non-trivial ttt-intersecting families for vector spaces

See the researcher in context

Building this map preview

$r$ -cross $t$ -intersecting families for vector spaces

On the $P_3$ -hull numbers of $q$ -Kneser graphs and Grassmann graphs

Treewidth of the $q$ -Kneser graphs

Non-trivial $t$ -intersecting families for vector spaces