|
Combinatorics/Algebra Seminar
Spring 2015 Archive:
-
April 13, 20
-
Jonathan Smith: Diagrammatic duality.
Abstract:
Establishing duality between algebras and representation spaces is an important task. It underpins such varied topics as Fourier transforms (either analytical or discrete), and the coordinatization of spaces in geometry. Following a brief general summary of duality, diagrammatic duality is presented as a method for obtaining new dualities founded on existing ones. Whenever algebras of a certain class are equivalent to diagrams in a category of known dualizable algebras, diagrammatic duality furnishes representation spaces for the algebras in the class by examining dual diagrams in the category of representation spaces for the known dualizable algebras.
-
March 23, 30
-
Alex Nowak: Tropical eigenvalue problems.
Abstract:
Tropical mathematics is an umbrella term, covering the study of max-plus and
min-plus algebras. In the former, we define addition to be the component-wise
maximum of elements, while in the latter, minimization defines our addition; multiplication is given by addition in the standard, or "classical," sense. Imposing this structure on R, we obtain the max-plus and min-plus semifields Rmax and Rmin.
In this talk, we focus on matrices with entries over the max-plus semifield, and
how their eigenvalues provide us with the means to construct discrete-event dynamic systems that behave predictably and stably. Existence theorems of tropical
eigenvalues, along with algorithms for their computation, will be discussed.
-
March 2
-
Alex Kazda (Charles University, Vanderbilt University): Constraint satisfaction problems solvable by Datalog.
Abstract:
The Constraint Satisfaction Problem (CSP) asks us to decide if there
is a mapping that satisfies a given list of constraints on its values (for example
"Is this Boolean formula satisfiable?" or "Can we color this graph by two colors?").
We will consider only CSPs with a finite set of possible values here, although infinite
valued CSPs are a worthy subject of study, too.
The general CSP is an NP-complete problem, but when we restrict the set of allowed
constraints to relations from a fixed relational structure, the problem can become
solvable in polynomial time, or even in logarithmic space. The study of the complexity
of such restricted CSPs is a place where computer science, logic, and universal algebra
meet, and the past decade has seen great progress towards classifying the complexity of
such restricted CSPs.
In this talk, we will give an overview of what is known about the class of CSPs that can
be efficiently solved by the Datalog programming language and its fragments, linear
and symmetric Datalog.
-
February 23
-
Jack Lutz: Circuits over sets of natural numbers.
Abstract:
This talk will introduce the McKenzie-Wagner model of circuits over sets of natural numbers and discuss some open problems concerning the model.
-
February 16
-
William DeMeo: Isotopic algebras.
Abstract:
Isotopy is an equivalence relation between algebras that
contains (is coarser than) the isomorphism relation and is important
for understanding direct products. Isomorphic algebras have isomorphic
congruence lattices and it is natural to ask whether a similar result
holds for isotopy. That is, do isotopic algebras have isomorphic (or
isotopic) congruence lattices? I will answer this question negatively
with an example involving finite group actions (G-sets), after giving
some background and motivation for studying isotopy.
-
February 9
-
Tonći Antunović (UCLA): Stochastic competition on finite and infinite networks.
Abstract:
The two-type Richardson model introduced in the 90's by Häggström and Pemantle is a stochastic competition model in which two types of particles spread through a graph using first passage percolation dynamics. While originally studied on the Euclidean lattice, recent attempts to model large real world networks (internet, social networks) raise natural questions about the behavior of the model on other kinds of graphs. We will present results about the behavior of the model on large random regular graphs and on a version of the model on lifts of general Cayley graphs. We will also present a related competition model on preferential attachment networks.
This is based on several papers written in collaboration with Yael Dekel, Elchanan Mossel, Yuval Peres, Eviatar Procaccia and Miklós Rácz.
Archive of earlier seminars
Back to the Mathematics Institute
Back to Main Street
|
|