Maximal m-distance sets containing the representation of the Hamming graph H(n, m)

DOI10.1016/J.DISC.2016.08.028MaRDI QIDQ729778zbMATH OpenOpenAlexFDO

Authors Saori Adachi, Rina Hayashi, Hiroshi Nozaki, Chika Yamamoto

Publication date 22 December 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.01215

zbMATH Keywords

Erdős-Ko-Rado theoremEuclidean representationfew-distance setHamming graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: A set $X$ in the Euclidean space $mathbb{R}^d$ is called an $m$-distance set if the set of Euclidean distances between two distinct points in $X$ has size $m$. An $m$-distance set $X$ in $mathbb{R}^d$ is said to be maximal if there does not exist a vector $x$ in $mathbb{R}^d$ such that the union of $X$ and $x$ still has only $m$ distances. Bannai--Sato--Shigezumi (2012) investigated the maximal $m$-distance sets which contain the Euclidean representation of the Johnson graph $J(n,m)$. In this paper, we consider the same problem for the Hamming graph $H(n,m)$. The Euclidean representation of $H(n,m)$ is an $m$-distance set in $mathbb{R}^{m(n-1)}$. We prove that the maximum $n$ is $m^2+m-1$ such that the representation of $H(n,m)$ is not maximal as an $m$-distance set. Moreover we classify the largest $m$-distance sets which contain the representation of $H(n,m)$ for $mleq4$ and any $n$. We also classify the maximal $2$-distance sets in $mathbb{R}^{2n-1}$ which contain the representation of $H(n,2)$ for any $n$.

Recommendations

• Maximal m-distance sets containing the representation of the Johnson graph J(n,m)
• Maximal 2-distance sets containing the regular simplex
• Bounds on three- and higher-distance sets
• Constructions of maximum few-distance sets in Euclidean spaces
• On the large maximal \(\{ 0,1,2,\dots,t\}\)-cliques in Hamming graph \(H(n,q)\)

Cites work

• A proof of Erdős-Fishburn's conjecture for \(g(6)=13\)
• An Intersection Theorem for a Collection of Families of Subsets of a Finite Set
• An upper bound for the cardinality of an s-distance subset in real Euclidean space. II
• Classification of three-distance sets in two dimensional Euclidean space
• scientific article; zbMATH DE number 3234139 (Why is no real title available?)
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Maximal m-distance sets containing the representation of the Johnson graph J(n,m)
• Maximum planar sets that determine k distances
• New maximal two-distance sets
• On the largest subsets avoiding the diameter of (0, 1)-vectors
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complete intersection theorem for systems of finite sets
• The exact bound in the Erdős-Ko-Rado theorem
• The maximum sum and the maximum product of sizes of cross-intersecting families
• Uniqueness of maximum planar five-distance sets

Cited in

(2)

• Maximal 2-distance sets containing the regular simplex
• Maximal m-distance sets containing the representation of the Johnson graph J(n,m)

This page was built for publication: Maximal \(m\)-distance sets containing the representation of the Hamming graph \(H(n, m)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q729778)