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 themselves are listed below.

Notation. The graphs are specified in the DIMACS format. For a graph with say 64 nodes and 543 edges, the first line of the file would read:
p edge 64 543
followed by 543 lines like
e 1 2
e 1 3
e 1 20
...
indicating that there are edges from node 1 to 2, from node 1 to 3, from node 1 to 20, etc.
The nodes are labeled consecutively starting at 1. Each edge is specified just once.
The files have been gzipped. To uncompress them, run gunzip on them.
(See the DIMACS Implementation Challenges web page for further details about the format.)

In most of these graphs the nodes represent binary vectors. The binary vector 000000 would become node 1, 000001 becomes node 2, etc.
In other words the binary vector is converted to decimal and 1 is added.

So that you can check your algorithms - and the notation used here - a number of smaller examples are included where the size of the maximal independent set is already known.

If you can find the size of the largest independent set in any of these graphs (except of course for those that have already been solved) please let one of the OEIS bureaucrats know so that this page and the associated sequences can be updated. Currently (December 2015) the bureaucrats are N. J. A. Sloane, David Applegate, Russ Cox, and Charles Greathouse. Even information about lower bounds that are better than those presently known will be welcomed. The results will be posted here, with full credit of course. Please supply:
- the name of the graph
- the size of the maximal independent set
- the numbers of the nodes in a maximal independent set (important because these will be interesting codes)
- the method used
- any relevant references, and of course
- your name, affiliation and email address.
These are just samples of graphs arising from various classes of codes. If these are too easy there are many bigger examples that can be given.

Of course these become maximal clique problems if the graph is replaced by its complement.

Note that in English the adjectival form of maximum is maximal, and so a maximal independent set means one with the largest possible number of nodes (a global maximum).

Thanks to several correspondents who have sent comments on or improvements to this web page:
- Brian Borchers,
- Sergiy Butenko, Panos Pardalos, Ivan Sergienko, Vladimir Shylo, and Petro Stetsyuk (see Ref. [BPS03]),
- Johan Claes,
- David Eddy,
- W. J. van Hoeve,
- Andrew Makhorin,
- Ketan Narendra Patel and Igor Markov,
- Pablo San Segundo and Jorge Artieda,
- James B. Shearer,
- Guenter Stertenbrink,
- Dragan Stevanovic,
Their improvements have been incorporated in the following paragraphs.

The Graphs

Graphs From Single-Deletion-Correcting Codes

1dc.64.txt.gz, a 64-node graph in which the size of a maximal independent set is 10 (for example, the Varshamov-Tenegolts code VT₀(6) of length 6).

1dc.128.txt.gz, a 128-node graph in which it is known that the size of a maximal independent set is 16. The Varshamov-Tenegolts code VT₀(7) of length 7 forms an independent set of size 16 (see Ref. [Sl00]), namely
```
  1  14  20  21  35  48  55  58  66  79  86  89 100 101 120 123
```
and Magma has confirmed that no larger independent set exists.

1dc.256.txt.gz, a 256-node graph in which it is known that the size of a maximal independent set is 30. The Varshamov-Tenegolts code VT₀(8) of length 8 forms an independent set of size 30, namely
```
  1  15  22  25  36  37  60  61  67  88  91 103 106 113 127 130 144 151 154 166
169 190 196 197 220 221 232 235 242 256
```
and David Applegate has confirmed that no larger independent set exists (see Ref. [Sl00]). (Confirmed by N. J. A. Sloane using Cliquer [NO03], July 04, 2003.)

1dc.512.txt.gz, a 512-node graph in which it is now known that the size of a maximal independent set is 52. The Varshamov-Tenegolts code VT₀(9) forms an independent set of size 52, namely
```
  1  16  23  26  38  41  63  68  69  94 108 109 115 131 156 157 168 171 178 199
202 209 224 239 246 249 258 280 283 295 298 305 320 326 329 351 366 372 373 388
389 414 428 429 435 456 459 466 481 496 503 506
```
(see Ref. [Sl00]).
November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) show that 52 is best possible.
April 29, 2002: Ketan Narendra Patel , a post-doctoral researcher in the Electrical Engineering department at the University of Michigan working with Professor Igor Markov, confirms that 52 is best possible.
He says: "We formulated the problem as an integer linear program. Each vertex is represented by a binary variable, with a 1 signifying membership in the independent set. If two vertices share an edge we impose the constraint that the sum of their variables must be less than or equal to 1 (both cannot be members). We find the size of the largest independent set by maximizing the sum of all of the variables. We solved the problem using the optimization program CPLEX 7.00."

