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

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, 72, 77, 83, 89, 95, 101, 107, 114, 121, 128, 135, 142, 150, 158, 166, 174, 182, 191, 200, 209, 218, 227, 237, 247

Offset: 2

Author

N. J. A. Sloane, Jul 16 2003

Keywords

• nonn
• more

Comments

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.

Join two vertices u and v by an edge if v can be obtained from u by transposing a pair of adjacent coordinates.

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.

For n=4 the graph is

...........1001

........../....\

1100--1010......0101--0011

..........\..../

...........0110

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

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

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).

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.

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.

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.

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)

From Luis Manuel Rivera, Mar 23 2017: (Start)

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

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

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

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

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)

Links

• J. M. Gómez Soto, J. Leaños, L. M. Ríos-Castro, and L. M. Rivera, On an error-correcting code problem
• Sofía Ibarra and Luis Manuel Rivera, The automorphism groups of some token graphs, arXiv:1907.06008 [math.CO], 2019.
• Luis Manuel Rivera, Some properties of token graphs, 2018.
• N. J. A. Sloane, Challenge Problems: Independent Sets in Graphs

Crossrefs

Column 2 of A085684.

Formula

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

Extensions

a(26)-a(38) from Rob Pratt, Mar 15 2017

a(39)-a(50) from Rob Pratt, Mar 19 2017