Computational Combinatorics Reference List

by Derrick Stolee

There are a lot of things I want to discuss on this blog. So many, in fact, that I struggle to pick which topic to write about next. I have compiled a list of papers and user guides that are possible topics for later blog posts. This should give you an idea of what topics I want on the blog and also some reading material if you don’t want to wait for me to get there. Also, if you want to write a guest post discussing these or similar papers (or simply want to add a paper to the list), please send me an email! I promise a regular post next week.

I have grouped some of the papers by technique.

Canonical Deletion

We have already discussed an introduction to canonical deletion, but there are many uses of the technique that are worthy of discussion.

G. Brinkmann, J. Goedgebeur, B. D. McKay. Generation of Cubic graphs. Discrete Mathematics and Theoretical Computer Science, 13:2, 2011.

G. Brinkmann, J. Goedgebeur, B. D. McKay. The Generation of Fullerenes, preprint.

G. Brinkmann, B. D. McKay, C. Saager, The Smallest Cubic Graphs of Girth Nine, Combinatorics, Probability, and Computing, 4:4, pages 317-329, 1995.

B. D. McKay. Small graphs are reconstructible. Australasian Journal of Combinatorics, 15:123-126, 1997.

D. Stolee, Generating p-extremal graphs, 2011.

nauty

The canonical labeling algorithm is very important to the procedure for canonical deletion. It may be helpful to discuss how it works and how one can exploit it to efficiently perform automorphism group and orbit calculations.

S. G. Hartke and A. Radcliffe. McKay’s canonical graph labeling algorithm. In Communicating Mathematics, volume 479 of Contemporary Mathematics, pages 99-111. American Mathematical Society, 2009.

B. D. McKay. Practical Graph Isomorphism, Congressus Numerantium, 30:45-87, 1981.

B. D. McKay. nauty user’s guide (version 2.4). Dept. Computer Science, Austral. Nat. Univ., 2006.

Orbital Branching

Orbital branching is a relatively new technique, originally designed to solve integer linear programs with symmetric constraints. This was further generalized to constraint systems. In the last paper, it was specifically used to generate combinatorial objects.

J. Ostrowski, J. Linderoth, F. Rossi, and S. Smriglio. Orbital branching. In IPCO ’07: Proceedings of the 12th international conference on Integer Programming and Combinatorial Optimization, volume 4513 of LNCS, pages 104-118, Berlin, Heidelberg, 2007. Springer-Verlag.

J. Ostrowski, J. Linderoth, F. Rossi, and S. Smriglio. Constraint orbital branching. In A. Lodi, A. Panconesi, and G. Rinaldi, editors, Integer Programming and Combinatorial Optimization, 13th International Conference, IPCO 2008, Bertinoro, Italy, May 26-28, 2008, Proceedings, volume 5035 of Lecture Notes in Computer Science. Springer, 2008.

J. Ostrowski, J. Linderoth, F. Rossi, and S. Smriglio. Solving large Steiner triple covering problems. Technical Reports of the Computer Sciences Department, University of Wisconsin-Madison, (1663), 2009.

S. Hartke, D. Stolee, Uniquely K_r-Saturated Graphs, preprint.

Flag Algebras

Razborov’s flag algebra technique has seen an explosion in computational results in recent years. Several problems that have avoided improvement over previous decades are now receiving significant progress. This section in particular needs several additions.

A. A. Razborov, Flag Algebras. Journal of Symbolic Logic, 72:4, 1239-1282, 2007.

R. Baber, J. Talbot, Hypergraphs do jump, 2010.

J. Balogh, P. Hu, B. Lidický, H. Liu, Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube, preprint.

J. Cummings, D. Kral, F. Pfender, K. Sperfeld, A. Treglown, M. Young, Monochromatic Triangles in Three-Colored Graphs, preprint.

Other Methods

Many other computational approaches have been used with varying degrees of generality. At some point, categorization is meaningless and we need such an “other” category. However, some of these techniques are very successful for their given problems. The question is: can they be generalized for other problems? I hope so and look forward to investigating them further. Also, I have not read the majority of these papers other than to see that they do use computation of some sort but not enough to know if they fit in a category above.

K. Coolsaet, J. Degraer, and E. Spence. The strongly regular (45, 12, 3, 3) graphs. The Electronic Journal of Combinatorics, 13(R32):1, 2006.

S. G. Hartke, J. Vandenbussche, On a question of Sós about 3-uniform friendship hypergraphs, Journal of Combinatorial Designs, 16:3, 253-261, 2008.

A. Jobson, A. Kézdy, H. Snevily, and S. C. White. Ramsey functions for quasi-progressions with large diameter, Journal of Combinatorics, 2:4, 557-573, 2011.

P. Kaski, P. R. J. Östergård. The steiner triple systems of order 19. Mathematics of Computation, 73(248):2075-2092, 2004.

M. Kouril, J. Paul. The van der Waerden number W(2, 6) is 1132. Experimental Mathematics, 17(1):53-61, 2008.

C. Lam, L. Thiel, and S. Swiercz. The non-existence of finite projective planes of order 10. Canadian Journal of Mathematics, 41(6):1117-1123, 1989.

B. D. McKay and E. Spence. Classification of regular two-graphs on 36 and 38 vertices. Australasian Journal of Combinatorics, 24:293-300, 2001.

S. Niskanen and P. R. J. Östergård. Cliquer user’s guide, version 1.0. Technical Report, T48, 2003.

P. R. J. Östergård, A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120, 2002, Pages 197–207.

E. Spence. The strongly regular (40, 12, 2, 4) graphs. The Electronic Journal of Combinatorics, 7:R22, 2000.

Call for Suggestions

This list is far from complete. Please suggest your favorite papers with your favorite applications or techniques.

Please also send me an email (stolee at illinois dot edu) if you would like to write a blog post about any of the above papers or some of your own work.

Advertisements