4-ICC Invited Talks

About 4-ICC

The 4ICC was held at the University of Auckland in Auckland, New Zealand 15-19 December 2008. The ICC is held approximately every 10 years, and when held it includes the annual ACCMCC meeting of the Combinatorial Mathematics Society of Australasia and the annual graph-theoretical meetings held in Slovenia/Slovakia/New Zealand/Arizona-Portugal.

List of invited talks

Alexander Barvinok, University of Michigan

Talk title

"On the number of non-negative integer and 0-1 matrices with prescribed row and column sums"

Talk abstract

I plan to survey recent results on the enumeration of non-negative integer matrices with prescribed row and column sums (also known as contingency tables) and of 0-1 matrices with prescribed row and column sums (also known as binary contingency tables). The results point at some interesting phenomena of probabilistic “attraction” and “repulsion” in the space of matrices as well as allow us to describe what a random non-negative integer or 0-1 matrix with prescribed row and column sums looks like.

Video

{{#ev:googlevideo|1452039458797799200|500}}

---

Peter Cameron, Queen Mary College London

Talk title

"Synchronization and permutation groups"

Talk abstract

A (finite-state, deterministic) automaton can be regarded combinatorially as an edge-coloured directed graph with a unique edge of each colour leaving each vertex; algebraically, as a subsemigroup of the transformation semigroup on a set with a prescribed set of generators. An automaton is synchronizing if there is a word in the generators (a sequence of colours) which brings you to the same state no matter where you start; such a word is called a reset word. The Cerny conjecture asserts that an n-state synchronizing automaton has a reset word of length at most (n-1)² if true, this would be best possible. In a new approach to the Cerny conjecture, Araujo and Steinberg have suggested studying permutation groups G on Ω with the property that, given any map f on Ω which is not a permutation, the semigroup generated by G and f is synchronizing. They call such groups synchronizing. A synchronizing group is primitive. The problem of deciding which permutation groups are synchronizing includes many substantial results and diffcult open problems from combinatorics and finite geometry, including Baranyai’s theorem, large sets of Steiner triple systems, and ovoiods and spreads of classical polar spaces. Some of these issues will be described in the talk. There are several properties of permutation groups stronger than synchronization, which are also connected with the Cerny problem; some of these will also be mentioned.

This is joint work with a number of authors, including Joao Araujo, Peter Neumann, Jan Saxl, Csaba Schneider, Pablo Spiga, and Ben Steinberg.

Video

{{#ev:googlevideo|6032994074418737591|500}}

---

Maria Chudnovsky, Columbia University

Talk title

"Packing seagulls in graphs with no stable set of size three"

Talk abstract

Hadwiger’s conjecture implies that if G has no three-vertex stable set, then G contains K_t as a minor where t = [math]\lceil[/math]|V(G)|/2[math]\rceil[/math]. This remains open, but Jonah Blasiak proved it in the subcase when |V(G)| is even and the vertex set of G is the union of three cliques. Here we prove a strengthening of Blasiak’s result: that the conjecture holds if some clique in G contains at least |V(G)|/3 vertices.

This is a consequence of a result about packing “seagulls”. A seagull in G is an induced three-vertex path. It is not known in general how to decide in polynomial time whether a 3 graph contains k pairwise disjoint seagulls; but we answer this for graphs with no three-vertex stable set and with at least 4k-2 vertices. At the moment we are working to remove the last hypothesis.

This is joint work with Paul Seymour.

Video

{{#ev:googlevideo|-1924530321039943278|500}}

---

Jan de Gier, University of Melbourne

Talk title

"Punctured plane partitions, restricted fully packed loops and the qKZ equation"

Talk abstract

Fully packed loop (FPL) diagrams are another way of writing alternating sign matrices. We describe a class of p-restricted vertically symmetric FPL diagrams which we conjecture to be equinumerous with cyclically symmetric transpose complement plane partitions with a hole of size p. This conjecture arises as a consequence of the Razumov-Stroganov conjecture, which links particular polynomial solutions of the q-Knizhnik-Zamolodchikov equation to (p-restricted) FPL diagrams. In the case of p = 0 we are able to extend our results to weighted enumerations, and furthermore show a connection to the discrete Boussinesq and Hirota equation, or octagon recurrence.

Video

{{#ev:googlevideo|5980072549669702624|500}}

---

Jesús de Loera, University of California-Davis

Talk title

"When combinatorial computing meets algebraic computing: Hilbert's nullstellensatz and feasibility of combinatorial problems"

Talk abstract

Systems of multivariate polynomial equations can be used to model the combinatorial problems. In this way, a problem is feasible (e.g. a graph is 3-colorable, Hamiltonian, etc) if and only if a certain system of polynomial equations has a solution over an algebraically closed field. Such modeling has being used to prove non-trivial combinatorial results via polynomials (e.g. work by Alon, Tarsi, Karolyi, etc). More recently, in the work of E. de Klerk, M. Laurent, J. Lasserre, P. Parrilo, Y.Nesterov, and others, optimization problems were modeled by a zero dimensional radical ideal and were shown to have a finite sequence of semidefinite programs that converge to the optimal solution. Thus the polynomial method is not just for proving theorems but a rather exciting method to compute with combinatorial objects. In this talk we introduce the audience to this idea.

We show that for combinatorial feasibility problems (e.g., deciding if G is Hamiltonian?) the Hilbert Nullstellensatz gives a sequence of linear algebra problems, over an algebraically closed field, that eventually decides feasibility. In this talk I present both theoretical and experimental results about these sequences of linear algebra relaxations to feasibility questions in combinatorial optimization:

1. First we show that the size of the smallest Nullstellensatz linear algebra system, certifying that there is no stable set of size larger than the stability number of the graph, grows as fast as the stability number of the graph.
2. We implemented these algorithm and the corresponding large-scale linear-algebra computations over K. We report on experiments for the problem of proving the non-3-colorability of graphs. We successfully solved graph problem instances having thousands of nodes and tens of thousands of edges.

This talk is based on papers joint work with several people (J. Lee, P. Malkin, S. Margulies, and S. Onn).

Video

{{#ev:googlevideo|-656026300856053943|500}}

---

Cheryl Praeger, University of Western Australia

Talk title

"The normal quotient philosophy for edge-transitive graphs"

Talk abstract

Studying normal quotients has proved an effective way to describe the structure of many families of finite edge-transitive graphs. The normal quotient approach was initiated in my investigation of s-arc transitive graphs, and then refined in collaboration with Giudici and Li to develop our theory of locally s-arc transitive graphs. I will attempt to present the essence of this philosophy - hopefully with reference to a new analysis of an infinite family of edge-transitive graphs.

Video

{{#ev:googlevideo|2243505954692995048|500}}

---

Chris Rodger, Auburn University

Talk title

"Cycle systems with two associate classes"

Talk abstract

A k-cycle system of a graph G is a partition of the edges of G, each element of which induces a cycle of length k. A k-cycle system with 2 associate classes is a k-cycle system of a graph with a partition P of the vertices in which two vertices are joined by λ₁ or λ₂ edges iff the vertices are in the same element or in different elements of P respectively.

Results on the existence of k-cycle systems with 2 associate classes will be presented in this talk in the extreme cases where the cycles are hamiltonian, or have length 3 or 4. Resolvability of such decompositions will also be addressed, where the cycles themselves are partitioned into sets, each element of which forms a 2-factor. A new result on amalgamations of graphs (graph homomorphisms) will be used to address the hamiltonian case.

Video

{{#ev:googlevideo|3511714973004364310|500}}

---

Paul Seymour, Princeton University

Talk title

"Well-quasi-ordering tournaments and Rao's degree-sequence conjecture"

Talk abstract

(joint with Maria Chudnovsky, Columbia)

Rao conjectured about 1980 that in every infinite set of degree sequences (of graphs), there are two degree sequences with graphs one of which is an induced subgraph of the other. We recently found a proof, and we sketch the main ideas.

The problem turns out to be related to ordering digraphs by immersion (vertices are mapped to vertices, and edges to edge-disjoint directed paths). Immersion is not a well-quasi-order for the set of all digraphs, but for certain restricted sets (for instance, the set of tournaments) we prove it is a well-quasi-order.

The connection between Rao’s conjecture and tournament immersion is as follows. One key lemma reduces Rao’s conjecture to proving the same assertion for degree sequences of split graphs (a split graph is a graph whose vertex set is the union of a clique and a stable set); and to handle split graphs it helps to encode the split graph as a directed complete bipartite graph, and to replace Rao’s containment relation with immersion.

Video

{{#ev:googlevideo|-7949380536411412871|500}}

---

Mike Steel, University of Canterbury

Talk title

"Is testing a tree easier than finding it?"

Talk abstract

This purely mathematical question arises from evolutionary molecular biology. We have a sequence of discrete states that have evolved independently on some unknown tree by a simple markov process, and we wish to reconstruct the underlying leaf-labeled tree. How long do the sequences need to be so that our estimate is correct with high probability? And in particular, how fast does the sequence length need to grow as a function of number n of vertices of the tree? We contrast this “reconstruction” question with a corresponding “testing question”: Is the required rate of sequence length growth with n lower if we are given a candidate tree and wish to merely “test” it by asking: Is this the tree that produced the sequences? How about if we are given two trees along with the promise that one of the two trees produced the sequences - can we “tease” out the true tree with even shorter sequences? Using arguments based on combinatorics and discrete probability we find the answers to these questions can sometimes be surprising, depending on the properties of the markov process.

Video

{{#ev:googlevideo|-2884218421081679897|500}}

---

Nick Wormald, University of Waterloo

Talk title

"The chromatic number of random graphs"

Talk abstract

A number of landmark results have been obtained in the past 20 years on the chromatic number of random graphs, beginning with the Shamir-Spencer result on its concentration. Other sharp concentration type results have been obtained quite recently, using a variety of methods. A very recent one is that the chromatic number of a random d-regular graph is almost determined for many values of d. This is joint work with Graeme Kemkes and Xavier Perez.

Video

{{#ev:googlevideo|-6846825444888908620|500}}

---

Doron Zeilberger, Rutgers University

Talk title

"Guesseling"

Talk abstract

How does one prove an intriguing and beautiful explicit formula, guessed by Ira Gessel, that a certain set of lattice paths is enumerated by a certain beautiful formula?

“One” GUESSES a much uglier “formula” for a much more general set of lattice paths, then “one” proves it by induction, and then, for the original special case guessed by Ira Gessel, “one” gets an ugly duckling of a “formula” for the original Gessel guess, and finally “one” proves that the ugly “formula” for the special case, is equivalent to the original beautiful swan of Ira Gessel.

Sounds ugly? Well, maybe, but “one” does not mind, since “one” is a computer. But teaching “one” how to perfrom all the steps all by itself, is beautiful, if I do say so myself.

(Joint work with Manuel Kauers, Christoph Kauers, and a “one”).

Video

{{#ev:googlevideo|2750774243251929170|500}}

---