The relationship between the genus of a graph and its chromatic number has
been studied extensively. This study culminated in the late 1960s with
the Ringle-Youngs Theorem, which states that the maximum chromatic number
of a graph embeddable in each surface S is precisely the size of the
largest clique embeddable in S. Similar results are known for thickness;
they say that the maximum chromatic number of a graph with thickness k is
at most 1 more than the size of the largest clique with thickness k. What
is surprising, then, is how little is known about the relationship between
chromatic number and crossing number. In 2007, Mike Albertson conjectured
that if graph G has chromatic number r, then G has crossing number at
least that of K_r. The case r = 5 is equivalent to the 4 Color Theorem
and the only other case verified until now was r = 6. Recently Albertson,
Jacob Fox, and I verified the conjecture for 7 < r < 12.
Date: April 1st, 2009
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Kellen Myers
Title:Van der Waerden's theorem
Abstract:In 1927, B.L. van der Waerden proved the theorem that
bears his name: for given integers r and k, there exists an N so that any
r-coloring of the integers 1 through N contains a monochromatic arithmetic
progression of length k. Proof of this theorem will be presented, as well
as an explanation of the sorts of bounds on N (w.r.t r and k) that are
known. I will also discuss, if time permits, generalizations and related
ideas, including the Hales-Jewett theorem and Szemeredi's theorem. If
there is any extra time, I will also present an
interesting new combinatorial proof of a famous conjecture of Fermat.
Date: March 25th, 2009
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Robert DeMarco
Title: Extremal Graph Theory
Abstract:This talk will be a quick overview of this large topic in
combinatorics. It will first review two of the famous theorems of Turan
and Dirac that not only are important on their own but helped give rise to
the field of extremal graph theory. The talk will then present a few more
recent theorems and questions in this field with more (or less) detail
depending on time. Yay!
Date: March 11th, 2009
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Thomas Robinson
Title: Umbral calculus
Abstract: I will derive (mostly) a formula for the higher
derivatives of a composite
function. Using that result, I will get some adjoint formulas from the
classical umbral calculus. I will also discuss the Riordan group which
arises in the classical umbral calculus and give a combinatorial
interpretation.
Date: March 4th, 2009
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Jay Williams
Title:Infinite trees, Konig's Lemma, and Aronszajn trees
Abstract:Everybody loves graphs and trees, even set theorists.
But, not content to
work with just finite trees, they have developed large bodies of work
regarding infinite trees. For instance, Konig's lemma states that an
infinite tree in which each level is finite has an infinite branch. We
will see an example of how this is useful. Then we'll discuss what it
means for a tree to have uncountable height and construct an Aronszajn
tree, an uncountable-height tree with some surprising properties. No set
theory will be assumed, so don't be afraid.
Date: February 25th, 2009
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Beth Kupin
Title: Concentration Inequalities and Tail Bounds
Abstract: Naively, we look at the expectation of a random
variable to get a sense
of what its value will be. Unfortunately, expectation doesn't always give
a good picture, and so when we need more acurate information one
possibility is to turn to more advanced methods to try to
determine how close a random variable is to its expected value. I'll
introduce a few of these "tail bound" inequalities (Markov, Azuma, and
Talagrand), and focus on examples that compare their various strengths and
weaknesses. No probability thoery required!
Date: February 18th, 2009
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Mike Neiman
Title:List Coloring Bipartite Graphs
Abstract: The list-coloring number of a graph is the minimum number
k su$
that for every assignment of a list of at least k colors to each vertex
there is a proper vertex coloring assigning to each vertex a color from
its list. I'll talk about bounds for the list-coloring numbers of
bipartite graphs, some of which are due to N. Alon. This will be an
expository talk, with emphasis on some probabilistic techniques and an
interesting open problem.
Date: February 11th, 2009
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Phil Matchett Wood
Title: On a Conjecture of Alon
Abstract: Let f(n,m) be the cardinality of largest subset of
{1,2,...,n} which does not contain a subset whose elements sum to m. I
would give
you some example values of f(n,m) that might lead you to conjecture an
asymptotic formula, but I just crashed Maple (last time I use the
graphical interface instead of the command line!), taking my tiny bit
of code with it.
In any case, in this talk, we will show that
f(n,m) = (1+o(1)) n / snd(m),
so long as
n(\log n)^(1+\epsilon) <= m <= n2/(9\log^2n) ,
which matches the hypothesis that f(n,m) is near n/snd(m). This
proves a conjecture of Alon posed in 1987 and demonstrates a
structural approach to a sumset problem.
Joint work with Linh Tran and Van Vu.
Date: Feb 4th, 2009
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Andrew Baxter
Title: An Introduction to Generating Functions, Part 2
Abstract: In the second part of the two-part primer on generating
functions, I will discuss exponential generating functions. Adding an
extra twist can allow for better results when counting labeled objects
like labeled trees. The two most general techniques are the Exponential
Theorem and the Lagrange Inversion Formula, which will be discussed at
length. If there is time, I will demonstrate further types of generating
functions such as doubly-exponential or Eulerian generating functions.
Date: January 28th, 2009
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Eric Rowland
Title: An Introduction to Generating Functions, Part 1
Abstract: The first installment in this acclaimed miniseries on
generating functions
introduces ordinary generating functions in one variable and some of their
uses and properties, including the relationships generating functions have
to closed formulas and recurrence equations. We'll see some basic and
not-so-basic generating functions, and using them I'll give an outline of
the generatingfunctionansatzcomplexityhierarchaeology. I'll also talk
about the important role of generating functions in obtaining information
about the asymptotic growth rate of sequences.
Fall 2008
Date: December 3rd, 2008
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Beth Kupin
Title: Szemeredi's Regularity Lemma
Abstract: It's often hard to find true independence and/or true
randomness
arising naturally in a problem. To get around this, we cheat a bit; the
Regularity Lemma proves the existence of a decomposition of a large, dense
graph into smaller pieces, in which the edges between pieces are evenly
distributed (i.e., regular). This means that the edges between these
pieces will (more or less) behave as if they were randomly distributed,
even though there was nothing random about the choice of the initial
graph!
I will talk a little bit about the proof of the lemma, but much more about
how it is used to prove other results, such as the Erdos-Stone Theorem, or
Roth's Theorem about 3-term arithmetic progressions. This will be an
introductory talk, so no previous knowledge about extremal graph theory
will be assumed.
Date: November 12th, 2008
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Phil Matchett-Wood
Title: 3-term Arithmetic Progressions in sufficiently dense sets,
and
the Erdos-Heilbronn Conjecture.
Abstract: This talk will discuss the maximum density of a subset
A
of {1,2,3,...n} such that A contains no 3-term arithmetic
progression. The first result in this vein was due to Roth in 1953,
with subsequent improvements by Heath-Brown in 1987, by Szemeredi in
1990, and by Bourgain in 1999 and 2008. The talk will also discuss a
recent application of the density bound on sets containing no 3-term
arithmetic progression to the Erdos-Heilbronn Conjecture.
Date: November 12th, 2008
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Paul Raff
Title: Combinatorial Codes and Avoiding Difference Sets
Abstract: In 1980, Perrin and Schutzenberger gave the so-called
Triangle Conjecture on codes, but a counterexample was given by Peter
Shor in 1984 and the Triangle Conjecture has been ignored since then.
However, there is still a lot of information that is still unknown
related to the conjecture, and Shor's counterexample provides
motivation for finding large sets whose differences are not part of
some prescribed set D. In this talk, I will define the codes, go over
the Triangle Conjecture and its counterexample, give results
pertaining to avoiding prescribed differences, and talk briefly about
future potential work related to Szemeredi-type theorems on arithmetic
progressions.
This talk is self-contained, and all are encouraged to attend.
Date: November 5th, 2008
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Mike Neiman
Title: Correlation Inequalities
Abstract: Correlation inequalities examine how probabilistic events
positively or negatively reinforce each other. I will give an introduction
to some correlation inequalities and applications to random graph models,
in particular percolation and the more general random-cluster model.
Since this is an introductory talk, I will assume very little previous
knowledge.
Date: October 29th, 2008
Time: 12:00 PM
Place: Graduate
Student Lounge, 7th Floor, Hill Center
Speaker: Emilie Hogan
Title:The Laurent Phenomenon for Non-Linear Recurrences
Abstract:
Non-linear recurrence relations that produce infinite sequences of
integers are very
surprising. Often this can be explained by the Laurent Phenomenon, when a
non-linear
recurrence of order k produces a sequence of Laurent polynomials in the
first k terms.
Some well known examples of this phenomenon are the Somos-k sequences.
Somos-4 is
defined by the
recurrence:s(n)*s(n-4)=s(n-1)*s(n-3)+s(n-2)2When the first
4 terms are defined to be x1, x2, x3,
x4
every term in the sequence is a Laurent polynomial in these 4 variables. I
will give
sufficient conditions for a non-linear recurrence to follow the Laurent
Phenomenon, and
show how the Somos-4 sequence satisfies these conditions. This talk will
be based on
the paper by Sergey Fomin and Andrei Zelevinsky, "The Laurent Phenomenon".
Date: October 22th, 2008
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Brian Thompson
Title: The Zarankiewicz Problem and Other X-tremal "Sports"
Abstract: Wikipedia defines extreme sports as "activities perceived as having a high level of inherent danger." To protect ourselves against this threat of danger, we will first be equipped with some heavy-duty tools such as the Lov‡sz Local Lemma.
Throughout the talk, we will be examining several problems in extremal graph theory; more specifically, we will focus on questions of the form, "What is the largest graph G that avoids H as a subgraph?" For those of you with a competitive spirit, we will see how to extend these into multi-player games of strategy and insight. And for the more introverted types, I will also present some games of "graph theory solitaire".
Date: October 15th, 2008
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Kellen Myers
Title: Ramsey Theory on the Integers & Rado Numbers
Abstract: Ramsey theory is the study of the structure within a set, and whether such structure is preserved under (finite) partitions (thought of as "colorings"). A coloring with r colors is called an r-coloring. A
structure preserved under colorings is called regular (or r-regular for
only r-colorings). In any such problem, we can also ask what the minimal
such n is (for fixed r and m), a question that is often bounded
theoretically and/or computed via computer. Schur's theorem tells us that
solutions to the equation x+y=z are regular. In this talk, we will
consider the generalization of Schur's theorem to linear equations, done
by Richard Rado, and other results (both "existence" and
bounding/computational) pertaining to linear equations - of which some
solution sets are regular and some are only 2-regular.
Date: October 8th, 2008
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Jeffrey Amos
Title: The Multi-dimensional Chicken McNugget problem
Abstract: Millions of American have no doubt asked themselves this
question: if I can only buy multiples of 6, 9, and 20 chicken
McNuggets, what is that largest number of McNuggets that I can't buy?
Mathematicians with a precise grasp on their level of hunger have
pondered this riddle for over a century Ð even since before
McDonald's. I will be considering a generalization of this problem.
Given a set of integer vectors, what is the largest vector that cannot
be written as a sum of a sequence of the given vectors? I will be
presenting results concerning what "largest vector" should mean, when
it exists, and several 1-dimensional results that generalize into
n-dimensions.
Date: October 1st, 2008
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Eric Rowland
Title: Pattern Avoidance in Binary Trees
Abstract: Let T and t be binary trees. We say that T avoids the pattern t if T does not contain t as a (contiguous) subtree. A natural thing to do with a notion of 'pattern' is, of course, to count the objects (in this case n-leaf binary trees) that avoid a given pattern. We'll start by working out for small tree patterns the generating function that answers this question. Then we will consider the analogue of Wilf equivalence: Two tree patterns are equivalent if the trees that avoid them areequinumerous, i.e., they have the same generating function. It is not
straightforward to understand these equivalence classes. However, I'll
describe a method of restructuring trees that often lets us prove
(bijectively) the equivalence of two equivalent tree patterns.
Date: September 24th, 2008
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Andrew Baxter
Title: Generalized Permutation Patterns and Mahonian Statistics
Abstract: In their 2000 article, Babson and Steingrimsson introduce the
concept of the generalized permutation pattern. These are meant to serve
as atomic permutation statistics which can be combined to form more
interesting permutation statistics such the major index MAJ or the number
of inversions INV. In this talk I will introduce these generalized
patterns (although Arvind metioned one in his talk) and how Babson and
Steingrimsson used them to find previously-unknown Mahonian statistics,
that is those statistics which have the same distribution over the
symmetric group as INV. I will then discuss my own research in tying up
some loose ends which Babson and Steingrimsson left behind.
Date: September 17th, 2008
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Dan Cranston
Title: Injective Coloring of Sparse Graphs
Abstract: An injective coloring is a vertex coloring such that every two vertices with a common neighbor receive distinct colors; it need not be a proper coloring. The injective chromatic number of G, denoted χi(G), is the least k such that G has an injective coloring with k colors. The discharging method is a bookkeeping technique for induction proofs on graphs. Specifically, we use discharging when we have a variety of different induction steps possible, no single one of which is always applicaple; the key is to prove that in all cases one of the induction steps is applicable.
The goal of this talk is to introduce the discharging method, and we do so by proving two theorems about Injective Coloring. Let mad(G) denote the maximum average degree (over all subgraphs) of G. We prove that if the maximum degree is 3 and mad(G) < 5/2, then χi(G) ≤ 4. Similary, if the maximum degree is 3 and mad(G) < 36/13, then χi(G) ≤ 5.
No background is assumed. This talk should be accessible to all grad students (even CS people ;).
Date: September 10th, 2008
Time: 12:00 PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Speaker: Arvind Ayyer
Title: Exclusion Processes: A Meeting Point for Probabilists, Combinatorialists and Statistical Mechanicians
Abstract: An exclusion process is a Markov process defined on the integer lattice, or its subset, in which each site is either occupied by a particle or is empty. Motivated by statistical mechanical considerations, Derrida et al. considered a particular finite model and gave a formula for its steady state probability distribution using the so-called "matrix product ansatz". Taking this as the starting point, I will go through the literature and survey some interesting models studied by the three groups and end by describing an exclusion process with two kinds of particles which is joint work with Joel Lebowitz and Eugene Speer.