Computational Combinatorics Roundup: March 2013

by Derrick Stolee

I was thinking that this month was lacking any new computational combinatorics papers, but then three papers arrived in my feed within a couple days of each other, followed by several others to finish out the month. Read on to learn about them, and as always send me an email whenever you see a relevant research article or news story.

Survey Paper

Alexander A. Razborov, Flag Algebras: an Interim Report.
Razborov gave one of four plenary talks at the Extremal Combinatorics at Illinois 2 Conference and as part of that presentation wrote this survey paper. The survey discusses briefly the context of the flag algebra technique and then gets into details of specific research results whose proofs use flag algebras. There is also a brief discussion on some solvers, including Flagmatic. Thanks to Michael Young for the link.

Research Papers

Martino Borello, Francesca Dalla Volta, Gabriele Nebe, The automorphism group of a self-dual [72,36,16] code does not contain S_3, A_4, or D_8, arXiv:1303.4899 [cs.IT].
Steven T Dougherty, Suat Karadeniz, Bahattin Yildiz , The automorphism group of the doubly-even [72,36,16] code can only be of order 1, 3 or 5, arXiv:1303.4920 [cs.IT].
While the two papers above have disjoint sets of authors, they discuss very similar topics. A [72,36,16] code is a 36-dimensional subspace of the 72-dimensional vector space over the finite field of order 2 where the minimum weight of a nonzero vector is 16. It is not known that such a space exists, but it would be interesting for certain sharpness conditions in coding theory. Two properties that could help discover such a code is to make it self-dual or doubly-even: all vectors have weight a multiple of four. A self-dual code with these parameters are always doubly-even, so the second paper proves a stronger result. The methods are very group-theoretic, using Magma as a main tool.

Shalosh B. Ekhad, Doron Zeilberger, “How To Generate As Many Somos-Like Miracles as You Wish,” arXiv:1301.5306 [math.CO].
Zeilberger and his computer companion work to automatically construct and prove that certain nonlinear recurrences form integer sequences (which may be very surprising). These are called Somos-like miracles because Michael Somos conjectured several such nonlinear recurrences, such as a(n) = \frac{a(n-1)\cdot a(n-3) + a(n-2)^2}{a(n-4)}. The method fits within the framework of the Wilf-Zeilberger method, which has not et been discussed on this blog.

Sarada Herke, Barbara Maenhaut, Perfect 1-Factorisations of Circulants with Small Degree, The Electronic Journal of Combinatorics 20(1), P58 (2013).
A 1-factor is a 1-regular spanning subgraph. Note that n must be even for any hope that one exists. A 1-factorization is a decomposition of a graph into 1-factors. A perfect 1-factorization is one where the union of every pair of 1-factors forms a Hamiltonian cycle. Such 1-factorizations are rare, but one place where they appear more frequently is in circulant graphs. The authors characterize the 3-regular circulant graphs with perfect 1-factorizations and use computer search to find which 4-regular circulant graphs of order at most 30 have perfect 1-factorizations. Also, see Ian Wanless’ progress on this conjecture.

Geoff rey Exoo, On Some Small Classical Ramsey Numbers, Electronic Journal of Combinatorics, 20(1), P68 (2013).
This paper improves lower bounds on two 2-color Ramsey numbers, specifically R(3,11) \geq 47 and R(4,8) \geq 58. Each case is an increase of 1 from previously known examples; this is the first improvement to lower bounds on R(3,11) in 46 years. The computational method is a randomized local search with some creative methods for getting away from local minima. By starting with previously-known lower bounds, these algorithms hit with success!

Janusz Dybizbanski, Tomasz Dzido, Stanisław Radziszowski, On Some Zarankiewicz Numbers and Bipartite Ramsey Numbers for Quadrilateral, arXiv:1303.5475 [math.CO].
This paper considers variants of Turán densities and Ramsey numbers, except for bipartite graphs. The Zarankiewicz number z(m,n;s,t) is the maximum number of edges in a subgraph of K_{m,n} that does not contain a copy of K_{s,t}. When m = n and s = t = 2, the authors use z(n) = z(n,n;2,2). (Since K_{2,2} \cong C_4, they refer to these as quadrilaterals.) A similar adaptation of Ramsey theory comes when coloring the edges of K_{n,n} to avoid a monochromatic copy of K_{s_i,s_i} for a list s_1, \dots, s_k. Let b(s_1,\dots,s_k) be the minimum n such that every k-coloring of E(K_{n,n}) contains an i-colored copy of K_{s_i,s_i} for some i\in [k]. When s_i = s, the number is written as b_k(s). The authors provide several upper bounds for z(n) and also some equalities. They then apply these to find bounds on the bipartite Ramsey numbers b_k(2). In particular, they compute b_4(2) = 19 by using their pure results as upper bound and finding a lower bound. (Previous papers computed b_2(2) = 5 and b_3(2) = 11.) They conjecture b_5(2) = 28 (and have an upper bound matching it), but the best lower bound is b_5(2) \geq 26.

Advertisements