An Erdős-Ko-Rado theorem for signed sets (Q1388967): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / cites work | |||
Property / cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A simple proof of the Erdős-Chao Ko-Rado theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Radius and diameter in Manhattan lattices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Maximal sets of given diameter in the grid and the torus / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3741626 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0898-1221(97)00215-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2003292888 / rank | |||
Normal rank |
Latest revision as of 09:50, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An Erdős-Ko-Rado theorem for signed sets |
scientific article |
Statements
An Erdős-Ko-Rado theorem for signed sets (English)
0 references
17 November 1998
0 references
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.
0 references
Erdős-Ko-Rado theorem
0 references
intersecting families
0 references