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. |
©2024 Vanderbilt University ·
Site Development: University Web Communications