Intersecting systems of signed sets (Q2372885)

From MaRDI portal
Revision as of 18:10, 2 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
Intersecting systems of signed sets
scientific article

    Statements

    Intersecting systems of signed sets (English)
    0 references
    0 references
    16 July 2007
    0 references
    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.
    0 references

    Identifiers