MathematicsSeminar 
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 longstanding unresolved question. This question is of fundamental interest in the theory of computing because of its close relationship with graphisomophism testing.
While the problem may be difficult in general, grouptheoretic methods have enabled polynomialtime 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 lexicographicleader approach to finding canonical forms. It turns out that this approach leads to NPcomplete problems, even for very restricted classes of graphs for which there are simple polynomialtime solutions by grouptheoretic 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 longstanding 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 modeltheoretic 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:

