Computational Combinatorics Roundup: November-December
by Derrick Stolee
We continue our monthly update of collecting research papers (or blog posts!) that were posted in the previous month+ (or were missed by previous lists). So far, I’ve just been watching the arXiv updates and my Google Scholar updates. Please comment or send me an email if you have an addition. (You can even tell me about papers when you see them, and I’ll add them to the next one!)
I’ve added my own short synopsis in italics based on a cursory glance through the papers. These are not reviews which verify their correctness or quality.
Aaronson’s post sparked a series of experimental/computational methods discussions on the TCS Stackexchange:
- Is “Experimental Complexity Theory” being used to solve open problems? (See Ryan Williams’ excellent answer about his own work. [The work he mentions would be fit for discussion on this blog. Anyone want to make a guest post?])
- A reading list on experimental algorithmics
- Are there applications of experimental mathematics in TCS?
G. Brinkmann, J. Goedgebeur, J. Schlage-Puchta, Ramsey Numbers for Graphs of Order 10, Electronic Journal of Combinatorics 19(4) P36 (2012).
The Ramsey number is the minimum such that every red/blue-edge-coloring of contains either a red triangle () or a blue copy of . The authors first generate all graphs of order 10. For each such , they generated all maximally triangle-free graphs with no copy of in the complement. Combined with some extremal bounds, their algorithm can verify all Ramsey numbers with value up to 30. Only 10 graphs remain where is unknown.
S. D. Stoichev, Experimental Results of the Search for Unitals in Projective Planes of Order 25. arXiv:1211.0596 [math.CO]
Uses a local search method to find unitals of known projective planes, where such unitals were not previously found.
H. Magnusson, H. Ulfarsson, Algorithms for discovering and proving theorems about permutation patterns. arXiv:1211.7110v1 [math.CO]
Automated methods for discovering and proving theorems about permutations.
N. Borie, Generating tuples of integers modulo the action of a permutation group and applications. arxiv:1211.6261 [math.CO]
The authors take a group acting on and extend that action to rearranging the coordinates of -tuples. Then, they generate orbits of -tuples of nonnegative integers modulo this group action. This problem is more general than graph generation, since adjacency matrices are simply a restricted form . The technique appears to report the lexicographic-maximum element of each orbit. The methods are currently available in Sage (Ticket #6812)
M. Bogaerts, P. Dukes, Semidefinite programming for permutation codes. arXiv:1212.1185 [math.CO]
The paper investigates objects called permutation codes which are very group-theoretic objects that I cannot say anything meaningful about (read the paper!). However, their analysis builds into Linear Programming and Semi-Definite Programming problems.
H. Fujita, A New Lower Bound for the Ramsey Number . arXiv:1212.1328 [cs.DM]
The improved lower bound was found by using a SAT solver on the standard CNF formula for a 2-edge-colored graph with no red and no blue . The solver finished because the author added the constraint to make the example a circulant graph. However, these constraints make the problem too strong, so the author relaxed a few of these restrictions based on partial solutions.
M. J. Dinneen, R. Versteegen, Obstructions for the Graphs of Vertex Cover Seven. CDMTCS Research Report Series.
A vertex cover is a set of vertices such that every edge has at least one endpoint in this set (the vertices cover the edges). The vertex cover number is the minimum size of a vertex cover. The family of graphs with vertex cover number at most is closed under edge-deletion (only reduces constraints of being a vertex cover) and edge-contraction (the contractions allow vertices to cover more edges). By Robertson and Seymour’s Graph Minor Theorem, there are a finite number of forbidden minors which characterize this family. The authors compute this list for and describe why the list is likely much larger for . The authors follow a method of Fellows and Langston to compute the finite list, which requires a few technical algorithms and bounds, including a bound on the treewidth (or pathwidth) of the graphs in the family. It is worth noting that many polynomial-time algorithms for bounded treewidth or minor-free families are actually galactic algorithms, so the fact that something is actually computable here is perhaps surprising.