Upper bounds for the size of set systems with a symmetric set of Hamming distances (Q6061162)
From MaRDI portal
scientific article; zbMATH DE number 7773817
Language | Label | Description | Also known as |
---|---|---|---|
English | Upper bounds for the size of set systems with a symmetric set of Hamming distances |
scientific article; zbMATH DE number 7773817 |
Statements
Upper bounds for the size of set systems with a symmetric set of Hamming distances (English)
0 references
5 December 2023
0 references
For a positive integer \(q\), a \textit{vector system\/} \({\mathcal{H}}\) is a subset of \(\{0,1,\dots,q-1\}^n\); the \textit{Hamming distance\/} \(d_H(\mathbf{h}_1,\mathbf{h}_2)\) of \(\mathbf{h}_1,\mathbf{h}_2\in{\mathcal{H}}\) is \(\left\vert \{i\in[n]:(\mathbf{h}_1)_i\ne(\mathbf{h}_2)_i\}\right\vert \). For distinct elements \(F,G\) of a fixed family of subsets \({\mathcal{F}}\subseteq2^{[n]}\), their \textit{Hamming distance\/} \(d_H(F,G)\) is \(\vert F\triangle G\vert \); \(D({\mathcal{F})}\) is the set \(\{d_H(F,G):F,G\in{\mathcal{F}},F\ne G\}\). \({\mathcal{F}}\) is \textit{Hamming symmetric\/}, if \(d\in D({\mathcal{F}})\) always implies \(n-d\in D({\mathcal{F}})\). The author proves \textbf{Theorem 1.3:} \textit{Let \({\mathcal{F}}\) be a Hamming symmetric family of subsets of \([n]\); let \(s:=\vert D({\mathcal{F}})\vert \). If \(\frac n2\notin D({\mathcal{F}})\), then \(\vert {\mathcal{F}}\vert \le\sum\limits_{j=0}^{\left\lfloor\frac s2\right\rfloor}\binom {n}{2j}\). If \(\frac n2\in D({\mathcal{F}})\), then \(\vert {\mathcal{F}}\vert \le\sum\limits_{j=0}^{\left\lfloor\frac{s-1}2\right\rfloor}\binom {n}{2j+1}\).\/} A generalization is proposed in Conjecture 1.
0 references
extremal set theory
0 references
linear algebra bound method
0 references
rank of graphs
0 references
extremal graphs
0 references
maximum spectral radius
0 references
minimum spectral radius
0 references