An Erdős-Ko-Rado theorem for signed sets
type: Item
instance of: scholarly article
title: An Erdős-Ko-Rado theorem for signed sets
zbMATH Open document ID: 0901.05088
DOI: 10.1016/S0898-1221(97)00215-0
publication date: 1998-11-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 1164074
zbMATH Keywords: Erdős-Ko-Rado theorem
zbMATH Keywords: intersecting families
author: Béla Bollobás
author: Imre Leader
reviewed by: Sergej L. Bezrukov
MaRDI profile type: Publication
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: A simple proof of the Erdős-Chao Ko-Rado theorem
cites work: Radius and diameter in Manhattan lattices
cites work: Maximal sets of given diameter in the grid and the torus
cites work: Q3741626
full work available at URL: s0898-1221(97)00215-0
OpenAlex ID: W2003292888
published in: Computers & Mathematics with Applications
Recommended article: An Erdős-Ko-Rado theorem for restricted signed sets
Recommended article: Erdős-Ko-Rado theorems of labeled sets
Recommended article: An Erdős-Ko-Rado theorem for multisets
Recommended article: Q3679189
Recommended article: An analogue of the Erdős-Ko-Rado theorem for multisets
Recommended article: A generalization of the Erd\H{o}s-Ko-Rado Theorem
Recommended article: A generalization of the Erdős-Ko-Rado theorem
Recommended article: Erdős-Ko-Rado theorems in certain semilattices
Recommended article: Q3754007
description: scientific article; zbMATH DE number 1164074