|
Spring 2005
Place: WMAX 216
Time: Tuesday, 4-5pm
25th Jan |
Anders Buch (Aarhus) |
|
Formulas for quiver varieties: A quiver variety is a general
type of degeneracy locus associated to a quiver of vector bundles and bundle
maps over a variety. I have proved a formula for the Grothendieck class
of a quiver variety when the underlying quiver is equioriented of type
A. This formula is stated in terms of integers called quiver coefficients,
which are generalizations of Littlewood-Richardson coefficients.
Knutson, Miller, and Shimozono have shown that the lowest degree coefficients,
which describe the cohomology class of the quiver variety, are non-negative.
I will speak about a proof that general quiver coefficients have signs
that alternate with codimension. I will also explain a cohomology
formula for non-equioriented quiver varieties, which I have recently proved
with R. Rimanyi. |
1st Feb |
Josh Cooper (Courant) |
|
Generalized de Bruijn Cycles:Joint work with Ron Graham. A (binary)
de Bruijn cycle of order $k$ is a cyclic string of 0's and 1's so that
a sliding "window" of length $k$ will see every binary $k$-word exactly
once. It is classical that such strings exist for every $k$, even for alphabets
with more than two symbols. If we change the ``window'' from $\{1,2,\ldots,k\}$
to another set $W$ of cardinality $k$, then we may ask whether there exists
a $q$-ary string $S$ of length $q^k$ with the same property: that, when
restricted to the indices $W+r$ modulo $q^k$ for each $r$ from $0$ to $q^k-1$,
$S$ yields every possible $k$-tuple exactly once. It turns out that this
problem is surprisingly difficult, and only the case of $k=2$ has been
settled completely. We present the proof of this result and discuss several
related questions, including the issue of finding bounds on the shortest
string which, for a given window, yields every $k$-tuple at least
once. |
8th Feb |
Dimitris Achlioptas (Microsoft) |
|
Phase Transitions in Hard Optimization Problems: Many hard (NP-complete)
optimization problems are easy for random inputs. For example, in
a random graph where each edge is present with probability 1/2 one can
find a Hamiltonian cycle in linear time, almost surely. On the other hand,
random instances of satisfiability (k-SAT) and graph coloring appear to
be hard. Moreover, each problem appears to be hardest near its "threshold",
a constraint density around which the probability of solubility drops rapidly
from near 1 to near 0. Locating these two thresholds and understanding
the behavior of algorithms near them is an active topic of research in
combinatorics, theoretical computer science, probability, and statistical
physics.
We study how the structure of the set of solutions evolves in each of
these two problems as constraints are added. This allows us to determine
the location of the threshold for both random satisfiability and random
graph colorability up to second order terms. To do this we prove that for
a large class of random constraint satisfaction problems the second moment
of the number of solutions is captured by an "entropy-energy" tradeoff.
Critical values of this tradeoff correspond to points where the structure
of the space of solutions undergoes dramatic change. By identifying these
critical points, we not only get to locate thresholds but we also gain
rigorous insight on why algorithms have a hard time near them. |
22nd Feb |
Malek Abdesselam(UBC) |
|
Feynman diagrams, classical invariant theory, resultants, and the
Hadamard-Foulkes-Howe conjecture:
Foulkes' conjecture (1950) can be stated as a comparison of Schur multiplicities
in two plethystic compositions of complete symmetric functions. In 1987,
R. Howe gave a strengthening of this conjecture into a surjectivity statement
for a specific SL(V)-equivariant map between iterated symmetric powers
of a vector space V. In fact, the resulting Foulkes-Howe conjecture, has
already been studied in the mid 1890's by J. Hadamard, in the context of
classical invariant
theory and classical elimination theory! I will try to relate this
story, in the most appropriate tongue, that of Feynman diagrams, which
are ubiquitous combinatorial objects in physics. I will also discuss some
recent work, by Jaydeep Chipalkatti and myself, regarding a generalization
of the problem addressed by the conjecture. |
1st Mar |
Richard Anstee (UBC) |
|
Some new and interesting results in matching theory: |
8th Mar |
Matthew Morin (UBC) |
|
The chormatic symmetric function of caterpillars: |
15th Mar |
Shlomo Hoory (CS, UBC) |
|
Simple permutations mix well: Joint work with Alex Brodsky.
A naturally occurring question in cryptography is how well the composition
of simple permutations drawn from a simple distribution resembles a random
permutation. Although such constructions are a common source of security
for block ciphers like DES and AES, their mathematical justification (or
lack thereof) is troubling. Motivated by this question, we study the random
composition of a small family of O(n^3) simple permutations on {0,1}^n.
Specifically we ask how many randomly selected simple permutations need
be composed to yield a permutation that is close to k-wise independent.
We improve on the results of Gowers 1996 and Hoory, Magen, Myers and Rackoff
2004, and show that up to a polylogarithmic factor, n^2*k^2 compositions
of random permutations from this family suffice. We also introduce the
new notion of closeness to k-wise independence against adaptive adversaries
and show the constructed permutation has the stronger property. In addition,
our results give an explicit construction of a degree O(n^3) Cayley graph
of the alternating group of 2^n objects with a spectral gap Omega(1/(n^2*2^n)),
which is a substantial improvement over previous constructions.
This question is essentially about the rapid mixing of a certain Markov
chain, and the proofs are based on the comparison technique. |
22nd Mar |
Federico Ardila (Microsoft) |
|
The Bergman complex of a matroid and the space of phylogenetic trees:
Motivated
by a problem about solving systems of polynomial equations, we associate
to each matroid M a polyhedral complex B(M), called the "Bergman complex".
I will talk about the combinatorics and topology of this complex. Somewhat
surprisingly, the space of phylogenetic trees is (essentially) a
Bergman complex, and we obtain some new results about it as a consequence.
If M is an oriented matroid, the Bergman complex B(M) has a "positive part"
B+(M), which I will also describe.
If time allows, I will show how, for the matroid of a crystallographic
root system, one can describe these objects in terms of the combinatorics
of the associated Dynkin diagram.
The talk will be essentially self-contained. |
29th Mar |
Roger Woodford (UBC) |
|
Prime Symmetric Divisor Functions: Applying a symmetric polynomial
to the multi-set of prime divisors (with repetition) of a positive integer
n defines a function from the natural numbers into the integers. We investigate
questions pertaining to these "prime symmetric functions" analogous to
questions posed regarding the usual divisor functions, such as the sum
of proper divisors function. For instance, if f is a prime symmetric function,
when does f(n) = n? More generally, when does f^(k)(n) = n? What is the
average order of f? If the sequence of iterates n, f(n), f^(2)(n),... is
ultimately periodic, what is the expected number of iterations before the
sequence terminates in a cycle? We develop some of the general properties
of this new class of divisor functions. |
|