Challenge Problems: Independent Sets in Graphs

N. J. A. Sloane
OEIS Foundation, 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Home page: http://NeilSloane.com;     Email: njasloane(AT)gmail.com

Created October 2000; updated July 04 - July 18, 2003; May 15, 2005; July 28, 2005, Oct 24 2009, Nov 18 2009; Jul 19 2011; June 18 2015; Dec 05 2015.

KEYWORDS: challenge graphs, maximal independent set, maximal clique, clique-finding, transposition-correcting code, deletion-correcting code, code for Z-channel, code for asymmetric channel, Varshamov-Tenengolts codes, non-classical codes, non-standard codes, Lovasz theta numbers.

Abstract

This is a collection of graphs arising from coding theory in which we would very much like to know the sizes of the maximal independent sets.


Details


The Graphs


Graphs From Single-Deletion-Correcting Codes


Graphs From Two-Deletion-Correcting Codes


Graphs From Codes For Correcting a Single Transposition (Excluding the End-Around Transposition)


Graphs From Codes For Correcting a Single Transposition (Including the End-Around Transposition)


Graphs From Codes For Correcting One Error on the Z-Channel

(Also Called Codes For Correcting One Unidirectional or Asymmetric Error)


References


Lovasz theta numbers

In March 2005 Brian Borchers computed the Lovasz theta numbers for many of these graphs. This gives an upper bound on the size of the largest independent set. The results are as follows.

(These results have been incorporated in the above paragraphs.)

Problem                 Theta        Bound

1dc.64                  10.0000         10
1dc.128                 16.841880(**)   16
1dc.256                 30.0000         30
1dc.512                 53.0307         53
1dc.1024                95.9847         95
1dc.2048               174.7290        174

1et.64                  18.8000         18
1et.128                 29.2309         28*
1et.256                 55.1142         53*
1et.512                104.4204        102*
1et.1024               184.2260        180*
1et.2048               342.0288        338*

1tc.64                  20.0000         20
1tc.128                 38.0000         38
1tc.256                 63.3999         63
1tc.512                113.4002        112*
1tc.1024               206.3042        205*
1tc.2048               374.6431        372*

1zc.128                 20.6667         20
1zc.256                 38.0000         38
1zc.512                 68.7500         68
1zc.1024               128.6667        128
1zc.2048               237.4000        237
1zc.4096                 -

2dc.128                  5.2424          5
2dc.256                  7.4618          7
2dc.512                 11.7678         11
2dc.1024                 -
2dc.2048                 -

He remarks that, for the tc and et problems, it is possible to get tighter bounds by computing the theta numbers for each of the connected components, the resulting improvements are marked with asterisks (*).

(**) Entry corrected by Alexander Engau, Sep 10 2010


Codes over alphabet of size 4

For a code of length 6 over an alphabet of size 4, the size of the largest code with minimal distance 3 is somewhere in the range [164-179].
This is asking for the maximal independent set in the graph with 4096 vertices labeled {0,1,2,3}^6,
with two vertices joined iff their Hamming distance is at least 3.
See Andries Brouwer's table for more information. This question was mentioned in the following paper:
Galina T. Bogdanova, Andries E. Brouwer, Stoian N. Kapralov and Patric R.J. Ostergard, Error-Correcting Codes over an Alphabet of Four Elements, Designs, Codes and Cryptography 23 (2001) 333-342.
Of course no structure is assumed, so the question of whether the alphabet is GF(4) or Z/4Z does not arise.
Length 6 and minimal distance 3 is (currently, Dec 05 2015) the smallest case where the size of a maximal code over an alphabet of size 4 is not presently known.
The sizes of the maximal codes with minimal distance 3 in this family form sequence A265032 in the OEIS.