Intersecting systems of signed sets
Summary: A family \({\mathcal F}\) of sets is said to be (strictly) EKR if no nontrivial intersecting subfamily of \({\mathcal F}\) is (as large as) larger than some trivial intersecting subfamily of \({\mathcal F}\). For a finite set \(X := \{x_1,\dots, x_{|X|}\}\) and an integer \(k \geq 2\), we define \({\mathcal S}_{X,k}\) to be the family of signed sets given by \[ {\mathcal S}_{X,k} := \{\{(x_1,a_1),\dots, (x_{|X|},a_{|X|})\}: a_i \in [k],\;i = 1, \dots, |X|\}. \] For a family \({\mathcal F}\), we define \({\mathcal S}_{{\mathcal F},k} := \bigcup_{F \in {\mathcal F}}{\mathcal S}_{F,k}\). We conjecture that for any \({\mathcal F}\) and \(k \geq 2\), \({\mathcal S}_{{\mathcal F},k}\) is EKR, and strictly so unless \(k=2\) and \({\mathcal F}\) has a particular property. A well-known result (stated by \textit{J. C. Meyer} [Lect. Notes Math. 411, 127--139 (1974; Zbl 0302.05112)] and proved in different ways by \textit{M. Deza} and \textit{P. Frankl} [SIAM J. Algebraic Discrete Methods 4, 419--431 (1983; Zbl 0526.05001)], \textit{K. Engel} [Combinatorica 4, 133--140 (1984; Zbl 0557.05008)], \textit{P. L. Erdős} et al. [Comb. Probab. Comput. 1, 323--334 (1992; Zbl 0792.05137)], and \textit{B. Bollobás} and \textit{I. Leader} [Comput. Math. Appl. 34, 9--13 (1997; Zbl 0901.05088)]) supports this conjecture for \({\mathcal F} = \binom{[n]}{r}\). The main theorem in this paper generalises this result by establishing the truth of the conjecture for families \({\mathcal F}\) that are compressed with respect to some \(f^* \in \bigcup_{F \in {\mathcal F}}F\) (i.e. \(f \in F \in {\mathcal F}, f^* \notin F \Rightarrow (F \backslash \{f\}) \cup \{f^*\} \in {\mathcal F}\)). We also confirm the conjecture for families \({\mathcal F}\) that are uniform and EKR.
- Intersection Theorems for Systems of Sets
- Multiple cross-intersecting families of signed sets
- Set systems with positive intersection sizes
- An intersection theorem for systems of sets
- Union-intersecting set systems
- Intersection statements for systems of sets
- Intersection Properties of Systems of Finite Sets
- scientific article; zbMATH DE number 3596845
- Set-systems with signed solutions
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- On t-intersecting families of signed sets and permutations
- The Erdős-Ko-Rado properties of various graphs containing singletons
- The Erdős-Ko-Rado properties of set systems defined by double partitions
- All 2-transitive groups have the EKR-module property
- An Erdős-Ko-Rado theorem for unions of length 2 paths
- Set systems with positive intersection sizes
- An Erdős-Ko-Rado theorem for restricted signed sets
- Erdős-Ko-Rado theorems for simplicial complexes
- A Hilton-Milner-type theorem and an intersection conjecture for signed sets
- Intersecting families, signed sets, and injection
- On Chvàtal's conjecture and a conjecture on families of signed sets
- Large non-trivial \(t\)-intersecting families of signed sets
- An exact result for (0, 1)-vectors
- Strongly intersecting integer partitions
- Multiple cross-intersecting families of signed sets
This page was built for publication: Intersecting systems of signed sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2372885)
