An Erdős-Ko-Rado theorem for signed sets
Let \([n]=\{1,\dots,n\}\). A signed \(r\)-set on \([n]\) is a pair \((A,f)\), where \(A\subseteq [n]\), \(| A| =r\) and \(f:A\to\{-1,1\}\). A family \(\mathcal A\) of signed \(r\)-sets is called intersecting if for any \((A,f),(B,g)\in\mathcal A\) there exists \(x\in A\cap B\) such that \(f(x)=g(x)\). It is shown that \(| {\mathcal A}| \leq 2^{r-1}{n-1\choose r-1}\) for any intersecting family \(\mathcal A\) of signed \(r\)-sets. In the case \(r<n\) all maximum intersecting families are specified. As an application of this result the authors provide another proof to their published result on constructing a maximum-sized set of vertices of a grid \([-k,k]^n\), which has a fixed diameter \(d\). This problem is more difficult if \(d\) is odd. In the case \(d\geq n(k+1)\) it is shown how the result mentioned above can be applied to simplify the original proof.
- An Erdős-Ko-Rado theorem for restricted signed sets
- Erdős-Ko-Rado theorems of labeled sets
- An Erdős-Ko-Rado theorem for multisets
- An Erdős-Ko-Rado theorem for multisets
- scientific article; zbMATH DE number 3900758
- An analogue of the Erdős-Ko-Rado theorem for multisets
- A generalization of the Erdős-Ko-Rado theorem
- A generalization of the Erdős-Ko-Rado theorem
- Erdős-Ko-Rado theorems in certain semilattices
- scientific article; zbMATH DE number 3991507
- A generalization of Talbot's theorem about King Arthur and his knights of the round table
- 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
- Maximal sets of given diameter in the grid and the torus
- Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
- Compression and Erdős-Ko-Rado graphs
- Graphs with the Erdős-Ko-Rado property
- An Erdős-Ko-Rado theorem for unions of length 2 paths
- On intersecting families of independent sets in trees
- An Erdős-Ko-Rado theorem for restricted signed sets
- A positive fraction mutually avoiding sets theorem
- The Katona cycle proof of the Erdős-Ko-Rado theorem and its possibilities
- A Hilton-Milner-type theorem and an intersection conjecture for signed sets
- A generalization of the Erdős-Ko-Rado theorem to t-designs in certain semilattices
- A sharp bound for the product of weights of cross-intersecting families
- Intersecting families, signed sets, and injection
- Erdős-Ko-Rado theorems of labeled sets
- On the Holroyd-Talbot conjecture for sparse graphs
- On Chvàtal's conjecture and a conjecture on families of signed sets
- Very well-covered graphs with the Erdős-Ko-Rado property
- Large non-trivial \(t\)-intersecting families of signed sets
- Stability of large rainbow intersecting families with product measure
- An Erdős-Ko-Rado type theorem for subgraphs of perfect matchings
- On intersecting families of subgraphs of perfect matchings
- Strongly intersecting integer partitions
- An Erdős--Ko--Rado theorem for partial permutations
- Multiple cross-intersecting families of signed sets
This page was built for publication: An Erdős-Ko-Rado theorem for signed sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1388967)
