Universal Algebra and Logic

Fall 2008 Seminars

Time: Tuesday, December 9. (SC 1308, 4:30 – 5:30 p.m.)
Speaker: Justin Brody
Title: On Rational Limits of Shelah-Spencer Graphs
Abstract: For $\alpha$ irrational in $(0,1)$, the random graph $G(n, n^{- \alpha})$ is a finite probability space whose events are order $n$-graphs which occur with probability determined by 
declaring that any potential edge will occur with probability $n^{-\alpha}$. Work of Shelah, Spencer, and Baldwin has shown that the limiting behavior of these graphs as $n \to \infty$ is very tame. In particular there is a unique countable graph $G_\alpha$ which functions as a certain limit of these graphs. We will examine ultraproducts $\Prod_U G_{\alpha_n}$ for $\{\alpha_n \}$ an irrational sequence in $(0,1)$ converging to a rational.

Time: Tuesday, December 2. (SC 1308, 4:30 – 5:30 p.m.)
Speaker: Ralph McKenzie
Title: The complexity of constraint satisfaction problems: classifying the
complexity of CSP problems using finite algebras IV

Time: Tuesday, November 18. (SC 1308, 4:30 – 5:30 p.m.)
Speaker: Ralph McKenzie
Title: The complexity of constraint satisfaction problems: classifying the
complexity of CSP problems using finite algebras III

Time: Tuesday, November 11. (SC 1308, 4:30 – 5:30 p.m.)
Speaker: Ralph McKenzie
Title: The complexity of constraint satisfaction problems: classifying the
complexity of CSP problems using finite algebras II

Time: Tuesday, November 4. (SC 1308, 4:30 – 5:30 p.m.)
Speaker: Ralph McKenzie
Title: The complexity of constraint satisfaction problems: classifying the
complexity of CSP problems using finite algebras
Abstract: Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general (it includes graph three-coloring), but certain restrictions on the form of constraints can ensure tractability. Feder and Vardi (1998) conjectured that every “specific” instance of the CSP (such as graph three-coloring) is either tractable or NP-complete. Bulyatov and Jeavons (2002) showed that to every specific instance of CSP is correlated a finite algebra and that relative complexity of two CSP problems is directly tied to structural relations between the correlated algebras. They proposed general algebraic criteria for an instance of CSP to be tractable, or NP-complete. Thus they created an algebraic version of the dichotomy conjecture of Feder and Vardi, which is currently the focus of a lot of research. Remarkable progress has been made on the dichotomy conjecture during the past two years. Using a combination of universal-algebraic and graph-theoretic ideas, a team of young central european mathematicians has shown that for a finite algebra A for which no non-trivial Abelian congruences occur in the variety it generates, all CSP problems involving admissible relations over A are tractable. My talks will discuss in detail an easier proof of a result the team proved two months ago, on the way to the mentioned result: if a relational structure R has Jonsson terms among its polymorphisms, then the (2p, 3p)-consistency algorithm solves CSP(R) in polynomial time.

Time: Tuesday, October 28. (SC 1308, 4:30 – 5:30 p.m.)
Speaker: Constantine Tsinakis
Title: Universal Algebra for the Working Mathematician II.

Time: Tuesday, October 14. (SC 1308, 4:30 – 5:30 p.m.)
Speaker: Constantine Tsinakis
Title: Universal Algebra for the Working Mathematician.
Abstract: The title of the talk captures its aims. My intention is to provide an account of those fundamental results in the area that every well-educated research mathematician would find useful in his/ her research. One of the aims of universal algebra is to study features common to many familiar algebraic systems, such as groups, rings, lattices, etc. Such a study places a number of algebraic notions in their proper setting, reveals connections of seemingly unrelated concepts, and uses the higher level of abstraction to apply these results to entirely new situations. A central theme in this area is that of a variety or an equational class.

Time: Tuesday, October 7. (SC 1308, 4:30 – 5:30 p.m.)
Speaker: Petar Markovic, University of Novi Sad, Serbia
Title: An Idiot’s Guide to Complexity II.

Time: Tuesday, September 30. (SC 1308, 4:30 – 5:30 p.m.)
Speaker: Petar Markovic, University of Novi Sad, Serbia
Title: An Idiot’s Guide to Complexity I.
Abstract: I will attempt to give the basic concepts, ideas and results of the theory of computational complexity. The lecture is geared towards first-year graduate students and people who may have heard these notions before but never in a systematic way.

Time: Tuesday, September 23. (SC 1308, 4:30 – 5:30 p.m.)
Speaker: George Metcalfe, Vanderbilt University
Title: Proof Theory and Algebra I.
Abstract: Classes of algebraic structures, such as groups, lattices, Boolean algebras etc. are often presented using a list of identities (equations) that specify when an algebra belongs to the class. However, this presentation does not help much in testing whether a particular identity holds for all members of the class. In this talk, I will introduce alternative algorithmic or “proof-theoretic” presentations of classes of algebras, and explain some of the main results, applications, and challenges in the field.

Time: Tuesday, September 16. (SC 1308, 4:30 – 5:50 p.m.)
Speaker: Matthew Nickodemus, Vanderbilt University
Title: The Stone Duality Theorem.
Abstract: In 1936, Marshall Stone proved that every Boolean algebra is isomorphic to the algebra of all clopen subsets of some totally disconnected compact space. In this talk, I will prove Stone’s Theorem. My talk will be aimed at first year graduate students, and advanced undergraduates

Time: Tuesday, September 9. (SC 1308, 4:10 – 5:30 p.m.)
Title: Organizational Meeting.

Back Home   

Contact Information

Department of Mathematics
Vanderbilt University
Stevenson Center 1326
Nashville, TN 37240
U.S.A.

Phone: (615) 322-6672
Fax: (615) 343-0215