The graduate student combinatorics seminar is organized by graduate students in the math, computer science, and operations research departments. Students (and perhaps other invited speakers) speak about topics in combinatorics that are of interest to the group as a whole. The talks are to be understandable to everyone present and last less than an hour.
The seminar usually meets Mondays at 1:10pm in the Graduate Student Lounge on the 7th floor of the Hill Center. Everyone is invited to attend.
This semester the seminar is also being sponsored by DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science. DIMACS is providing funding for food and help with publicity, as well as access to DIMACS members and visitors to participate in the seminar.
We are currently looking for speakers (including faculty and visitors) for the seminar. If you would like to give a talk, then please contact Bill Cuckler, whose webpage is here.
If Delta is 3-connected, then Omega is a group expansion. If Delta is only 2-connected, then Omega is built from group expansions and multary quasigroup expansions in analogy to Tutte's 3-decomposition of graphs.
Biased expansions have associated matroids; those of group expansions of complete graphs are Dowling's lattices. If Delta is 2-connected and not extendible on the same vertex set, then it is built out of Dowling lattices and irreducible multary quasigroup expansions.
The 3-connectedness theorem implies that a multary
quasigroup with enough factorizations must be a group in disguise; this
proves a conjecture of Belousov. If it does not have enough
factorizations, it is obtained by composition of multary operations from
disguised groups and irreducible multary quasigroups.
Date: Monday, April 4, 2005
Speaker: Siddhartha Sahi
Title: Higher Correlations and FKG
Abstract: The FKG inequality is a correlation inequality for
pairs of random
variables defined on a lattice. An interesting consequence of the
inequality is that in the random graph G(n, p) monotone increasing events
are
positively correlated, so knowing that there is a path from x to y makes
it
more likely that there is a path from v to w. I will give an extension of
the FKG inequality for correlations involving more than two random
variables.
The proof employs formal power series.
Date: Monday, April 11, 2005
Speaker: Sujith Vijay
Title: Variations on a Question of Erdos
Abstract: Given a real number x and positive integers a and b,
the quasi-progression
Q(x;a,b) is the sequence of integers [ax],[(a+1)x],...,[bx] where [.]
denotes the floor function. When x is an integer, the quasi-progression
reduces to an ordinary arithmetic progression. Erdos asked in the 1930s
whether the non-negative integers can be coloured red and blue such that
all arithmetic progressions starting with 0 have bounded discrepancy
(i.e., the difference in the number of reds and blues in any
arithmetic progression is bounded by some absolute constant). I
will use a theorem of Roth to show that if the integers from 0 to N are
2-coloured, there exists a quasi-progression Q(x;a,b) such that x > 2 and
Q(x;a,b) has discrepancy at least 0.014 N^(1/6). I will also introduce a
game-theoretic "Maker-Breaker" version of the problem, and show how Maker
can force a discrepancy of N^(1/2-epsilon) on some arithmetic
progression,
for sufficiently large N.
Date: Monday, April 18, 2005
Speaker: Drew Sills
Title: Computer proofs via the algorithms of Sister Celine and Zeilberger
Abstract: A series $\sum_{k\geq 0} c_k$ is called hypergeometric if the term ratio $c_{k+1}/c_k$ is a fixed rational function of $k$ for all
$k$. Hypergeometric series had been studied extensively throughout the 19th and early 20th centuries, and it turns out that most of the functions of
elementary calculus have representations as hypergeometric series. In recent years, there has been a great deal of renewed interest in hypergeometric
series and their generalizations.
In her 1946 Ph.D. thesis, Sister Mary Celine Fasenmyer provided the first systematic (in fact algorithmic) approach
to finding recurrence relations satisfied by hypergeometric summands which allow the automatic derivation of hypergemetric summation formulas. Sister
Celine's algorithm, while easy to implement in modern computer algebra systems, is unfortunately rather slow.
In 1990, Doron Zeilberger published his
creative telescoping algorithm which accomplishes essentially the same goal as Sister Celine's algorithm, but does so much faster. Zeilberger's
algorithm was combined with some insights provided by Herbert Wilf to form the "WZ theory", for which the two shared the 1998 AMS Steele prize for
seminal contribution to research.
During the summer of 2004, Zeilberger, together with his student Mohamud Mohammed, produced a simplfied version of
Zeilberger's algorithm.
I plan to discuss and demonstrate the algorithms of Sister Celine and Zeilberger.
Date: Monday, April 25, 2005
Speaker: Diane Maclagen
Title:Counting lattice points in polyhedra
Abstract:The problem of counting the number of lattice points
in a polytope arises in several areas, including (combinatorial)
representation theory. I will give an introduction to some of the
techniques.
Links:
Previous semesters:
Fall
2004,
Spring
2004,
Fall
2003
and Spring
2003.
Rutgers Math Department's Seminar Page.
DIMACS/Computer Science Theory of Computing Seminar (previous semesters).
experimental math.
Princeton discrete math seminar.