×

Cross-intersecting families and primitivity of symmetric systems. (English) Zbl 1220.05130

Let \(X\) be a finite set and \(\mathfrak{p} \subseteq 2^X\) the power set of \(X\). The pair \((X, \mathfrak{p})\) is called a \(\mathfrak{p}\)-system, or a system for short, if the following three conditions hold.
(i)
If \(A \in \mathfrak{p}\) and \(B \subset A\), then \(B \in \mathfrak{p}\).
(ii)
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 \not= y\).
(iii)
For every \(x \in X\), \(\{x\} \in \mathfrak{p}\).
Given a system \((X, \mathfrak{p})\), we can construct a simple graph, denoted \(G(X, \mathfrak{p})\), whose vertex set is \(X\), and \(\{a,b\}\) is an edge if and only if \(\{a,b\} \not \in \mathfrak{p}\). We call \((X, \mathfrak{p})\) connected (disconnected) if the graph \(G(X, \mathfrak{p})\) is connected (disconnected).
An element of \(\mathfrak{p}\) is also called a \(\mathfrak{p}\)-subset of \(X\). A family \(\{A_1, A_2, \dots ,\) \(A_m\} \subseteq 2^X\) is said to be a cross-\(\mathfrak{p}\)-family over \(X\) if \(\{a,b\} \in \mathfrak{p}\) for any \(a \in A_i\) and \(b \in A_j\) with \(i \not= j\). Let \(\alpha(X, \mathfrak{p})\) denote \(\max \{|A| : A \in \mathfrak{p}\}\). We call a system \((X, \mathfrak{p})\) symmetric if there is a group \(\Gamma\) transitively acting on \(X\) and preserving the property \(\mathfrak{p}\), i.e., for every pair \(a,b \in X\) there is a \(\gamma \in \Gamma\) such that \(b = \gamma(a)\), and \(A \in \mathfrak{p}\) implies \(\delta(a) \in \mathfrak{p}\) for every \(\delta \in \Gamma\).
The main result established in this paper is the following. Let \((X, \mathfrak{p})\) be a connected symmetric system, and let \(\{A_1, A_2, \dots ,\) \(A_m\}\) be a cross-\(\mathfrak{p}\)-family over \(X\) with \(A_1 \not= \emptyset\). Then \[ \sum^m_{i=1}|A_i| \leq \begin{cases} |X| & \text{ if \(m \leq \frac{|X|}{\alpha(X, \mathfrak{p})}\)}; \\ m \alpha (X, \mathfrak{p}) & \text{ if \(m \geq \frac{|X|}{\alpha(X, \mathfrak{p})}\)}. \end{cases} \] Moreover, the primitivity of symmetric systems is introduced to fully characterize when the upper bound is attained. This result 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.

MSC:

05D05 Extremal set theory
05C65 Hypergraphs

References:

[1] Albertson, M. O.; Collins, K. L., Homomorphisms of 3-chromatic graphs, Discrete Math., 54, 127-132 (1985) · Zbl 0572.05024
[2] Aschbacher, M., On the maximal subgroups of the finite classical groups, Invent. Math., 76, 469-514 (1984) · Zbl 0537.20023
[3] Borg, P., Intersecting and cross-intersecting families of labeled sets, Electron. J. Combin., 15, N9 (2008) · Zbl 1160.05339
[4] Borg, P., On \(t\)-intersecting families of signed sets and permutations, Discrete Math., 309, 3310-3317 (2009) · Zbl 1216.05003
[5] Borg, P., Extremal \(t\)-intersecting sub-families of hereditary families, J. Lond. Math. Soc., 79, 167-185 (2009) · Zbl 1180.05118
[6] Borg, P., A short proof of a cross-intersection theorem of Hilton, Discrete Math., 309, 4750-4753 (2009) · Zbl 1187.05074
[7] Borg, P., Cross-intersecting families of permutations, J. Combin. Theory Ser. A, 117, 483-487 (2010) · Zbl 1228.05006
[8] Borg, P.; Leader, I., Multiple cross-intersecting families of signed sets, J. Combin. Theory Ser. A, 117, 583-588 (2010) · Zbl 1216.05163
[9] Cameron, P. J.; Ku, C. Y., Intersecting families of permutations, European J. Combin., 24, 881-890 (2003) · Zbl 1026.05001
[10] Deza, M.; Frankl, P., On the maximum number of permutations with given maximal or minimal distance, J. Combin. Theory Ser. A, 22, 352-360 (1977) · Zbl 0352.05003
[11] Engel, K., Sperner Theory (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0868.05001
[12] Erdős, P.; Ko, C.; Rado, R., Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser., 2, 313-318 (1961) · Zbl 0100.01902
[13] Frankl, P., The Erdős-Ko-Rado theorem is true for \(n = c k t\), Col. Soc. Math. J. Bolyai, 18, 365-375 (1978) · Zbl 0401.05001
[14] Frankl, P.; Wilson, R. M., The Erdős-Ko-Rado theorem for vector spaces, J. Combin. Theory Ser. A, 43, 228-236 (1986) · Zbl 0609.05055
[15] Godsil, C.; Meagher, K., A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations, European J. Combin., 30, 404-414 (2009) · Zbl 1177.05010
[16] Greene, C.; Kleitman, D. J., Proof techniques in the ordered sets, (Rota, G.-C., Studies in Combinatorics (1978), Math. Assn. America: Math. Assn. America Washington, DC), 22-79 · Zbl 0409.05012
[17] Hall, P., On representatives of subsets, J. Lond. Math. Soc., 10, 26-30 (1935) · Zbl 0010.34503
[18] Hilton, A. J.W., An intersection theorem for a collection of families of subsets of a finite set, J. Lond. Math. Soc., 2, 369-384 (1977) · Zbl 0364.05002
[19] Hsieh, W. N., Intersection theorems for systems of finite vector spaces, Discrete Math., 12, 1-16 (1975) · Zbl 0311.05001
[20] Jacobson, N., Basic Algebra. I (1985), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0557.16001
[21] Ku, C. Y.; Leader, I., An Erdős-Ko-Rado theorem for partial permutations, Discrete Math., 306, 74-86 (2006) · Zbl 1088.05072
[22] Ku, C. Y.; Wong, T. W.H., Intersecting families in the alternating group and direct product of symmetric groups, Electron. J. Combin., 14, R25 (2007) · Zbl 1111.05093
[23] Larose, B.; Malvenuto, C., Stable sets of maximal size in Kneser-type graphs, European J. Combin., 25, 657-673 (2004) · Zbl 1048.05078
[24] Li, Y. S.; Wang, J., Erdős-Ko-Rado-type theorems for colored sets, Electron. J. Combin., 14, R1 (2007) · Zbl 1111.05094
[25] Newton, B.; Benesh, B., A classification of certain maximal subgroups of symmetric groups, J. Algebra, 304, 1108-1113 (2006) · Zbl 1108.20001
[26] Wang, J.; Zhang, S. J., An Erdős-Ko-Rado-type theorem in Coxeter groups, European J. Combin., 29, 1112-1115 (2008) · Zbl 1140.20001
[27] Wilson, R. M., The exact bound in the Erdős-Ko-Rado theorem, Combinatorica, 4, 247-257 (1984) · Zbl 0556.05039
[28] H.J. Zhang, Primitivity and independent sets in direct products of vertex-transitive graphs, J. Graph Theory, doi:10.1002/jgt.20526; H.J. Zhang, Primitivity and independent sets in direct products of vertex-transitive graphs, J. Graph Theory, doi:10.1002/jgt.20526 · Zbl 1232.05177
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.