1dc.1024.txt.gz, a 1024-node graph. The Varshamov-Tenegolts code VT₀(10) forms an independent set of size 94, namely
```
  1  24  27  39  42  49  70  73  96 111 118 121 132 133 159 174 180 181 204 205
211 226 252 253 259 286 300 301 307 328 331 338 353 376 379 391 394 401 432 439
442 463 470 473 484 485 511 514 540 541 552 555 562 583 586 593 624 631 634 646
649 672 687 694 697 718 724 725 739 766 772 773 799 814 820 821 844 845 851 866
892 893 904 907 914 929 952 955 976 983 986 998 1001 1024
```
(see Ref. [Sl00]).
March 21, 2005: Brian Borchers (see below) has given an upper bound of 95, showing that the size of a maximal independent set is either 94 or 95.
June 30, 2005: Brian Borchers has shown that 94 is the answer. He says: "This was finally solved by a branch and bound calculation using the Lovasz theta number SDP bounds. The computation required 298 hours on 16 processors of an IBM p690 system at the National Center for Supercomputer Applications."

Most wanted! 1dc.2048.txt.gz, a 2048-node graph in which the size of a maximal independent set is not known. The Varshamov-Tenegolts code VT₀(11) forms an independent set of size 172, namely

   1   28   29   40   43   50   71   74   81  120  123  134  137  176  183
 186  207  214  217  228  229  256  260  261  288  303  310  313  334  340
 341  355  383  396  397  403  418  446  449  476  477  488  491  498  515
 543  558  564  565  588  589  595  610  638  648  651  658  673  700  701
 728  731  743  746  753  775  778  785  824  827  848  855  858  870  873
 911  918  921  932  933  960  963  991 1006 1012 1013 1026 1054 1068 1069
1075 1096 1099 1106 1121 1148 1149 1159 1162 1169 1208 1211 1232 1239 1242
1254 1257 1286 1289 1328 1335 1338 1359 1366 1369 1380 1381 1408 1422 1428
1429 1443 1471 1474 1502 1516 1517 1523 1540 1541 1568 1583 1590 1593 1614
1620 1621 1635 1663 1676 1677 1683 1698 1726 1729 1756 1757 1768 1771 1778
1800 1803 1810 1825 1852 1853 1880 1883 1895 1898 1905 1936 1943 1946 1958
1961 1988 1989 2016 2031 2038 2041

(see Ref. [Sl00]), but it is possible that a larger independent set exists. March 21, 2005: Brian Borchers (see below) has given an upper bound of 174, so the answer here is in the range 172-174.

The sizes of the maximal independent sets in this family of graphs agree with sequence A000016 in the OEIS for the graphs with <= 1024 nodes (see Ref. [Sl00]). Whether they agree with this sequence for larger graphs is an open problem. Certainly sequence A000016 gives a lower bound, but it is possible that there exist larger independent sets in the graphs with 2048 or more nodes.

Graphs From Two-Deletion-Correcting Codes

2dc.128.txt.gz, a 128-node graph in which it is known that the size of a maximal independent set is 5.
For example, nodes {54, 65, 72, 121, 128}.

2dc.256.txt.gz, a 256-node graph in which it is known that the size of a maximal independent set is 7.
For example, nodes {63, 77, 129, 136, 214, 241, 256}.

2dc.512.txt.gz, a 512-node graph. On Apr 28, 2001, Guenter Stertenbrink reported that this could be searched with brute force in 30 mins. He finds that there are 120 maximal independent sets of size 11, one of which is {1, 8, 63, 105, 141, 220, 294, 449, 456, 505, 512}.
Confirmed by S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk [BPS03], November 28, 2001.

