Feedback
Seminars
Upcoming Seminars:
Select which seminar you are interested in:
- CSC Seminar
- Discrete Math Seminar
- Number Theory Seminar
- Operations Research Seminar
- Seminar on Teaching Mathematics
- Global Warming Spring 2011 Seminar Series: A Science Perspective
Discrete Math Seminars
Discrete Math seminar: Andrew Poelstra
Tuesday, May 28 - 2:30pm to 3:30pm
Title: RamseyScript and Double Arithmetic Progressions
Abstract: Ramsey Theory is the study of very persistent structures: structures which
are monochromatic under any finite coloring of some set. For example, every
finite coloring of the naturals contains monochromatic solutions to the
equation x + y = z. Equivalently, there is a least integer N(r) such that
every r-coloring of {1, 2, ..., N(r)} has a monochromatic solution. There
are no good bounds for N(r) and exact values are only known for small r
through computational search.
We introduce the program RamseyScript, which does computational searches
for this and similar problems for integer colorings, sequences, words on
finite alphabets and permutations. It is operated through a simple script
language and obviates much single-purpose code.
We also discuss an open Ramsey problem: does every finite coloring of the
natural numbers contain double arithmetic progressions? We discuss the
history of the problem and present evidence toward a solution gathered
through RamseyScript.
Abstract: Ramsey Theory is the study of very persistent structures: structures which
are monochromatic under any finite coloring of some set. For example, every
finite coloring of the naturals contains monochromatic solutions to the
equation x + y = z. Equivalently, there is a least integer N(r) such that
every r-coloring of {1, 2, ..., N(r)} has a monochromatic solution. There
are no good bounds for N(r) and exact values are only known for small r
through computational search.
We introduce the program RamseyScript, which does computational searches
for this and similar problems for integer colorings, sequences, words on
finite alphabets and permutations. It is operated through a simple script
language and obviates much single-purpose code.
We also discuss an open Ramsey problem: does every finite coloring of the
natural numbers contain double arithmetic progressions? We discuss the
history of the problem and present evidence toward a solution gathered
through RamseyScript.
Discrete Math seminar: Brian Alspach
Thursday, Jun 6 - 2:30pm to 3:30pm
Title: The Coxeter Group Project: A Progress Report
Abstract: If one forms a Cayley graph on the symmetric group using only transpositions
for the connection set, then the graph is bipartite. In 2006, Araki proved that if such a
Cayley graph is connected, then for any two vertices u and v in different parts, there is
a Hamilton path whose terminal vertices are u and v. Of course, the symmetric group is
a Coxeter group. The speaker has embarked on a project of extending Araki's Theorem
to Cayley graphs on other families of Coxeter groups. This talks is a summary of what
has been achieved so far.
Abstract: If one forms a Cayley graph on the symmetric group using only transpositions
for the connection set, then the graph is bipartite. In 2006, Araki proved that if such a
Cayley graph is connected, then for any two vertices u and v in different parts, there is
a Hamilton path whose terminal vertices are u and v. Of course, the symmetric group is
a Coxeter group. The speaker has embarked on a project of extending Araki's Theorem
to Cayley graphs on other families of Coxeter groups. This talks is a summary of what
has been achieved so far.
Discrete Math seminar: Robert Samal
Tuesday, Jun 18 - 2:30pm to 3:30pm
Discrete Math seminar: Jessica McDonald
Tuesday, Jun 25 - 2:30pm to 3:30pm
Title: Packing Steiner Trees.
Abstract:
A classic theorem dueto Nash-Williams and Tutte implies that a graph G contains k pairwise edge-disjoint spanning trees provided it is 2k-edge-connected. Kriesell has conjectured a generalization of this result for Steiner trees. Given a set of T distinguished vertices in a graph G, a T-Steiner tree is a subgraph of G that is a tree and that spans T. Kriesell's Conjecture is that a connected graph G should contain k edge-disjoint T-Steiner trees provided that every edge-cut of G that separates T has size at least 2k. In this talk we show that Kriesell's Conjecture holds when 2k is replaced by 5k+4.
Joint work with Matt DeVos and Irene Pivotto.
Abstract:
A classic theorem dueto Nash-Williams and Tutte implies that a graph G contains k pairwise edge-disjoint spanning trees provided it is 2k-edge-connected. Kriesell has conjectured a generalization of this result for Steiner trees. Given a set of T distinguished vertices in a graph G, a T-Steiner tree is a subgraph of G that is a tree and that spans T. Kriesell's Conjecture is that a connected graph G should contain k edge-disjoint T-Steiner trees provided that every edge-cut of G that separates T has size at least 2k. In this talk we show that Kriesell's Conjecture holds when 2k is replaced by 5k+4.
Joint work with Matt DeVos and Irene Pivotto.
Discrete Math seminar: Manuel Kauers
Tuesday, Jul 23 - 2:30pm to 3:30pm