Intersecting systems of signed sets

Peter Borg

The electronic journal of combinatorics, Tome 14 (2007)

Résumé

A family ${\cal F}$ of sets is said to be (strictly) EKR if no non-trivial intersecting sub-family of ${\cal F}$ is (as large as) larger than some trivial intersecting sub-family of ${\cal F}$. For a finite set $X := \{x_1, ..., x_{|X|}\}$ and an integer $k \geq 2$, we define ${\cal S}_{X,k}$ to be the family of signed sets given by $${\cal S}_{X,k} := \Big\{\big\{(x_1,a_1), ..., (x_{|X|},a_{|X|})\big\} \colon a_i \in [k], i = 1, ..., |X|\Big\}.$$ For a family ${\cal F}$, we define ${\cal S}_{{\cal F},k} := \bigcup_{F \in {\cal F}}{\cal S}_{F,k}$. We conjecture that for any ${\cal F}$ and $k \geq 2$, ${\cal S}_{{\cal F},k}$ is EKR, and strictly so unless $k=2$ and ${\cal F}$ has a particular property. A well-known result (stated by Meyer and proved in different ways by Deza and Frankl, Engel, Erdős et al., and Bollobás and Leader) supports this conjecture for ${\cal F} = {[n] \choose r}$. The main theorem in this paper generalises this result by establishing the truth of the conjecture for families ${\cal F}$ that are compressed with respect to some $f^* \in \bigcup_{F \in {\cal F}}F$ (i.e. $f \in F \in {\cal F}, f^* \notin F \Rightarrow (F \backslash \{f\}) \cup \{f^*\} \in {\cal F}$). We also confirm the conjecture for families ${\cal F}$ that are uniform and EKR.

Détail

DOI : 10.37236/959

Classification : 05D05