|
CombinaTexas'05 will be held on the
campus of Texas A&M University
, on February 24, Saturday, 2007.
All the academic activities will be held at the
Blocker Building (BLOC), Room 165 and 155.
|
Abstracts
|
|---|
Speaker:
Ioana Dumitriu
Title:
Error-correcting codes with feedback, or How to
beat a (constrained) liar
Abstract:
The Ulam-R\'{e}nyi liar game has served as a great source of
inspiration for combinatorialists and information theorists alike for the
better part of a century. Numerous variations of the problem have been
studied as two-person, perfect information "liar" games, or as strategies
for adaptive search with unreliable answers (error-correcting codes). I
will survey some of the work that has been done on this particular
formulation of the Ulam-Renyi problem; variants range from fully adaptive
to semi-adaptive strategies, constrained versus unconstrained lies,
uni or multichannels, etc.
|
Speaker:
Art Duval
Title:
Counting weighted simplicial spanning trees of shifted complexes
Abstract:
Building upon the work of Kalai and Adin, we extend the concept
of a spanning tree from graphs to simplicial complexes. For all complexes
K satsifying a mild technical condition, we show that the simplicial
spanning trees of K can be enumerated using its Laplacian matrices,
generalizing the matrix-tree theorem. As in the graphic case, replacing
the Laplacian with a weighted analogue yields homological information about
the simplicial spanning trees being counted. We find a nice expression for
the resulting weighted tree enumerator of shifted complexes, by
generalizing a formula for the Laplacian eigenvalues of a shifted complex
to the weighted case.
This is joint work with Caroline Klivans and Jeremy Martin
|
Speaker:
Miguel Mendez
Title:
Enumerative applications of the arithmetic product of formal power series and symmetric functions
Abstract:
The arithmetic product in the context of Joyal’s species has been introduced
recently by Manuel Maia and myself. This operation, described in
set-theoretical terms, could be mapped to the algebraic world of
generating functions in two ways.
1) It goes to the arithmetic product on formal power series, obtained by taking exponential or ordinary generating functions on the arithmetic product of two combinatorial or tensor species.
2) It goes to the arithmetic product of symmetric function, by taking cycle index, or equivalently, Frobenius character on the arithmetic product of two combinatorial or tensor species.
The first operation on formal power series gives interesting combinatorial interpretation to the Lambert series and to the product of Dirichlet series. The arithmetic product of symmetric functions is a little known operation. It can be formulated in terms of characters of the symmetric groups, leading to the problem of expanding the arithmetic product of two Schur functions in terms of Schur functions.
By exploiting some similarities of the arithmetic product with plethysm we obtain combinatorial interpretations of the arithmetic product of elementary and homogeneous symmetric functions, closed formulas for simple cases, and formulas for the enumeration of 2x n matrices up to row and column permutation.
|
Speaker:
Douglas West
Title:
Parity and Strong Parity Edge-Colorings of Graphs
Abstract:
A parity walk in an edge-coloring of a graph is a walk along which each
color is used an even number of times. Let $p(G)$ be the fewest colors in an
edge-coloring of $G$ having no parity path (a parity edge-coloring ).
Let $p'(G)$ be the least number of colors in an edge-coloring of $G$ having no
open parity walk (a strong parity edge-coloring).
Always $p'(G)\ge p(G)\ge \chi'(G)$.
The main result is that $p'(K_n)=2^{\CL{\lg n}}-1$ for all $n$, proved using
binary vector spaces. This result strengthens a special case of Yuzvinsky's
Theorem on sums of binary vectors. The optimal strong parity edge-coloring of
$K_n$ is unique when $n$ is a power of 2, and the optimal colorings are
completely described for all $n$.
In addition to presenting this proof, this talk will discuss combinatorial
aspects of these parameters, including examples where $p(G)$ and $p'(G)$ are
equal, examples where they are not, and relations to other parameters.
Many open problems will be presented.
These results are joint work with David P. Bunde, Kevin Milans, and Hehui Wu,
present and former students at the University of Illinois.
|
Speaker:
Herbert Wilf
Title:
Partition congruences and geographical clusters of cases of a disease
Abstract:
[The two subjects in the title are unrelated except that I'll talk about both of them]
Ramanujan conjectured and proved a number of results about congruence properties of the integer
partition function, in particular that p(5n+4) is divisible by 5 for all n. This was refined by
Berkovich and Garvan, and we will give a short proof of a similar refinement. We show that not
only is p(5n+4) divisible by 5, but actually the number of partitions of 5n+4 whose "BG rank" is
j, is divisible by 5, for all n and j.
In the second sub-talk I'll show how the distribution of the maximum cell occupancy in
balls-in-boxes problems can be rapidly computed using combinatorial methods, thus allowing
determination of whether an apparent cluster of disease cases in a small locality is really
unusual or is to be expected. Older methods for this problem required exponential time.
|
| |
