cp's OEIS Frontend

A085680 Size of largest code of length n and constant weight 2 that can correct a single adjacent transposition.

%I A085680 #61 Mar 20 2022 02:15:45
%S A085680 1,1,2,3,4,6,7,9,11,13,15,17,20,23,26,29,32,36,40,44,48,52,57,62,67,
%T A085680 72,77,83,89,95,101,107,114,121,128,135,142,150,158,166,174,182,191,
%U A085680 200,209,218,227,237,247
%N A085680 Size of largest code of length n and constant weight 2 that can correct a single adjacent transposition.
%C A085680 Form a graph whose n-choose-2 vertices correspond to the binary vectors of length n with exactly two 1's and n-2 0's in each vector.
%C A085680 Join two vertices u and v by an edge if v can be obtained from u by transposing a pair of adjacent coordinates.
%C A085680 a(n) is the maximal size of a subset S of the vertices such that the distance between every pair of vertices in S is at least 3.
%C A085680 For n=4 the graph is
%C A085680 ...........1001
%C A085680 ........../....\
%C A085680 1100--1010......0101--0011
%C A085680 ..........\..../
%C A085680 ...........0110
%C A085680 so a(4) = 2 (use 1100 and 0011 as the set S, or 1100 and 0101). - _N. J. A. Sloane_, Mar 15 2017
%C A085680 From Luis Manuel Rivera, Mar 15 2017: (Start)
%C A085680 This sequence also arises in the problem of determining the 2-packing number of certain graphs (the 2-token graph of a path with n vertices).
%C A085680 Let G be a graph of order n and let k be an integer such that 1 <= k <= n-1. The k-token graph F_k(G) of G is defined to be the graph with vertex set all k-subsets of V(G), where two vertices are adjacent in F_k(G) whenever their symmetric difference is an edge of G.
%C A085680 A 2-packing of a graph G is a subset S of V(G) such that d(u, v) >= 3, for every pair of distinct vertices u, v in S. The 2-packing number of G is the maximum cardinality of a 2-packing of G.
%C A085680 For n != 2, A085680(n) is also the 2-packing number of F_2(P_n), where P_n is the path graph with vertex set {1, ..., n} and edge set {{i, i+1} : 1 <= i <= n-1}. The bijection f between the two graphs is given as follows: for A in V(F_2(P_n)), f(A)=a_1 ... a_n, where a_i=1 iff i in A.
%C A085680 This comment is based on joint work with my colleagues José Manuel Gómez Soto, Jesús Leaños, and Luis Manuel Ríos-Castro. (End)
%C A085680 From Luis Manuel Rivera, Mar 23 2017: (Start)
%C A085680 My colleagues and I have obtained the following lower bounds for a(n)=A085680(n), n >= 10:
%C A085680 a(n) >= (n^2-n+20)/10, for n == 0 or 1 mod 5,
%C A085680 a(n) >= (n^2-n+18)/10, for n == 2 or 4 mod 5.
%C A085680 a(n) >= (n^2-n+14)/10, for n == 3 mod 5.
%C A085680 In all cases, this lower bound coincides with the 50 values that are presently known. We conjecture that these formulas are in fact the exact values for a(n). (End)
%H A085680 J. M. Gómez Soto, J. Leaños, L. M. Ríos-Castro, and L. M. Rivera, <a href="/A085680/a085680.pdf">On an error-correcting code problem</a>
%H A085680 Sofía Ibarra and Luis Manuel Rivera, <a href="https://arxiv.org/abs/1907.06008">The automorphism groups of some token graphs</a>, arXiv:1907.06008 [math.CO], 2019.
%H A085680 Luis Manuel Rivera, <a href="https://www.researchgate.net/profile/Luis_Rivera37/publication/324760132_Some_properties_of_token_graphs/links/5ae11908aca272fdaf8d8cf6/Some-properties-of-token-graphs.pdf">Some properties of token graphs</a>, 2018.
%H A085680 N. J. A. Sloane, <a href="/A265032/a265032.html">Challenge Problems: Independent Sets in Graphs</a>
%F A085680 It appears that the second differences eventually have period 5: 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, ... However, this is only a conjecture. If true, it would imply the g.f. (1-x+x^2-x^10+x^11)/((1-x)^2*(1-x^5)). - _Rob Pratt_, Mar 15 2017
%Y A085680 Column 2 of A085684.
%K A085680 nonn,more
%O A085680 2,3
%A A085680 _N. J. A. Sloane_, Jul 16 2003
%E A085680 a(26)-a(38) from _Rob Pratt_, Mar 15 2017
%E A085680 a(39)-a(50) from _Rob Pratt_, Mar 19 2017