## Keywords (2)

Publications
Cross-intersecting families and primitivity of symmetric systems

# Cross-intersecting families and primitivity of symmetric systems,10.1016/j.jcta.2010.09.005,Journal of Combinatorial Theory,Jun Wang,Huajun Zhang

Cross-intersecting families and primitivity of symmetric systems
Let $X$ be a finite set and $\mathfrak p\subseteq 2^X$, the power set of $X$, satisfying three conditions: (a) $\mathfrak p$ is an ideal in $2^X$, that is, if $A\in \mathfrak p$ and $B\subset A$, then $B\in \mathfrak p$; (b) For $A\in 2^X$ with $|A|\geq 2$, $A\in \mathfrak p$ if $\{x,y\}\in \mathfrak p$ for any $x,y\in A$ with $x\neq y$; (c) $\{x\}\in \mathfrak p$ for every $x\in X$. The pair $(X,\mathfrak p)$ is called a symmetric system if there is a group $\Gamma$ transitively acting on $X$ and preserving the ideal $\mathfrak p$. A family $\{A_1,A_2,\ldots,A_m\}\subseteq 2^X$ is said to be a cross-$\mathfrak{p}$-family of $X$ if $\{a, b\}\in \mathfrak{p}$ for any $a\in A_i$ and $b\in A_j$ with $i\neq j$. We prove that if $(X,\mathfrak p)$ is a symmetric system and $\{A_1,A_2,\ldots,A_m\}\subseteq 2^X$ is a cross-$\mathfrak{p}$-family of $X$, then $\sum_{i=1}^m|{A}_i|\leq\left\{ \begin{array}{cl} |X| & \hbox{if m\leq \frac{|X|}{\alpha(X,\, \mathfrak p)},} \\ m\, \alpha(X,\, \mathfrak p) & \hbox{if m\geq \frac{|X|}{\alpha{(X,\, \mathfrak p)}},} \end{array}\right.$ where $\alpha(X,\, \mathfrak p)=\max\{|A|:A\in\mathfrak p\}$. This generalizes Hilton's theorem on cross-intersecting families of finite sets, and provides analogs for cross-$t$-intersecting families of finite sets, finite vector spaces and permutations, etc. Moreover, the primitivity of symmetric systems is introduced to characterize the optimal families.
Journal: Journal of Combinatorial Theory - JCT , vol. 118, no. 2, pp. 455-462, 2011
View Publication
 The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
 ( www.sciencedirect.com ) ( www.informatik.uni-trier.de ) ( dx.doi.org )
More »

## Citation Context (1)

• ...Lemma 2.6 ([18]) Let n and r be two positive integers with r ≤ n .T henSr,n is IS-primitive except for n = r =3 ...

Sort by:

## Citations (3)

### Nontrivial independent sets of bipartite graphs and cross-intersecting families

Published in 2011.

### Independent Sets in Direct Products of Vertex-transitive Graphs

Published in 2010.