2dc.1024.txt.gz, a 1024-node graph in which it is known that the size of a maximal independent set is 16.
On Apr 28, 2001, Guenter Stertenbrink reported that this graph contains an independent set of size 16, which is therefore a lower bound on the maximal size.
Confirmed by S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk [BPS03], November 28, 2001; also by Johan Claes Nov 27, 2002.
One example is {1, 8, 43, 64, 121, 344, 402, 500, 564, 689, 830, 897, 904, 939, 1017, 1024}.
On Sep 20 2003 James B. Shearer reported that he has shown that the independence number of this graph is indeed 16. He says:
"I did this by exhaustive search helped by the following two observations:
"1. We may assume the vertices corresponding to the all 0's vector and to the all 1's vector are included in a maximal independent set (since their neighborhoods are cliques).
"2. We may assume at least half the vertices in the independent set correspond to vectors with first coordinate 0 (since the graph is symmetric with respect to mapping vertices to their complements as 0-1 vectors).
"The search took about 750 seconds on a 43p-140 RS/6000 workstation (which uses a 332 Mhz 604e powerpc chip)."

2dc.2048.txt.gz, a 2048-node graph in which it is known that the size of a maximal independent set is 24.
July 25, 2005: Brian Borchers has found an independent set of size 24, namely
```
    1         8        57        64
  197       334       482       508
  628       643       792       875
 1017      1078      1149      1193
 1392      1604      1761      1793
 1854      1869      1992      2047
```
Comments from Pablo San Segundo, Dec 04 2015: The search for a maximal clique in the graph 2dc.2048 has now finished. The answer is 24 (which was already known to be a lower bound).
The total time was 16.4 days using a 20-core XEON with 128Gb. 18-cores out of the 20 were in fact used.
The solution was found by a strong heuristic algorithm during pre-processing (about 5s). The actual search time was used “only” to prove optimality. The actual maximum clique algorithm is our most recent variant based on infra-chromatic BBMCX, described here, but as yet unpublished: https://www.researchgate.net/profile/Pablo_San_Segundo.
The project was carried out by Pablo San Segundo and Jorge Artieda, Polytechnic University of Madrid (UPM) and Center of Automation and Robotics (CAR). Supported by National Grant DPI 2014-53525-C3-1-R .

The sizes of the maximal independent sets in this family of graphs form sequence A057591 in the OEIS

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

These graphs all decompose into k+1 connected components, where k = log_2 of the number of nodes.
That is, the subgraphs defided by the binary vectors of length n and weight w may be treated individually.

1tc.8.txt.gz, an 8-node graph in which it is known that the size of a maximal independent set is 4.

1tc.16.txt.gz, a 16-node graph in which it is known that the size of a maximal independent set is 8.

1tc.32.txt.gz, a 32-node graph in which it is known that the size of a maximal independent set is 12.

1tc.64.txt.gz, a 64-node graph in which it is known that the size of a maximal independent set is 20.
For example, nodes { 1, 5, 7, 8, 15, 21, 29, 31, 33, 34, 36, 40, 49, 50, 54, 56, 57, 61, 63, 64 }.

1tc.128.txt.gz, a 128-node graph in which the size of a maximal independent set is 38.
For example, nodes { 1, 2, 4, 8, 9, 13, 15, 16, 18, 29, 30, 32, 36, 41, 50, 57, 58, 60, 64, 65, 67, 71, 72, 79, 93, 95, 97, 99, 100, 104, 113, 114, 118, 120, 121, 125, 127, 128 }.

1tc.256.txt.gz, a 256-node graph in which the size of a maximal independent set is 63.

1tc.512.txt.gz, a 512-node graph. November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) showed that a maximal independent set has size 110.
April 29, 2002: Ketan Narendra Patel confirmed that 110 is best possible. Confirmed also by N. J. A. Sloane using Cliquer [NO03], July 07, 2003.

1tc.1024.txt.gz, a 1024-node graph in which the size of a maximal independent set is 196.
On Apr 28, 2001, Guenter Stertenbrink reported that this graph contains an independent set of size 188.
November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) increased the lower bound to 196.
July 17, 2003: N. J. A. Sloane used Cliquer [NO03] to show that the size of a maximal independent set is 196. This took 200 hours on a MAC OS X.

