 |
|
||||
- RICHARD ANSTEE, UBC
Forbidden Configurations: Progress towards a Conjecture [PDF]
-
A conjecture of Anstee and Sali predicts the asymptotic bounds that result when forbidding a single configuration.
Define a matrix to be {\it simple} if it is a (0,1)-matrix with no repeated columns. For a given (0,1)-matrix $F$, we say a matrix $A$ has no {\it configuration}
$F$ if there is no submatrix of $A$ which is a row and column permutation of $F$. Letting $|A|$ denote the number of columns in $A$, we define
$\hbox{forb}(m,F)=\max\{|A| : A$ is $m$-rowed simple matrix with no configuration $F\}$.
The conjecture gives an integral valued function $f(F)$ and claims that $\hbox{forb}(m,F)$ is $\Theta(m^{f(F)})$. The function $f(F)$ is determined by considering various possible product constructions that avoid $F$. One value of the conjecture is that it predicts critical configurations F to consider. We describe some recently proven critical cases and some proof ideas. This is joint work with M. Raggi and A. Sali.
- MATT BECK, San Francisco State University
Symmetrically constrained compositions [PDF]
-
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 mathematics. Partition analysis is full of
beautiful---and sometimes surprising---identities. As an example (and the
first motivation for our study), we mention compositions $(\lambda_1,
\lambda_2, \lambda_3)$ of an integer $m$ (i.e., $m = \lambda_1 +
\lambda_2 + \lambda_3$ and all $\lambda_j \in {\bf Z}_{\ge 0}$) that
satisfy the six "triangle conditions"
\[
\lambda_{\pi(1)} + \lambda_{\pi(2)} \geq \lambda_{\pi(3)} \qquad \text{ for every permutation } \pi \in S_3 \, .
\]
George
Andrews proved in the 1970's that the number $\Delta(m)$ of such
compositions of $m$ is encoded by the generating function
\[
\sum_{m \ge 0} \Delta(m) \, q^m = \frac{1}{(1-q^2)^2(1-q)} \, .
\]
More generally, for fixed given
integers $a_1, a_2, \dots, a_n$,
we call a composition $\lambda_1 + \lambda_2 + \cdots + \lambda_n$
\emph{symmetrically constrained}
if it satisfies each of the the $n!$ constraints
\[
\sum_{j=1}^n a_j \lambda_{ \pi(j) } \geq 0 \qquad \text{ for every permutation } \pi \in S_n \, .
\]
We show how to compute the generating functions of these compositions,
combining methods from partition theory, permutation statistics, and
polyhedral geometry.
This is joint work with Ira Gessel, Sunyoung Lee, and Carla Savage.
- NANTEL BERGERON, York University
Primitive orthogonal idempotents for R-trivial monoids [PDF]
-
We show that the notions of $R$-trivial monoid and weakly ordered monoid are equivalent. We use this fact to construct a complete system of orthogonal idempotents for all $R$-trivial monoids.
- KAROLY BEZDEK, Calgary
- SARA BILLEY, Univseristy of Washington
Singularities of generalized Richardson varieties [PDF]
- SARA BILLEY, Univseristy of Washington
-
Richardson varieties play an important role in intersection
theory and in the geometric interpretation of the
Littlewood-Richardson Rule for flag varieties. We discuss three
natural generalizations of Richardson varieties which we call
projection varieties, intersection varieties, and rank varieties. In
particular, the rank varieties can be described explicitly in
combinatorial terms. They are enumerated by dimension using a well
known q-analog of Stirling numbers of the second kind.
This is joint work with Izzet Coskun.
- TED BISZTRICZKY, University of Calgary
Combinatorial Constructions of Polytopes [PDF]
-
The face lattice of a (convex) polytope P is the set L(P) of all faces of P, partially ordered by inclusion. It is known that L(P) is an atomic and coatomic graded lattice. Two polytopes P and Q are combinatorially equivalent if L(P) and L(Q) are isomorphic. The combinatorial construction of a polytope is the construction of a lattice that is a face lattice. A geometrical realization of a polytope P is a polytope Q, in a real space of suitable dimension, that is combinatorially equivalent to P. We present both a combinatorial construction and a geometrical realization of a polytope.
- FAN CHUNG, UCSD
Flipping edges and vertices in graphs [PDF]
-
We study a certain random process on a graph $G$ which is a variation of a classical voter model and is also a special case of the so-called Tsetlin library random walk. Initially each vertex of $G$ is colored either blue or red.
At each step an edge is chosen at random and both endpoints change their colors to blue with probability $p$ and to red otherwise. This edge-flipping process corresponds to a random walk on the associated state graph in which each coloring configuration is a node. We show that the eigenvalues for the random walk on the state graph can be indexed by subsets of the vertex set of $G$. For example, for the uniform case of $p=1/2$, for each subset $T$ of the vertex set $V$ of $G$, the eigenvalue $\lambda_T$ (with multiplicity $1$) is the ratio of the number of edges in the induced subgraph of $T$ divided by the total number of edges in $G$. We analyze the stationary distribution of the state graph of colorings of $G$ for several special familie of graphs, such as paths, cycles and trees. We also mention related problems in connection with memoryless games.
This is a joint work with Ron Graham
- CHRIS GODSIL
State Transfer of Graphs [PDF]
-
If $A$ is the adjacency matrix of a graph $X$, then the continuous quantum walk on $X$ is governed by
the unitary matrix
\[
H(t) := \exp(itA).
\]
We have perfect state transfer from the vertex $u$ to vertex $v$ at time $\tau$ if
the $uv$-entry of $H(\tau)$ has absolute value 1.
The basic problem is to identify those cases where perfect state transfer occurs.
Some progress has been made in finding examples where it does, but the consensus
seems to be that it is not common. In my talk I will report on recent work that
provides necessary conditions: for example if there is perfect state transfer from $u$ to $v$,
then the vertex-deleted subgraphs $X\setminus u$ and $X\setminus v$ are cospectral.
- ANGELE HAMEL, Wilfrid Laurier University
Symplectic Schur Function Identities [PDF]
-
We provide a combinatorial proof of a symplectic character identity relating
the sum of a product of symplectic Schur functions to the product
$\prod^{m}_{i=1} \prod^{n}_{j=1} (x_i + x^{-1}_{i} + y_j + y_{j}^{-1})$. This formula is due to Hasegawa and has also been proved combinatorially by Terada. The identity itself generalizes a well-known identity of Littlewood
expressing $\prod^{m}_{i=1} \prod^{n}_{j=1} (x_i + y_j)$ as a sum of products of Schur
functions. We also discuss other symplectic Schur function identities we have proved that have recently been found to have a connection to analytic number theory.
This is joint work with R.C. King.
- PENNY HAXEL, University of Waterloo
On Schnyder's Theorem [PDF]
-
We give a simple proof of Schnyder's Theorem, which states that a graph is planar if and only if the dimension of its incidence poset is at most three, and discuss some related results. (Joint work with Fidel Barrera-Cruz)
- DAVID KIRKPATRICK, University of British Columbia
Competitive search in symmetric trees [PDF]
-
A familiar quandary arises when there are several possible approaches that might lead to the solution of a problem, but no way of knowing which, if any, are viable for a particular problem instance. Faced with this uncertainty, one is forced to explore alternative approaches through a coordinated interleaving process. As usual, the objective is to minimize the total exploration cost.
Popular formulations of such problems include variants of the {\em cow-path problem}: search, among a collection of disjoint paths that emanate from some junction point, for a goal (pasture) located at some unknown distance along one of the paths. Much of the existing work has assumed that at most one of the alternatives is viable, providing support for a competitive analysis of algorithms, using the cost of the unique viable alternative as a benchmark. Recently more attention has been devoted to versions in which there may be multiple viable solutions (think of cow-paths with many, equally satisfactory, goals), and arguably-optimal universal search strategies have been formulated in this richer setting.
In this talk we look at the same multi-goal search problem when the search domain is modeled as a symmetric tree. In so doing our hope is to reflect more accurately the fact that alternative solutions to natural problems may have much in common, deviating only at clearly defined decision/branch points. We describe optimal competitive search strategies in this context that generalize earlier results on the $m$-ray cow-path problem.
[Based on joint work with Sandra Zilles, University of Regina]
- FU LIU, University of California, Davis
Pure-cycle Hurwitz factorizations and multi-noded rooted trees [PDF]
-
Pure-cycle Hurwitz numbers count the number of connected branched covers of the projective line where each branch point has only one ramification point over it. The main result of the talk is that when the genus is $0$ and one of the ramification indices is $d,$ the degree of the covers, the pure-cycle Hurwitz number is $d^{r-3},$ where $r$ is the number of branch points. This is equivalent to the statement that the number of minimal factorizations of a $d$-cycle into a given type is $d^{r-2}.$
Springer and Irving independently proved the above result by symmetrizing the problem. We give a "desymmetrized" bijective proof. Our argument proceeds by constructing a new combinatorial class of objects which we call multi-noded rooted trees, showing it has cardinality $d^{r-2},$ and establishing a bijection between this new class and minimal factorizations.
- GARY MACGILLIVRAY, University of Victoria
Injective oriented colourings [PDF]
-
\emph{Oriented colourings} are vertex colourings of oriented graphs that respect the direction of the arcs: whenever there is an arc from a vertex coloured $i$ to a vertex coloured $j \not= i$, there is no arc from a vertex coloured $j$ to a vertex coloured $i$. There are several possible definitions of ''\emph{injective}'' oriented colourings. An example, first studied by Courcelle in 1994, is that these are oriented colourings where no two in-neighbours of a vertex are assigned the same colour. The different definitions lead to a collection of five related colouring parameters. The goal is to discuss the aspects of the theory of these colourings that relate to homomorphism models, complexity, algorithms, critical digraphs, obstructions, and bounds.
- MARNI MISHNA, Simon Fraser University
Recent progress in exact lattice path enumeration [PDF]
-
We will report on some recent taxonomic results in lattice paths confined to the first quadrant. Three independent investigations have offered different concrete strategies for deciding the nature of the generating function for a class of walks, based solely on the allowable directions for the steps. Our favourite is an adaptation of the kernel method. The underlying functional equations appear in a far broader combinatorial context, and the kernel method handles these equations well. The results can be either exact enumeration, or a prediction of the nature of related generating functions. We will discuss the potential of this technique to predict D-finiteness for general combinatorial classes.
- BOJAN MOHAR, Simon Fraser University
Average degree condition forcing complete graph immersion [PDF]
-
An immersion of a graph $H$ into a graph $G$ is a one-to-one mapping $f: V(H) \to V(G)$ and a collection of edge-disjoint paths, one for each edge of $H$, such that the path $P_{uv}$ corresponding to edge $uv$ has endpoints $f(u)$ and $f(v)$. We prove that every simple graph with average degree $\Omega(t)$ immerses the complete graph $K_t$. Moreover, if $G$ is dense enough, then there is an immersion of $K_t$ in which each path $P_{uv}$ is of length precisely 2. This is joint work with Matt DeVos, Zdenek Dvorak, Jacob Fox, Jessica McDonald, and Diego Scheide.
- ISABELLA NOVIK, University of Washington
Face numbers of balanced spheres and manifolds [PDF]
-
We compare the face numbers of balanced triangulations of spheres and manifolds to those of arbitrary triangulations of spheres and manifolds. This includes discussion of some recent results as well as many open problems.
- BRUCE REED, McGill
Some recent evidence for the Erdos-Hajnal Conjecture [PDF]
-
The Erdos Hajnal conjecture states that for every graph $H$, there is an $\epsilon>0$ such that EVERY
graph $G$ which does not contain $H$ as an induced subgraph has a clique or a stable set of size at
least $|V(G)|^\epsilon$. We prove the wekaening of this conjecture obtained by replacing EVERY by
ALMOST EVERY and discuss the value of $\epsilon$ for various $H$. This is joint work with Frederic Havet, Ross Kang, Colin McDiarmid, Alex Scott, Stephan Thomasse, and Andrew Thomason.
- JEFF REMMEL, UCSD
Ascent Sequences, $2+2$-free posets, Upper Triangular Matrices, and Genocchi numbers. [PDF]
-
The combinatorics of the Genocchi numbers was developed by
Dumont and various co-authors in the 70's and 80's. More recently,
Bousquet-Melou, Claesson, Dukes, Kitaev and Parviainen showed that the
2+2-free posets are in bijection with so-called ascent sequences and
with non-negative integer valued upper triangular matrices which have no
zero rows or columns. We will show that the Genocchi and the Median
Genocchi numbers count the number of up-down ascent sequences. We also
show how the $q$-analogues of the Genocchi and Median Gennochi numbers
can be obtained by $q$-counting up-down ascent sequences.
- FRANK RUSKEY, University of Victoria
Tatami Tilings of Rectangles [PDF]
-
This talk is concerned with tilings of rectangular grids with tiles
of two sizes, $1 \times 2$ tiles (dimers) and $1 \times 1$ tiles (monomers).
The tiles must partition the rectangle and satisfy the constraint that no
four corners of the tiles meet; such tilings are called tatami tilings.
We provide a structural characterization of tatami tilings and use it
to prove that the tiling is completely determined by the tiles that are on
its border.
We show various enumerative results; for example, that the
number of tatami tilings of an $n \times n$ square with $n$ monomers is
$n2^{n-1}$.
We also show that, for fixed-height, the generating
function for the number of tatami tilings of a rectangle is a
rational, and outline an algorithm that produces the generating function.
This is joint work with Alejandro Erickson, Mark Schurch, and Jenni Woodcock.
- ANNE SCHILLING, UC Davis
The Murnaghan-Nakayama rule for $k$-Schur functions [PDF]
-
We prove the Murgnaghan-Nakayama rule for $k$-Schur functions of Lapointe and Morse, that is, we give an explicit formula for the expansion of the product of a power sum symmetric function and a $k$-Schur function in terms of $k$-Schur functions. This is proved using the noncommutative $k$-Schur functions in terms of the nilCoxeter algebra introduced by Lam and the affine analogue of noncommutative symmetric functions of Fomin and Greene.
This is joint work with Jason Bandlow and Mike Zabrocki (arXiv:1004.4886).
- REKHA THOMAS, University of Washington
Cone Lifts of Convex Bodies [PDF]
-
A central open question at the intersection of convexity and optimization is to characterize those convex semialgebraic sets that arise as the projection of a slice of a positive semidefinite cone by an affine space. In this talk I will address the following question: Given a convex body C and a closed convex cone K, when is C the projection of K intersected with an affine space? The characterization relies on a new notion of cone-factorization of a nonnegative matrix extending the well-known notion of nonnegative factorization of a nonnegative matrix.
- CSABA D. TOTH, University of Calgary
The size of topological graphs with restricted crossings [PDF]
-
A topological graph is a graph drawn in the plane such that the vertices are distinct points and the edges are Jordan arcs between the vertices. The celebrated crossing lemma gives an upper bound on the number of edges in terms of the number of vertices and the crossing number. We present new upper bounds on the number of edges under certain restrictions on the crossings. Assume $G$ is a topological graph with $n$ vertices such that every edge can be partitioned into two end segments and one middle segment such that (1) each crossing involves one end segment and one middle segment; (2) each middle segment and end segment intersect at most once; and (3) each middle segment crosses at most $k$ end segments that share a vertex. Then $G$ has $O(kn)$ edges. (Joint work with Eyal Ackerman and Radoslav Fulek.)
- KAREN YEATS, Simon Fraser University
Patterns in Feynman graph denominators [PDF]
-
We now know of many identities of the denominators of Feynman integrals after some, typically six, parametric integrations. Fortunately, these identities are very combinatorial in flavour and we are beginning to see something of the systematic picture. I will explain this story and present some nice denominator identities of graphs.
