Rocky Mountain Algebraic Combinatorics Seminar

Computing canonical forms of graphs: limitations of lexicographic methods

Takunari Miyazaki
Trinity College, Hartfort, CT

Determining the computational complexity of the problem of finding canonical representatives of graphs is a long-standing unresolved question. This question is of fundamental interest in the theory of computing because of its close relationship with graph-isomophism testing.

While the problem may be difficult in general, group-theoretic methods have enabled polynomial-time solutions for important classes of graphs, including graphs of bounded valence. In practice, however, variants of backtrack search to find lexicographic leaders have long been accepted as quite effective; for example, the system nauty is the leader in this category.
In this talk, I will discuss theoretical limitations of the lexicographic-leader approach to finding canonical forms. It turns out that this approach leads to NP-complete problems, even for very restricted classes of graphs for which there are simple polynomial-time solutions by group-theoretic methods.


Semifinite Generalized Quadrangles

Eric Moorhouse
University of Wyoming

A generalized quadrangle with k points per line (k finite), but infinitely many points and lines altogether, is called semifinite. The question of existence of such structures is a long-standing open question. The combined work of Kantor, Cameron and Brouwer ruled out the cases k=3,4; and the case k=5 was ruled out by Cherlin (2005) using model-theoretic techniques. I will outline Cherlin's argument and offer some variants of his approach. The hope (currently unrealized) is to extend this approach to k=6 or larger.


Weber 223
4–6 pm
Friday, October 10, 2014
(Refreshments in Weber 117, 3:30–4 pm)
Colorado State University

This is a joint Denver U / UC Boulder / UC Denver / U of Wyoming / CSU seminar that meets biweekly. Anyone interested is welcome to join us at a local restaurant for dinner after the talks.

PDF version

Previous Seminars:

September 26, 2014
Elissa Ross, Anton Betten
September 12, 2014
Petr Vojtěchovský, Alexander Hulpke
May 9, 2014
Philip DeOrsey, Tim Penttila
April 25, 2014
William J Martin, Jason Williford
April 11, 2014
Victor Pambuccian, George Shakan
March 7, 2014
Nathan Lindzey, Jens Harlander
February 21, 2014
Ross McConnell, Anton Betten
November 22, 2013
Justin Hughes, Josh Maglione

Department of Mathematics
Fort Collins, Colorado 80523