Maximal sets of given diameter in the grid and the torus (Q1313846): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Created claim: Wikidata QID (P12): Q127673949, #quickstatements; #temporary_batch_1722463431396 |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(93)90284-z / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2072500693 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q127673949 / rank | |||
Normal rank |
Latest revision as of 00:05, 1 August 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximal sets of given diameter in the grid and the torus |
scientific article |
Statements
Maximal sets of given diameter in the grid and the torus (English)
0 references
10 March 1994
0 references
Let \([k]= \{0,1,\dots,k-1\}\). The grid graph \(G\) has vertices \(x= (x_ 1,\dots,x_ n)\), \(x_ i\in [k]\), with \(x\) joined to \(y\) precisely when there exists \(j\) such that \(| x_ j- y_ j|= 1\) and \(x_ i= y_ i\) for all \(i\neq j\). (Thus \(G\) is the product of \(n\) paths of order \(k\).) If \(A\subseteq [k]^ n\), define the diameter of \(A\) by \(\text{diam }A= \max\{d(x,y)\) : \(x,y\in A\}\), where \(d(x,y)\) is the graph distance. The problem of determining, for given \(k\), \(n\), \(d\), the maximal size of a subset of \([k]^ n\) of diameter \(d\) was discussed by \textit{D. J. Kleitman} and \textit{M. Fellows} [Discrete Math. 73, No. 1/2, 119-125 (1989; Zbl 0675.05001)]. The authors prove their conjecture that there is some \(c= (c_ 1,\dots,c_ n)\), \(c_ i\) not necessarily integers, such that the ball \(B\bigl(c, {1\over 2} d\bigr)\) has maximal size among sets of diameter \(d\). The authors also consider analogous problems for the discrete torus \((\mathbb{Z}/k\mathbb{Z})^ n\), obtaining the maximal size of a subset of diameter \(d\) in the case when \(k\) is even. They make use of some isoperimetric inequalities.
0 references
grid graph
0 references
diameter
0 references
distance
0 references
discrete torus
0 references
isoperimetric inequalities
0 references