1tc.2048.txt.gz, a 2048-node graph in which the size of a maximal independent set is 352.
November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) reported that this graph contains an independent set of size 352.
May 15, 2005: Brian Borchers (see below) has obtained an upper bound of 362, as follows:
```
Comp   Bound    Best known
1          1       1 opt
2          4       4 opt
3         13      13 opt
4         33      32 opt
5         59      55 opt
6         76      71
7         76      71
8         59      55 opt
9         33      32 opt
10        13      13 opt
11         4       4 opt
12         1       1 opt

Best known: 352
Best bound: 362
```
The smaller components are easily (within a few hours each) handled by either his Lovasz theta-based branch and bound code or by MINTO on the integer programming formulation, but the two largest components haven't cracked yet.
July 27, 2005: Brian Borchers reports that "Using my branch and bound code, I've lowered the bounds on components 6 and 7 of 1tc.2048 to 73. This puts an overall bound of 356 on the size of the MIS. Each of these computations took about 48 hours on my desktop machine. I've also gotten times for getting the bounds down to 74 and 75.
"Exponential extrapolation from the computations that I've done suggests that it would take about 100 CPU days to prove that 71 is optimal for each of these components. So, I'm working with a student at ASU to parallelize the branch and bound code and run it on a large cluster. This should bring the solution time down to a reasonable day or two."
Oct 16 2009: Brian Borchers reports that: "I've finally resolved problem 1tc.2048. 352 is optimal. I used my SDP based branch and bound code to resolve the p6 component (which is isomorphic to the p7 component.) It took about 2 weeks of time on my new machine (with two quad core Intel Xeon 5530 processors) and over 1,000,000 nodes in the B & B tree to solve the problem.

The sizes of the maximal independent sets in this family of graphs form sequence A057608 in the OEIS. The size of the maximal independent set for length n and constant weight w is given in sequence A085684.

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

These graphs all decompose into k+1 connected components, where k = log_2 of the number of nodes.

1et.64.txt.gz, a 64-node graph in which it is known that the size of a maximal independent set is 18.
For example, nodes { 1, 5, 8, 13, 15, 29, 33, 35, 36, 47, 49, 50, 52, 56, 57, 61, 63, 64 }.

1et.128.txt.gz, a 128-node graph in which the size of a maximal independent set is 28.
For example, nodes {1, 2, 9, 12, 13, 18, 26, 30, 32, 39, 40, 41, 53, 59, 62, 64, 67, 68, 79, 84, 88, 98, 106, 113, 117, 118, 120, 128}.

1et.256.txt.gz, a 256-node graph in which the size of a maximal independent set is 50.
(An earlier version of this page said 48, but that was a simple arithmetic error - the 9 subgraphs contain maximal independent sets of sizes 1, 2, 6, 10, 12, 10, 6, 2, 1, respectively, and the sum of these numbers is 50, not 48! Thanks to several correspondents for pointing this out.)

1et.512.txt.gz, a 512-node graph. November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) show that the size of a maximal independent set is 100.
Confirmed by N. J. A. Sloane using Cliquer [NO03], July 09, 2003.

1et.1024.txt.gz, a 1024-node graph in which the size of a maximal independent set is 171.
November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) reported that this graph contains an independent set of size 171.
April 14, 2005: Brian Borchers has confirmed that the correct answer is 171.
For example, nodes { 1, 2, 4, 8, 9, 11, 15, 16, 25, 26, 30, 34, 36, 45, 52, 56, 59, 63, 69, 71, 79, 96, 97, 98, 102, 113, 116, 117, 123, 124, 128, 129, 138, 140, 153, 156, 157, 175, 191, 195, 196, 200, 208, 211, 218, 225, 231, 233, 236, 240, 245, 247, 255, 258, 265, 269, 279, 306, 313, 317, 329, 333, 334, 370, 380, 381, 385, 394, 404, 419, 431, 441, 449, 454, 456, 457, 461, 464, 474, 483, 487, 494, 497, 501, 504, 509, 512, 516, 520, 528, 530, 538, 543, 548, 556, 560, 561, 570, 574, 576, 583, 610, 612, 616, 621, 625, 630, 640, 642, 655, 665, 668, 682, 733, 737, 740, 744, 762, 767, 772, 773, 776, 781, 784, 786, 790, 797, 799, 800, 801, 819, 820, 827, 828, 836, 837, 846, 863, 864, 869, 874, 884, 889, 892, 898, 903, 904, 912, 919, 921, 930, 942, 947, 957, 960, 961, 964, 968, 973, 976, 977, 986, 990, 994, 996, 1009, 1011, 1012, 1020, 1021, 1024}.
The sizes of the maximal independent sets in the components are as follows:
```
Component         MIS                   
1                   1                   
2                   3
3                   9
4                  21
5                  33
6                  37
7                  33
8                  21
9                   9
10                  3
11                  1

Total             171
```
The maximal independent sets for each component were shown to be optimal by formulating an integer program and then solving it with the help of the "MINTO" [MINTO] integer programming code. This is essentially what Patel did for 1dc.512, but here it was done separately on each connected component.

