|May 21, 2013|
The Fields Undergraduate Network (FUN) includes a series of mathematical
talks aimed at undergraduates, and organized into a network involving
the local universities. We will be stating with trial run of four
events for next year with faculty members as consultants.
One statement of the pigeonhole principle is that any injective
function from a finite set to itself is surjective. This can also
be taken to be the definition of a set being finite, and thus, by
definition, infinite sets do not satisfy a pigeonhole principle.
However, if we restrict the allowable functions to ones which are
natural in some sense, then it is possible that some classes of
infinite sets will have a pigeonhole principle. In this talk, I
will make this idea precise. I will introduce the Grothendieck ring,
whose non-triviality is equivalent to the infinite pigeonhole principle,
and discuss various examples where the Grothendieck ring can be
calculated. In particular, I will show how model theory provides
us with very natural collections of sets and functions about which
it makes sense to ask for an infinite pigeonhole principle.
The representation theory of semisimple Lie groups is a classical subject going back to Weyl. I will describe the basics of this theory.
Then I will describe recent geometric approaches to this subject
and how they lead to categorical enhancement of representations.
Constraint satisfaction is a paradigm for specifying combinatorial problems in various areas of mathematics and computer science. One builds a constraint satisfaction instance by declaring a finite set of variables, a domain over which the variables are to be interpreted, and a finite collection of constraints which place restrictions on the values the variables may take in relation to the others. Given such a specification, one can ask whether a solution exists (i.e., an assignment of values to variables satisfying all the constraints). In general this sort of decision problem is NP-hard and hence presents a computational challenge to solve.
Many purely theoretical problems have arisen within the context of constraint satisfaction research, most famously the Dichotomy Conjecture which asserts that whenever the domain of a collection of instances are fixed to some finite set D and the allowable constraints are restricted to some finite set of relations on D, the does a solution exist question either remains NP-hard or becomes solvable in polynomial time. Spectacular advances towards a proof of the Dichotomy Conjecture have been achieved recently via the so-called algebraic approach. Under the algebraic approach one associates universal algebras, or collections of such algebras, to robust classes of restricted constraint satisfaction problems. It turns out that some well-studied properties of universal algebras perfectly capture the complexity of the corresponding problems. In my talk I will discuss the algebraic approach to the Dichotomy Conjecture, providing the necessary algebraic background along the way.