/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 1-13
On the largest subsets avoiding the diameter of
(0, ±1)-vectors
Saori Adachi, Hiroshi Nozaki *
Department of Mathematics Education, Aichi University of Education, 1 Hirosawa, Igaya-cho, Kariya, Aichi 448-8542, Japan
Received 4 September 2015, accepted 28 October 2015, published online 25 July 2016 Abstract
Let Lmkl c Rm+fc+' be the set of vectors which have m of entries -1, k of entries 0, and l of entries 1. In this paper, we investigate the largest subset of Lmkl whose diameter is smaller than that of Lmkl. The largest subsets for m =1, l = 2, and any k will be classified. From this result, we can classify the largest 4-distance sets containing the Euclidean representation of the Johnson scheme J(9,4). This was an open problem in Bannai, Sato, and Shigezumi (2012).
Keywords: The ErdSs-Ko-Rado theorem, s-distance set, diameter graph, independent set, extremal set theory.
Math. Subj. Class.: 05D05, 05C69
1 Introduction
The famous theorem in Erdos element subsets of In = {1, then
For n > 2k, the set {A c In | |A| = k, 1 G A} is the unique family achieving equality, up to permutations on In. For n = 2k, the largest set is any family which contains only one of A or In \ A for any k-element A c In. This result plays a central role in extremal set theory, and similar or analogous theorems are proved for various objects [2, 5, 9].
»Work supported by JSPS KAKENHI Grant Numbers 25800011, 26400003. E-mail addresses: s214m044@auecc.aichi-edu.ac.jp (Saori Adachi), hnozaki@auecc.aichi-edu.ac.jp (Hiroshi Nozaki)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
-Ko-Rado [8] stated that for n > 2k and a family A of k.., n}, if any two distinct A, B G A satisfy A n B = 0,
|A| — (H 1
2
Ars Math. Contemp. 13 (2017) 125-136
We can naturally interpret A c In as x = (x^ ..., xn) G Rn by the manner xj = 1 if i G A, xj =0 if i G A. By this identification, the Erdos-Ko-Rado Theorem can be rewritten that for n > 2k and a subset X of Lk = {x G Rn | xj G {0,1}, ^ xj = k} if any distinct x, y G X satisfy d(x, y) < D(Lk) = %/2k, then
where d(,) is the Euclidean distance, and D(Lk) is the diameter of Lk. We would like to consider the following problem to generalize the Erdos-Ko-Rado Theorem.
Problem 1.1. Let Lmkl C Rm+fc+' be the set of vectors which have m of entries -1, k of entries 0, and l of entries 1. Classify the largest X c Lmkl with D(X) < D(LmkI).
It is almost obvious for the cases m = l (Proposition 2.1) and m + k < l (Proposition 2.2). In this paper, we solve the first non-trivial case m =1, l = 2 and any k (Theorem 2.5). Using the largest sets for the case (m, k, l) = (1,6,2), we can classify the largest 4-distance sets containing the Euclidean representation of the Johnson scheme J(9,4). This was an open problem in [1].
We will give a brief survey on related results. Let Lnm be the set of (0, ±1)-vectors in Rn which have m non-zero coordinates. For a fixed set D of integers, let V(n, m, D) be the family of subsets V = {vi,..., vk } of Lnm such that (vj, vj) G D for any i = j. There are several results relating to the largest sets in V(n, m, D) for some (n, m, D) [4, 6, 7]. Since X c Lnm is on a sphere, if |D| = s holds, then |X| < (n+ss-i) + (d+--2) [3]. The case D = {d} is investigated in [4]. For non-negative integers d < m, t > 2, and n > n0(m) (see [4] about n0(m)), if X G V(n, m, {d, d + 1,..., d + t - 1}), then |X| < (n-d)/(m-d) [6]. This equality can be attained whenever a Steiner system S(n - d, m - d, t) (equivalently t-(n - d, m - d, 1) design) exists . We also have if
X G V(n, m, {-(t - 1),-(t - 2),..., t - 1}),then |X| < 2t-i(m - t + !)(?)/([7].
When m = t +1, this equality can be attained whenever a Steiner system S(n, m, m - 1)
2 Largest subsets avoiding the diameter of Lmkl
Let Lmkl denote the finite set in Rn = Rm+fc+', which consists of all vectors whose number of entries -1, 0,1 is equal to m, k, l, respectively. For two subsets X, Y of Lmkl, X is isomorphic to Y if there exists a permutation a G Sn such that X = {(yCT(i),..., yCT(n}) | (yi,..., yn) G Y}. The diameter D(X) of X c Rn is defined to be
where d(,) is the Euclidean distance. Let Mmkl denote the largest possible number of cardinalities of X c Lmkl such that D(X) < D(LmkI). The diameter graph of X c Rn is defined to be the graph (X, E), where E = {(x, y) | d(x, y) = D(X)}. The problem of determining Mmkl is equivalent to determining the independence number of the diameter graph of Lmfci. Note that Mmfci = Mifcm because we have Lmfci = -Lifcm = {-x | x G ¿ifcm}. Thus we may assume m < l. In this section, we determine Mmkl, and classify the largest sets for several cases of m, k, l.
First we determine Mmkl for the cases m = l and m + k < l.
exists.
D(X) = max{d(x, y) | x, y G X},
S. Adachi and H. Nozaki: On the largest subsets avoiding the diameter of (0, ±1)-vectors 3
Proposition 2.1. Assume m = I. Then we have
1f n\ik + m\ 1 Mmkl = -	= - |Lmkl|,
2 \mj \ m J 2
and the largest sets contain only one of x or —x for any x G Lmkl.
Proof. For any x G Lmkl, we have {y | d(x,y) = D(Lmkl)} = {—x}. Therefore the diameter graph of Lmkl is the set of independent edges. The proposition can be easily proved from this fact.	□
For X c Lmkl, we use the notation
Ni(X,j) = {(xi,...,xn) G X | xi = j}, and nm(X,j) = |Ni(X,j)|. Proposition 2.2. Assume m + k < I. Then we have
n — 1 \ f m + k^
Mmkl , , , 1 . .
vm + k — 1/ y m
For m + k > l, the largest set is Nl(Lmkl, —1) U Nl(Lmkl, 0), up to isomorphism. For m + k = l, then the largest sets contain only one of {(xi,..., xn) G Lmkl | x^ = 1, V« G J} or {(xi,..., xn) G Lmkl | xj = 1, V« G In \ J} for any J C In of order l.
Proof. A finite subset X of Lmkl satisfies D(X) < D(Lmkl) if and only if {i | xj = — 1,0} U {i | yi = —1,0} is not empty for any distinct (xi,..., xn), (yi,..., yn) G X. We can therefore apply the Erdos-Ko-Rado Theorem [8] to determine the positions of entries —1 or 0. The number of possible positions of —1, 0 is (mi+—- J. After fixing the position, —1, 0 can be placed in (m++k) ways. This determines Mmkl. The largest sets are classified from the optimal sets of the Erdos-Ko-Rado Theorem.	□
The remaining part of this section is devoted to proving
Mi k2 = Mk = (k + 3)+2,
and determining the classification of the largest sets. Note that D(Lik2) = %/10 and if X C Lik2 satisfies D(X) < D(Lik2), then D(X) < a/8. The following two lemmas are used later.
Lemma 2.3. Let X C Lik2 with D(X) < D(Lik2). Suppose k > 4, and ^| > Mk. Then there exists i G {1,... ,n} such that ni (X, 0) > Mk-i.
Proof. This lemma is immediate because the average of ni(X, 0) is
n t ni (X, 0) = kX > FM3 = Mk- i — > Mk- i — 1. □
n^	k + 3 k + 3	k + 3
i= i
Lemma 2.4. Let G = (V, E) be a connected simple graph, and E' a matching in G. Assume that G has an independent set I of size |V| — |E'|. Then for z G I if x G V satisfies (x, y) G E' for some y adjacent to z, then x G I.
4
Ars Math. Contemp. 13 (2017) 125-136
Proof. Since the cardinality of I is | V| — |E'|, only one of x or y is an element of I for any
(x, y) G E'. By assumption, y G I, and hence x G I.	□
The subsets Sk(i), Tk(i), Uk(i) of Lik2 are defined by
Sk(i) = {(xi, ...,x„) G Lifc2 | xi = • • • = xi-i = 0,xi = —1}, Tk(i) = {(xi, ...,x„) G Lifc2 | xi = • • • = xj-i = 0,xi = 1},
Uk(i)^(xi,---,xn)gLik21 x;={2,xi.=i—,jG={/+i,...,n}}
for i = 2, ...,k + 2. We define Sfc (1) = Ni(Lik2, — 1), and Tfc (1) = Ni(Lik2,1). The following are candidates of the largest subsets avoiding the largest distance %/10.
k+i
Xfc = Tk(k +1) u ( U Sk(i)) for k > 1,
i=i
k-i
Yi = Ti(1), Yk = Tk(k) U ( U Sk(i)) for k > 2,
i=i
k-2
Z2 = T2(1), Zk = Tk(k — 1) U ( U Sk(i)) for k > 3.
i=i
Note that |Xk | = | Yk | = |Zk | = Mk, and they can be inductively constructed by
Xk = {(0,x) | x G Xk-i} U Ni(Lik2, —1), Yk = {(0,x) | x G Yk-i}U Ni(Lik2, —1), Zk = {(0,x) | x G Zk-i} U Ni(Lik2, —1).
We also use the following notation.
Xk = Xk \ Sk(1) = {(0, x) | x G Xk-i} (k > 2), Yk' = Yk \ Sk(1) = {(0, x) | x G Yk-i} (k > 2), Zk = Zk \ Sk(1) = {(0, x) | x G Zk-i} (k > 3).
Theorem 2.5. Let X c Lik2 with D(X) < D(Lik2). Then we have
|X| < Mk.
If equality holds, then
(1)	for k = 1, X = Xi, or Yi,
(2)	for k > 2, X = Xk, Yk, or Zk,
up to isomorphism.
This theorem will be proved by induction. We first prove the inductive step.
Lemma 2.6. Let k > 2. Assume that the statement in Theorem 2.5 holds for some k — 1. Let X c Lik2 with D(X) < D(Lik2), such that nj(X, 0) = Mk-i for some i. Then we have |X | < Mk. If equality holds, then X = Xk, Yk, or Zk, up to isomorphism.
S. Adachi and H. Nozaki: On the largest subsets avoiding the diameter of (0, ±1)-vectors 5
Proof. Without loss of generality, n(X, 0) = Mk-i, and hence X contains X'k, Yk', or Z' for k > 3, and X1, or Y' for k = 2.
(i) Suppose X' C X for k > 2. The set of other candidates of elements of X is Sk (1) U Uk (k). The diameter graph G of Sk (1) U Uk (k) is a bipartite graph of the partite sets Sk(1) and Uk(k). Since the three elements
(-1,0,..., 0, 0,1,1), (-1,0,..., 0,1,0,1), (-1, 0,..., 0,1,1,0) € Sk (1)
are isolated vertices in G, they may be contained in X. Let G' be the subgraph of G formed by removing the three isolated vertices. A perfect matching of G' is given as follows.
Matching (i)
Sk (1) (-1,x2,...,xk+3)	Uk(k) (1,y2,...,yk+3)
xi = 1, xj = 1 (2 < i < k, i < j < n) xi = 1, xn = 1 (2 < i < k)	yi = -1,yj+i = 1 y = -1,yi+i = 1
By this matching, we can show
|X| < Mk_ i + |Sk(1)| = Mk.
We will classify the sets attaining this bound. First assume that x € X for some x € Sk(1) with x2 = 1. By Lemma 2.4, X must contain any x € Sk(1) with x2 = 1. In particular, (-1,1,1,0,..., 0) € X. Using Lemma 2.4 again, X must contain x € Sk(1) with x3 = 1. By a similar manner, X must contain any x € Sk(1). Therefore X = Xk.
Assume X does not contain any x € Sk (1) with x2 = 1, namely n2(X, 1) = 0. By assumption, we have
|X| = n2(X,-1) + n2(X,0) < ^ + ^ + Mk_i = Mk.
If |X| = Mk, then we have n2(X, -1) = (k+2) and n2(X, 0) = Mk_ 1. This implies that X is isomorphic to Xk, Yk, or Zk.
(ii) Suppose Yk' C X for k > 2. The set of other candidates of elements of X is the union of Sk (1) , Uk ( k - 1) , and
Si = {(xi,... ,xk+3) € Lik2 | xi = 1,xk = 1,xj = -1, k < j}
for k > 3, and S2(1) U Si for k = 2. The diameter graph G of Sk (1) U Uk (k - 1) U Si is a bipartite graph of the partite sets Sk(1) and Uk (k - 1) U Si. Since the three elements
(-1, 0,..., 0,1,1,0,0), (-1,0,..., 0,1, 0,1,0), (-1,0,..., 0,1, 0, 0,1) € Sk (1)
are isolated vertices in G, they may be contained in X. Let G' be the subgraph of G formed by removing the three isolated vertices. A perfect matching of G' is given as follows.
Matching (ii)
Sk (1) (-1,x2,...,xk+3)	Uk(k - 1) (1,y2,... ,yk+3)
xi = 1, xj = 1 (2 < i < k - 1, i < j < n) xi = 1, xn = 1 (2 < i < k - 1)	yi = -1,yj+i = 1 yi = -1,yi+i = 1
6
Ars Math. Contemp. 13 (2017) 125-136
Sk(1)	Si
(-1,0,..., 0,1,1, 0) (-1,0,..., 0,0,1,1) (-1,0,..., 0,1,0,1)	(1, 0,..., 0,1,-1, 0, 0) (1,0,..., 0,1,0,-1,0) (1,0,..., 0,1,0,0,-1)
By this maching, we can show |X | < Mk.
We will classify the sets attaining this bound. For k = 2, the maximum indepdent sets of G' is {(-1,0,0,1,1), (-1,0,1,0,1), (-1,0,1,1,0)} C S2(1) or Si. This implies that X = Y2 or Z2. For k > 3, we assume that x G X for some x G Sk(1) with x2 = 1. By Lemma 2.4, X must contain any x G Sk (1). Therefore X = Yk. If X does not contain any x G Sk (1) with x2 = 1, namely n2(X, 1) = 0. It can be proved that X is isomorphic to Xk, Yk, or Zk.
(iii) Suppose k > 3, and Zk C X. The set of other candidates of elements of X is the union of Sk(1), Uk(k - 2), and
S2 = {(xi,... ,xk+3) G Lik2 | xi = 1,xk-i = 1,xj = -1, k < j}
for k > 4, and S3(1) U S2 for k = 3. The diameter graph G of Sk(1) U Uk(k - 2) U S2 is a bipartite graph of the partite sets Sk(1) and Uk(k - 2) U S2. Since the four vectors
(-1,0,..., 0,1,1, 0, 0,0), (-1,0,..., 0,1,0,1, 0,0), (-1,0,..., 0,1,0, 0,1,0), (-1,0,..., 0,1,0, 0, 0,1) G Sk (1)
are isolated vertices in G, they may be contained in X. Let G' be the subgraph of G formed by removing the four isolated vertices. A maximum matching of G' is given as follows.
Matching (iii)
Sk (1) (-1,x2,...,xk+3)	Uk (k - 2) ... ,yk+3)
x, = 1, xj = 1 (2 < i < k - 2, i < j < n) x, = 1,xn = 1 (2 < i < k - 2)	y = -1,yj+i = 1 y = -1,yi+i = 1
Sk (1)	S2
(-1, 0,..., 0,1,1,0, 0) (-1,0,..., 0,0,1,1,0) (-1,0,..., 0,0,0,1,1) (-1,0,..., 0,1,0,0,1)	(1, 0,..., 0,1,-1, 0, 0, 0) (1,0,..., 0,1,0,-1,0,0) (1,0,..., 0,1,0,0,-1,0) (1,0,..., 0,1,0,0,0, -1)
Note that the two vectors
(-1,0,..., 0,1, 0,1,0), (-1,0,..., 0,0,1, 0,1) G Sk(1)	(2.1)
are unmatched in this matching. By this matching, we can show |X | < Mk.
We will classify the sets attaining this bound. If |X | = Mk, then the two vectors in (2.1) must be contained in X. Therefore X does not contain any element of S2, and contains an element of Sk (1) which matches some element of S2. For k = 3, X therefore contains Sk (1), and X = Z3. For k > 4, we assume that x G X for some x G Sk(1) with x2 = 1. By Lemma 2.4, X must contain any x G Sk(1). Therefore X = Zk. If X does not contain any x G Sk(1) with x2 = 1, namely n2(X, 1) = 0. Therefore X is isomorphic to Xk, Yk, or Zk.	□
S. Adachi and H. Nozaki: On the largest subsets avoiding the diameter of (0, ±1)-vectors 7
Matchings (i)-(iii) and the notation Si, S2 defined in the proof of Lemma 2.6 are used again later. The base case in the induction is the case k = 3. We will prove the cases k = 1,2, 3 in order.
Proposition 2.7. Let X c L112 with D(X) < D(L112). Then we have
|X | < M1 =6. If equality holds, then X = X1; or Y1, up to isomorphism.
Proof. Since the diameter graph G of L112 is isomorphic to C4 U C4 U C4, where C4 is the 4-cycle, the bound |X | < 6 clearly holds. Considering the permutation of coordinates, G has the automorphism group S4. Since the stabilizer of X1 in S4 is of order 6, the orbit of X4 has length 4. Similarly the orbit of Y1 has length 4. Since the number of maximum independent sets of G is 23 = 8, this proposition follows.	□
For k = 2, we also classify (M2 - 1)-point sets X with D(X) < D(L122) in order to prove the case k = 3.
Proposition 2.8. Let X c L122 with D(X) < D(L122). Then we have
|X| < M = 12.
If |X| = 12, then X = X2, Y2, or Z2, up to isomorphism. If |X| = 11, then X is
v2 = X2 u {(-1, o, o, 1,1), (-1, o, 1, o, 1), (-1, o, 1,1,0),
(-1,1,1, o, o), (1,-1,1, o, o)},
W2 = Y2' U {(-1,1,1,0, 0), (-1,1, 0,1,0), (-1,1,0, 0,1),
(-1, 0,0,1,1), (1,1,-1, 0,0)},
or the set obtained by removing a point from X2, Y2, or Z2, up to isomorphism.
Proof. First suppose n4(X, 0) = 6 for some i. Then we have |X| < 12, and X with |X| = 12 is X2, Y2, or Z2 by Lemma 2.6. In order to find X with |X| = 11, we consider 5-point independent sets in the diameter graph of S2(1) U U2(2) or S2(1) U U2(1) U Si. If X is not isomorphic to a subset of X2, Y2, or Z2, then X = V2 from S2(1) U U2(2), and X = W2 from S2(1) U U2(1) U S1.
Suppose ni(X, 0) < 5 for any i. If |X| > 11, then the average of n4(X, 0) is greater than 4. Without loss of generality, we may assume h1(X, 0) = 5. Since the diameter graph of L112 is C4 U C4 U C4, we can show that X contains a 5-point subset of X2 or Y2.
(i) Suppose X contains a 5-point subset of X2. By considering the automorphism group of X2, we may assume X contains the 5-point subset obtained by removing (0, -1,0,1,1) or (0,0, -1,1,1). First assume that X contains the 5-point subset obtained by removing (0, -1,0,1,1). Since other candidates of elements of X are still in S2(1) U U2(2), we have |X| < 11, and if |X| = 11, then X is isomorphic to a subset of X2, Y2, or Z2. Assume that X contains the 5-point subset obtained by removing (0,0, -1,1,1). The set of other candidates of elements of X is £2(1) U ^(2) U {(1,0,1, -1,0), (1,0,1,0, -1)}. If X does not contain both (1,0,1, -1,0) and (1,0,1,0, -1), then |X| < 11, and X
8
Ars Math. Contemp. 13 (2017) 125-136
attaining this bound is isomorphic to a subset of X2, Y2, or Z2. To make a new set, X may contain (1,0,1, -1,0). The two vectors (-1,1,0,1,0), (-1,0,0,1,1) G £2(1), which are at distance %/10 from (1,0,1, -1,0), are not contained in X. The set P1 consisting of the two isolated vertices
(-1, 0, 1, 0, 1), (-1, 0,1,1, 0) G S2(1)
and 6 points
(-1,1,1, 0, 0), (-1,1,0,0,1), (1, -1,1, 0,0), (1, -1,0,1, 0), (1,-1,0,0,1), (1,0,1,0, -1)
has the unique maximum 6-point independent set
I (-1, 0,1,0,1), (-1, 0,1,1,0), (1, -1,1, 0, 0), 1 \ (1,-1, 0,1,0), (1,-1, 0, 0,1), (1, 0,1,-1, 0)
which gives X isomorphic to Y2, and n2(X, 0) = 6. If X contains a 5-point independent set in P1 and is not isomorphic to a subset of Y2, then X contains the 5-point independent
set
{(-1, 0,1,0,1), (-1,0,1,1, 0), (-1,1,1,0,0), (1, -1,1, 0,0), (1, 0,1,0, -1)}.
Then X is isomorphic to W2 and n2 (X, 0) = 6.
(ii) Suppose X contains a 5-point subset of Y2. By considering the automorphism group of Y2', we may assume X contains the 5-point subset obtained by removing (0,1, -1,0,1). The set of other candidates of elements of X is S2 (1) U S1 U {(1,0,1,0, -1)}. To make a new set, X may contain (1,0,1,0, -1). The two vectors (-1,1,0,0,1), (-1,0,0,1,1) G S2(1), which are at distance %/10 from (1,0,1,0, -1), are not contained in X. The set consisting of the two isolated vertices
(-1,1, 1, 0, 0), (-1, 1, 0,1, 0) G S2(1)
and 5 points
(-1,0,1,1,0), (-1, 0,1,0,1), (1,1, -1,0,0), (1,1,0, -1, 0), (1,1, 0, 0, -1) has the unique maximum 5-point independent set
{(-1,1,1,0,0), (-1,1,0,1, 0), (1,1, -1,0,0), (1,1,0,-1,0), (1,1, 0,0,-1)}, which gives X is isomorphic to a subset of Z2.	□
Proposition 2.9. Let X c L132 with D(X) < D(L132). Then we have
|X| < M3 = 22. If equality holds, then X = X3, Y3, or Z3, up to isomorphism.
Proof. If n(X, 0) = 12 for some i, then we have |X| < 22, and the set attaining this bound is X3, Y3, or Z3 by Lemma 2.6.
S. Adachi and H. Nozaki: On the largest subsets avoiding the diameter of (0, ±1)-vectors 9
Suppose nj(X, 0) < 11 for any i. If |X| > 22, then the average of n4(X, 0) is greater than 11, which gives a contradiction. Therefore |X | < 22, and if |X | = 22, then the average of n (X, 0) is 11, and n4(X, 0) = 11 for any i. By Proposition 2.8, X may contain
V3' = {(0, v) e L132 | v e V2},
W = {(0,w) e L132 | w e W2},
or an 11-point set obtained by removing a point from Xg, Y3', or Zg.
(i)	Suppose X contains an 11-point subset of Xg. By considering the automorphism group of Xg, X may contain the set in Xg obtained by removing (0, -1,0,0,1,1), (0, -1, 1,1,0,0), (0,0, -1,0,1,1), or (0,0,0, -1,1,1). If X contains the set Xg with (0, -1,0,0, 1,1), (0, -1,1,1,0,0), or (0,0, -1,0,1,1) removed, then the set of other candidates of X is still £3(1) U U3(3), and |X| < 22. Suppose X contains the set Xg with (0,0,0, -1,1,1) removed. Then new candidates of vectors of X are only (1,0,0,1, -1,0) and (1,0,0,1,0, -1), and X may contain (1,0,0,1, -1,0). The three vectors (-1,1,0,0,1,0), (-1,0,1, 0,1,0), and (-1,0,0,0,1,1), which are at distance V'W from (1,0,0,1, -1,0), are not contained in X. Therefore by |X | = 22, the other new candidate (1,0,0,1,0, -1), and two isolated vectors (-1,0,0,1,0,1), and (-1,0,0,1,1,0) must be contained in X. Moreover a 7-point independent set must be obtained from Matching (i). Since (-1,1,0,0,1,0) and (-1,0,1,0,1,0) are not contained in X, by Lemma 2.4, (1, -1,0,0,0,1) and (1,0, -1,0, 0,1) must be contained in X, and consequently any element of U2(2) is contained in X. This implies n2(X, 1) = 0, and X is isomorphic to X3, Y3, or Z3.
(ii)	Suppose X contains an 11-point subset of Y3'. By considering the automorphism group of Y3', X may contain the set in Y3' obtained by removing (0, -1,0,0,1,1), (0, -1,1, 1,0,0), or (0,0,1, -1,0,1). If X contains the set Y3' with (0, -1,0,0,1,1), or (0, -1,1,1, 0,0) removed, then the set of other candidates of X is still S3(1) U U3(2) U S1, and |X | < 22. Suppose X contains the set Y3' with (0,0,1,-1,0,1) removed. Then a new candidate of an element of X is only (1,0,0,1,0, -1), and X may contain (1,0,0,1,0, -1). The three vectors (-1,1,0,0,0,1), (-1,0,1,0,0,1), and (-1,0,0,0,1,1), which are at distance %/10 from (1,0,0,1,0, -1), are not contained in X. By considering Matching (ii), we can show |X | < 22.
(iii)	Suppose X contains an 11-point subset of Z3. By considering the automorphism group of Z3, X may contain the set in Z3 obtained by removing (0,1, -1,0,0,1). Then a new candidate of an element of X is only (1,0,1,0,0, -1), and X may contain (1,0,1,0,0, -1). The three vectors (-1,1,0,0,0,1), (-1,0,0,1,0,1), and (-1,0,0,0,1,1), which are at distance %/10 from (1,0,1,0,0, -1),are not contained in X .By considering Matching (iii), we can show | X| < 22.
(iv)	Suppose X contains V3'. The set of other candidates of X is S3(1) U U3(3) \ {(1, -1,1,0,0,0)}, and the maximum independent set is of order at most 10 by Matching
(i).	Thus |X | < 22.
(v)	Suppose X contains W3. The set of other candidates of X is S3(1) U U3(2) US1 \ {(1, -1,0,1,0,0)}, and the maximum independent set is of order at most 10 by Matching
(ii).	Thus |X| < 22.
Therefore this proposition follows.	□
Finally we prove Theorem 2.5.
10
Ars Math. Contemp. 13 (2017) 125-136
Proof of Theorem 2.5. By Propositions 2.7-2.9, the statement holds for k = 1,2, 3. By the inductive hypothesis and Lemma 2.3, if |X| > Mk, then there exists i e {1,..., n} such that n4(X, 0) = Mk-1 for k > 4. By Lemma 2.6, this theorem holds for any k.	□
3 Classification of the largest 4-distance sets which contain J(n, 4)
A finite set X in Rd is called an s-distance set if the set of Euclidean distances of two distinct vectors in X has size s. The Johnson graph J(n, m) = (V, E), where
V = {{ii,..., im} | 1 < ii < • • • < im < n, ij e Z}, E = {(v, u) | |v O u| = m — 1, v, u e V},
is represented into Rn-1 as the m-distance set J(n, m) = L0,„_m,m. Indeed J(n, m) c Rn, but the summation of all entries of any x e J(n, m) is m, and J(n, m) is on a hyperplane isometric to Rn-1. Bannai, Sato, and Shigezumi [1] investigated m-distance sets containing J(n, m). In their paper, for m < 5 and any n, the largest m-distance sets containing J(n, m) are classified except for (n, m) = (9,4). In this section, the case (n, m) = (9,4) will be classified.
The set of Euclidean distances of two distinct points of J(9,4) is {v^, V4, >/6, v^}. The set of vectors which can be added to J(9,4) while maintaining 4-distance is the union of the following sets [1].
X=
X(iii) =
X(ii) = X=
4


where the exponents inside indicate the number of occurrences of the corresponding numbers, and the exponent P outside indicates that we should take every permutation. They conjectured that J(9,4) U X(i) U X(iii) U {(—4/3, (2/3)8)} U X(iv)' is largest, where (—4/3, (2/3)8) e X(ii), and
X(iv)' = j(xi,...,xg) e X(i
) I xi
3
4 3
' 4
, 3,

