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

%I #61 Mar 20 2022 02:15:45

%S 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 72,77,83,89,95,101,107,114,121,128,135,142,150,158,166,174,182,191,

%U 200,209,218,227,237,247

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

%C 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 Join two vertices u and v by an edge if v can be obtained from u by transposing a pair of adjacent coordinates.

%C 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 For n=4 the graph is

%C ...........1001

%C ........../....\

%C 1100--1010......0101--0011

%C ..........\..../

%C ...........0110

%C so a(4) = 2 (use 1100 and 0011 as the set S, or 1100 and 0101). - _N. J. A. Sloane_, Mar 15 2017

%C From Luis Manuel Rivera, Mar 15 2017: (Start)

%C 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 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 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 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 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 From Luis Manuel Rivera, Mar 23 2017: (Start)

%C My colleagues and I have obtained the following lower bounds for a(n)=A085680(n), n >= 10:

%C a(n) >= (n^2-n+20)/10, for n == 0 or 1 mod 5,

%C a(n) >= (n^2-n+18)/10, for n == 2 or 4 mod 5.

%C a(n) >= (n^2-n+14)/10, for n == 3 mod 5.

%C 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 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 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 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 N. J. A. Sloane, <a href="/A265032/a265032.html">Challenge Problems: Independent Sets in Graphs</a>

%F 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 Column 2 of A085684.

%K nonn,more

%O 2,3

%A _N. J. A. Sloane_, Jul 16 2003

%E a(26)-a(38) from _Rob Pratt_, Mar 15 2017

%E a(39)-a(50) from _Rob Pratt_, Mar 19 2017