Discrete Math Seminar Spring 2011. Contact: Andrzej Cyzgrinow, Susanna Fishel, or Glenn Hurbert
Some Wednesdays, 2-3pm, PSA 103, unless otherwise indicated.
Wednesday, January 26.
Danny
Dyer, Memorial University of Newfoundland
Title: New metrics
for edge seaching
Abstract: Edge searching is graph game in
which a number of slow moving cops try to capture a fast, invisible
robber. The traditional metric for classifying searches is the search
number, the minimum number of searchers needed to capture the
robber. We will discuss some new metrics for measuring
searches.
Wednesday, February 9.
Susanna
Fishel, ASU
Title: Background material for Drew Armstrong's talk
Abstract: TBA
Friday, February 18, 10:30-11:30, PSA 113.
Drew Armstrong
University of Miami
Title: The Ish arrangement and diagonal harmonics
Abstract: I will define the Ish arrangement of hyperplanes. I will mention how
to combine this with the Shi arrangement to get a new interpretation
of the Hilbert series of diagonal harmonics. I will mention a
mysterious ``combinatorial symmetry'' between the Shi and Ish
arrangements. I will mention an open problem, suitable for
undergraduates.
Wednesday, March 23, 2:30, PSA 108.
No Discrete Math Seminar, go to the Number Theory Seminar.
Matthias Beck, San Francisco State University
Title: Integer partitions from a geometric viewpoint
Abstract: The study of partitions and compositions (i.e., ordered partitions) of
integers goes back centuries and has applications in various areas within
and outside of number theory. Partition analysis is full of beautiful--and
sometimes surprising--identities, starting with Euler's classic theorem that
the number of partitions of an integer k into odd parts equals the number of
partitions into distinct parts.
Motivated by work of G. Andrews et al from the last 1 1/2 decades, we will
show how one can shed light to certain classes of partition identities by
interpreting partitions as integer points in polyhedra. Our approach yields
both "short" proofs of known results and new theorems.
This is joint work with Ben Braun, Ira Gessel, Nguyen Le, Sunyoung Lee, and
Carla Savage.
Wednesday, March 30.
No Discrete Math Seminar.
Friday April 1, PSA 106, 10:30am.
.
Fatemeh
Mohammadi, MSRI
Title: Vertex cover ideals of
graphs
Abstract:We study the powers of vertex cover ideal of a
graph which is one of the natural ideals associated to every graph.
First we introduce a class of monomial ideals which enables us to
study the vertex cover ideals of graphs. Then as examples the
(powers) of vertex cover ideals of chordal and bipartite graphs will
be mentioned.
Wednesday, April 8, Room and time to be determined.
Vikram Kamat, ASU
Title: TBA
Abstract: TBA
Wednesday, April 27.
Sreyash D Kenkre, IBM India
Title: Using Cycle Lengths to Bound The Chromatic
Number
Abstract: Discovering bounds on the chromatic number by
using the lengths of cycles in the graph is an active area of research
in graph theory. We mention some open problems in this area and
present the following results. Let G be a graph with chromatic number
$\chi$, $\ell$ as the length of a longest odd cycle, and $\omega$ as
the size of a largest clique. Erdos and Hajnal showed that $\chi \leq
\ell+1$. Graphs with $\omega = \ell+1$ provide a tight example. We
prove better bounds for smaller values of $\omega$ as a function of $
\ell$. In particular, we prove that for certain ranges of $\omega$,
$\chi \leq \frac{\ell+ \omega}{2}$. Erdos conjectured that for
triangle free graphs, $\chi = O({\ell}^{0.5+ \epsilon})$. For a long
time, the best bound known was $\chi = O(\ell)$. We use a simple
trick, of combining DFS trees with online coloring, to improve this to
$\chi = O(\ell/\log\log\ell)$.
The speaker will also take a few minutes at the end to discuss IBM India.