2 4 3, 3

Actually X(iv)' is isometric to Xe in Section 2 by replacing —2/3, 1/3, 4/3 to —1, 0, 1, respectively. Let X(resp.	) be the set obtained from Ye (resp. Ze) by the same
manner. Using Theorem 2.5, we can classify the largest 4-distance sets containing J(9,4).
Theorem 3.1. Let X c {(x1,...,x9) which contains J(9,4). Then we have
| x1 + • • • + xg = 1} be a 4-distance set
|X| < 258.
p
8
3
2
e
1
2
3
3
e
2
4
2
u
3
3
t
If equality holds, then X is one of the following, up to permutations of coordinates.
S. Adachi and H. Nozaki: On the largest subsets avoiding the diameter of (0, ±1)-vectors 11
(1)	J(9,4) U X(i) U X(iii) U {(-4/3, (2/3)8)} U X(iv)',
(2)	J(9,4) U X(i) U X(iii) U {(-4/3, (2/3)8)} U X(iv)'',
(3)	,7(9,4) U X(i) U X(iii) U {(-4/3, (2/3)8)} U X(iv)'''.
Proof. For any x G X(i) U X(iii), y G U4=1X(j), the Euclidean distance of x, y is i
in
{a/2, v4, v6, v8}, and hence X may contain X(i) U X(iii). The set X(iv) is isometric to L162 by replacing -2/3, 1/3, 4/3 to -1, 0, 1, respectively. Therefore the largest subsets of X(iv) with distances {V2 V4 V6, V8} are X(iv)', X(iv)'', and X(iv)''', up to permutations of coordinates. If X does not contain any element of X(ii), then
|X | < |J(9, 4) U X(i) U X (iii)| + |X(iv)' | = 257.
If X contains x G X(ii) with xj = -4/3, then X cannot contain y G X(iv) with yi = 4/3. By re-ordering the vectors, we may assume that the set
X(ii) (t) = {x G X(ii) | xj = -4/3, 3i G {1,..., t}}
is in X for some t. Clearly, from the definition of X (jj)(t), this set must have size t. For t = 7,8, 9, X contains at most one element of X(iv), and hence
|X | < |J(9,4) U X(i) U X (iii)| + t + 1 < 181.
If the set X(ii)(t) is in X for 1 < t < 6, then consider the set of vectors in X n X(iv) in which the entry 1/3 occurs in all of the first t positions. The final 9 - t entries of one of these vectors forms a vector from L1,6-t,2; no two vectors in this set can be at the maximum distance. Thus the size of
|{x G X n X(iv) | xj = 1/3, Vi G {1, .. ., t}}|
is bounded by M6-t. It is clear that
|{x G X n X(iv) | xj = -2/3, xjl = 4/3, xj2 = 4/3,
3i G {1,...,t}, 3ji,j2 G{t +1,..., 9}}|
is bounded by t (9-1). Thus, for 1 < t < 6, we have
|X| < |J(9,4) U X(i) U X(iii) | +1 + M6-t + ^9 - ^
t3 9t2 31t
=----1---+ 257 < 258,
3 2 6	< '
and equality holds only if t = 1. The sets attaining this bound are only the three sets in the statement.	□
4 Remarks on other Mmkl
Actually it is hard to determine Mmkl for other (m, k, l) by a similar manner in Section 2. Fix m, l, where m < l. By Proposition 2.2, if k < l - m, then Mmkl = (mr—-1)(m"lk).
12
Ars Math. Contemp. 13 (2017) 125-136
In general there are many largest sets for k = l — m. For k > l — m, we can inductively construct a large set Xk C Lmkl satisfying D(Xk) < D(Lmkl) as follows
Xk = {(0, x') | x' € Xfc_i} U {(xi,. .., x„) € Lmkl | xi = —1},
where Xl-m is a largest set for k = l — m. Therefore we have
_	fm + l- 1N fk + m + A /m + l-T
Mmkl > Mmki := + 1	+ , + + +
ym — 1 J \ m + l J \ m
We can generalize Lemma 2.3 as follows.
Lemma 4.1. Let X C Lmkl with D(X) < D(Lmkl). Suppose k > m(— m — l +1, and |X| > Mmkl. Then there exists i € {1,..., n} such that Ui(X, 0) > Mm,k-1,l.
Proof. This lemma is immediate because the average of ni (X, 0) is
1 £ ni(X, 0)= k|X| > kMmkl
n	m + k + l m + k + l
i=1
m +1 fm + k + A	_
= Mm,k-1,l--^^ , > Mk-1 — 1. □
m + k + l	l
In the manner of Section 2, it is hard to classify Mmkl for m — l + 1 < k < m (— m — l. Moreover it seems to be difficult to give matchings, like Matching (i) or (ii), of many possibilities of Xk. We need another idea to determine other Mmkl.
5 Acknowledgments
The authors thank Sho Suda for providing useful information. References
[1]	E. Bannai, T. Sato and J. Shigezumi, Maximal m-distance sets containing the representation of the Johnson graph J(n, m), Discrete Math. 312 (2012), 3283-3292, doi:10.1016/j.disc.2012.07. 028, http://dx.doi.org/10.1016/j.disc.2012.07.028.
[2]	P. Borg, Intersecting families of sets and permutations: a survey, Int. J. Math. Game Theory Algebra 21 (2012), 543-559 (2013).
[3]	P. Delsarte, J. M. Goethals and J. J. Seidel, Spherical codes and designs, Geometriae Dedicata 6 (1977), 363-388.
[4]	M. Deza and P. Frankl, Every large set of equidistant (0, +1, —1)-vectors forms a sunflower, Combinatorica 1 (1981), 225-231, doi:10.1007/BF02579328, http://dx.doi.org/10. 1007/BF02579328.
[5]	M. Deza and P. Frankl, Erd6s-Ko-Rado theorem—22 years later, SIAM J. Algebraic Discrete Methods 4 (1983), 419-431, doi:10.1137/0604042, http://dx.doi.org/10.1137/ 0604042.
[6]	M. Deza and P. Frankl, On t-distance sets of (0, ±1)-vectors, Geom. Dedicata 14 (1983), 293301, doi:10.1007/BF00146909, http://dx.doi.org/10.100 7/BF0 014 690 9.
[7]	M. Deza and P. Frankl, Bounds on the maximum number of vectors with given scalar products, Proc. Amer. Math Soc. 95 (1985), 323-329, doi:10.2307/2044537, http://dx.doi.org/
10.2307/2044537 .
S. Adachi and H. Nozaki: On the largest subsets avoiding the diameter of (0, ±1)-vectors 13
[8]	P. Erdos, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 12 (1961), 313-320.
[9]	P. Frankl, The shifting technique in extremal set theory, in: Surveys in combinatorics 1987 (New Cross, 1987), Cambridge Univ. Press, Cambridge, volume 123 of London Math. Soc. Lecture Note Ser., pp. 81-110, 1987.