1et.2048.txt.gz, a 2048-node graph in which the size of a maximal independent set is 316.
November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) report that this graph contains an independent set of size 316.
May 15, 2005: Brian Borchers (see below) has obtained an upper bound of 328, as follows:
```
Component   Theta Bound   Best Known
1                     1        1 opt
2                     3        3 opt
3                    11       11 opt
4                    31       28 opt
5                    54       52 opt
6                    69       63
7                    69       63
8                    54       52 opt
9                    31       28 opt
10                   11       11 opt
11                    3        3 opt
12                    1        1 opt

Best known: 316
Best bound: 328
```
The smaller components were all handled by integer programming (or by his SDP-based branch and bound code), but the two largest components have not cracked yet.
Nov 04 2009: Brian Borchers reports that: I was finally able to resolve the large components of 1et.2048. The MIS for the two large components of this graph is of size 63, so the MIS for the entire graph is of size 316. This was done using the integer linear programming formulation of the problem and Gurobi 2.0, a recently released branch and cut code for integer programming that turned out to be extremely efficient for this problem.

The sizes of the maximal independent sets in this family of graphs form sequence A057657 in the OEIS. The size of the maximal independent set for length n and constant weight w is given in sequence A085685.

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

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

1zc.128.txt.gz, a 128-node graph in which it is known that the size of a maximal independent set is 18 (see references [Et91], [EO98], [We89], [WVB88]).

1zc.256.txt.gz, a 256-node graph in which it is known that the size of a maximal independent set is 36 (see references [Et91], [EO98], [We89], [WVB88]).

1zc.512.txt.gz, a 512-node graph in which it is known that the size of a maximal independent set is 62 (see references [Et91], [EO98], [We89], [WVB88]).

Most wanted! 1zc.1024.txt.gz, a 1024-node graph in which it is known only that the size of a maximal independent set is in the range 112 - 117 (see reference [EO98]).

1zc.2048.txt.gz, a 2048-node graph in which it is known only that the size of a maximal independent set is in the range 198 - 210 (see reference [EO98]).

1zc.4096.txt.gz, a 4096-node graph in which it was formerly known only that the size of a maximal independent set is in the range 336 - 410 (see reference [EO98]).
November 28, 2001: S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk (cf. [BPS03]) increased the lower bound to 379.

The sizes of the maximal independent sets in this family of graphs form sequence A010101 in the OEIS.

References

[BPS03] Sergiy Butenko, Panos Pardalos, Ivan Sergienko, Vladimir Shylo, and Petro Stetsyuk, Estimating the size of correcting codes using extremal graph problems, in Optimization, edited by Charles Pearce, pp. 227-243. Springer New York, 2009.

[MINTO] Coral, Lehigh University, MINTO: Mixed INTeger Optimizer

[Et91] T. Etzion, New lower bounds for asymmetric and unidirectional codes, IEEE Trans. Inform. Theory, 37 (1991), 1696-1705.

[EO98] T. Etzion and P. R. J. Ostergard, Greedy and heuristic algorithms for codes and colorings, IEEE Trans. Inform. Theory, 44 (1998), no. 1, 382-388 [Electronic version].

[NO03] Sampo Niskanen and Patric R. J. Ostergård, Cliquer User's Guide, Version 1.0, Communications Laboratory, Helsinki University of Technology, Espoo, Finland, Tech. Rep. T48, 2003.

[Sl89] N. J. A. Sloane, Unsolved Problems in graph theory arising from the study of codes, Graph Theory Notes of New York, 18 (1989), pp. 11-20.

[Sl00] N. J. A. Sloane, On single-deletion-correcting codes, arXiv:math.CO/0207197, in Codes and Designs, Ohio State University, May 2000 (Ray-Chaudhuri Festschrift), K. T. Arasu and A. Seress (editors), Walter de Gruyter, Berlin, 2002, pp. 273-291.

[We89] J. H. Weber, Bounds and Constructions for Binary Block Codes Correcting Asymmetric or Unidirectional Errors, Ph. D. Thesis, Tech. Univ. Delft, 1989.

[WVB88] J. H. Weber, C. de Vroedt and D. E. Boekee, Bounds and constructions for binary codes of length less than 24 and asymmetric distance less than 6, IEEE Trans. Inform. Theory, 34 (1988), 1321-1332.

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.