Past Discrete Maths Seminars

 

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.