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 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:
|
|
