Search

Let $\mathcal{F}$ be a family of subsets of $[n]$. The diameter of $\mathcal{F}$ is the maximum size of symmetric differences among pairs of its members. Solving a conjecture of Erd\H{o}s, in 1966, Kleitman determined the maximum size of a family with fixed diameter, which states that a family with diameter $s$ has cardinality at most that of a Hamming ball of radius $s/2$. More precisely, suppose that $\mathcal{F} \subseteq 2^{[n]}$ is a family with diameter $s$, if $s=2d$ for an integer $d\ge 1$, then $|\mathcal{F}|\le \sum_{i=0}^d {n \choose i}$; if $s=2d+1$ for an integer $d\ge 1$, then $|\mathcal{F}|\le \sum_{i=0}^d {n \choose i} + {n-1 \choose d}$. This result extends the well-known Katona intersection theorem and the Erd\H{o}s--Ko--Rado theorem, and it is now known as the Kleitman diameter theorem. In 2017, Frankl characterized the extremal families of Kleitman's theorem and presented a stability result. In this paper, we solve a recent problem due to Li and Wu by determining the extremal families of Frankl's theorem, and establishing a further stability result. These theorems can be viewed as the first and second stability results for the Kleitman diameter theorem. Combining our framework with some appropriate structural analysis, it is feasible to further extend our method to establish higher-layer stability results of the Kleitman diameter theorem., Comment: 37pages

The well-known Erd\H{o}s--Ko--Rado theorem states that for $n> 2k$, every intersecting family of $k$-sets of $[n]:=\{1,\ldots ,n\}$ has at most $ {n-1 \choose k-1}$ sets, and the extremal family consists of all $k$-sets containing a fixed element (called a full star). The Hilton--Milner theorem provides a stability result by determining the maximum size of a uniform intersecting family that is not a subfamily of a full star. The further stabilities were studied by Han and Kohayakawa (2017) and Huang and Peng (2024). Two families $\mathcal{F}$ and $\mathcal{G}$ are called cross-intersecting if for every $F\in \mathcal{F}$ and $G\in \mathcal{G}$, the intersection $F\cap G$ is non-empty. Let $k \geq 1, t\ge 0$ and $n \geq 2 k+t$ be integers. Frankl (2016) proved that if $\mathcal{F} \subseteq\binom{[n]}{k+t}$ and $\mathcal{G} \subseteq\binom{[n]}{k}$ are cross-intersecting families, and $\mathcal{F}$ is non-empty and $(t+1)$-intersecting, then $|\mathcal{F}|+|\mathcal{G}| \leq\binom{n}{k}-\binom{n-k-t}{k}+1$. Recently, Wu (2023) sharpened Frankl's result by establishing a stability variant. The aim of this paper is two-fold. Inspired by the above results, we first prove a further stability variant that generalizes both Frankl's result and Wu's result. Secondly, as an interesting application, we illustrate that the aforementioned results on cross-intersecting families could be used to establish the stability results of the Erd\H{o}s--Ko--Rado theorem. More precisely, we present new short proofs of the Hilton--Milner theorem, the Han--Kohayakawa theorem and the Huang--Peng theorem. Our arguments are more straightforward, and it may be of independent interest., Comment: 22 pages

In this paper, we derive a tight upper bound for the size of an intersecting $k$-Sperner family of subspaces of the $n$-dimensional vector space $\mathbb{F}_{q}^{n}$ over finite field $\mathbb{F}_{q}$ which gives a $q$-analogue of the Erd\H{o}s' $k$-Sperner Theorem, and we then establish a general relationship between upper bounds for the sizes of families of subsets of $[n] = \{1, 2, \dots, n\}$ with property $P$ and upper bounds for the sizes of families of subspaces of $\mathbb{F}_{q}^{n}$ with property $P$, where $P$ is either $\mathcal{L}$-intersecting or forbidding certain configuration. Applying this relationship, we derive generalizations of the well known results about the famous Erd\H{o}s matching conjecture and Erd\H{o}s-Chv\'atal simplex conjecture to linear lattices. As a consequence, we disprove a related conjecture on families of subspaces of $\mathbb{F}_{q}^{n}$ by Ihringer [Europ. J. Combin., 94 (2021), 103306].

Sperner theory is one of the most important branches in extremal set theory. It has many applications in the field of operation research, computer science, hypergraph theory and so on. The LYM property has become an important tool for studying Sperner property. In this paper, we provide a general relationship for LYM inequalities between Boolean lattices and linear lattices. As applications, we use this relationship to derive generalizations of some well-known theorems on maximum sizes of families containing no copy of certain poset or certain configuration from Boolean lattices to linear lattices, including generalizations of the well-known Kleitman theorem on families containing no $s$ pairwise disjoint members (a non-uniform variant of the famous Erd\H{o}s matching conjecture) and Johnston-Lu-Milans theorem and Polymath theorem on families containing no $d$-dimensional Boolean algebras., Comment: arXiv admin note: text overlap with arXiv:2403.04289

The classical Erd\H{o}s-Ko-Rado theorem on the size of an intersecting family of $k$-subsets of the set $[n] = \{1, 2, \dots, n\}$ is one of the fundamental intersection theorems for set systems. After the establishment of the EKR theorem, many intersection theorems on set systems have appeared in the literature, such as the well-known Frankl-Wilson theorem, Alon-Babai-Suzuki theorem, and Grolmusz-Sudakov theorem. In 1995, Snevily proposed the conjecture that the upper bound for the size of an $\mathcal{L}$-intersecting family of subsets of $[n]$ is ${{n} \choose {s}}$ under the condition $\max \{l_{i}\} < \min \{k_{j}\}$, where $\mathcal{L} = \{l_{1}, \dots, l_{s}\}$ with $0 \leq l_{1} < \cdots < l_{s}$ and $k_{j}$ are subset sizes in the family. In this paper, we prove that Snevily's conjecture holds for $n \geq {{k^{2}} \choose {l_{1}+1}}s + l_{1}$, where $k$ is the maximum subset size in the family. We then derive an analogous result for $\mathcal{L}$-intersecting families of subspaces of an $n$-dimensional vector space over a finite field $\mathbb{F}_{q}$., Comment: arXiv admin note: text overlap with arXiv:1701.00585 by other authors

Let $\mathcal{F}$ be a family of subsets of $[n]=\{1,\ldots,n\}$ and let $L$ be a set of nonnegative integers. The family $\mathcal{F}$ is \emph{$L$-intersecting} if $|F\cap F'|\in L$ for every two distinct members $F,F'\in\mathcal{F}$; and $\mathcal{F}$ is $k$-uniform if all its members have the same size $k$. A large variety of problems and results in extremal set theory concern on $k$-uniform $L$-intersecting families. Many attentions are paid to finding the maximum size of a family among all $k$-uniform $L$-intersecting families with prescribed $n,k$ and $L$. In this paper, from another point of view, we propose and investigate the problem of estimating the maximum size of a member in a family among all uniform $L$-intersecting families with size $m$, here $n,m$ and $L$ are prescribed. Our results aim to find out more precise relations of $n,m,k$ and $L$., Comment: 18 pages

In this paper, we provide a common generalization to the well-known Erd\H{o}s-Ko-Rado Theorem, Frankl-Wilson Theorem, Alon-Babai-Suzuki Theorem, and Snevily Theorem on set systems with $\mathcal{L}$-intersections. As a consequence, we derive a result which strengthens substantially the well-known theorem on set systems with $k$-wise $\mathcal{L}$-intersections by F$\ddot{u}$redi and Sudakov [J. Combin. Theory, Ser. A (2004) 105: 143-159]. We will also derive similar results on $\mathcal{L}$-intersecting families of subspaces of an $n$-dimensional vector space over a finite field $\mathbb{F}_{q}$, where $q$ is a prime power.

A family of $k$-subsets $A_1, A_2, ..., A_d$ on $[n]=\{1,2,..., n\}$ is called a $(d, c)$-cluster if the union $A_1\cup A_2 \cup ... \cup A_d$ contains at most $ck$ elements with $c