CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Extremal Combinatorics

MAHMUD AKELBEK, Weber State University
Various bounds on the scrambling index and the generalized scrambling index  [PDF]

The scrambling index of a primitive digraph D is the smallest positive integer m such that for every pair of vertices u and v, we can get to a vertex w in D by directed walks of length m, and it is denoted by k(D). In this talk, we present various upper bounds on the scrambling index and the generalized scrambling index of primitive digraphs.

SEAN MCGUINNESS, Thompson Rivers University
Degree constrained subgraphs in a graph  [PDF]

At each vertex v of a graph G we partition the edges into k sets $E_{v1}, E_{v2}, \dots , E_{vk}.$ Let $0 \le q_{vi} \le p_{vi} \le |E_{vi}|$, i=1,2...k and let $0\le t_v \le d_G(v).$ We shall address the problem: can one find a subgraph $H$ of $G$ such that at each vertex $v$, $q_{vi} \le |E(H) \cap E_{vi}| \le p_{vi},\ i = 1, \dots ,k$ and $d_H(v) \le t_v$ ?

MARK SCHURCH, University of Victoria
On Graphs with Depression Three  [PDF]

Consider an edge ordering $f$ of a graph $G$. A path for which $f$ increases along its edge sequence is called an $f$-ascent, and a maximal $f$-ascent if it is not contained in a longer $f$-ascent. The depression of $G$ is the least integer $k$ such that every edge ordering has a maximal ascent of length at most $k$. I will discuss graphs with depression three and no adjacent vertices of degree three or more.

BEN SEAMONE, Carleton University
Variations of the 1,2,3-Conjecture  [PDF]

Karoński, Łuczak, and Thomason conjectured that the edges of a graph having no edge component can be weighted from the set \{1,2,3\} so that any two adjacent vertices have distinct sums of weights from their respective incident edges. I will survey a number of variations of this "1,2,3-Conjecture" including a variation which has been completely solved by myself and Dr. Brett Stevens where only two edge weights are required.

TAMON STEPHEN, Simon Fraser University
A short proof that 4-prismatoids have width at most 4.  [PDF]

Santos' recent construction of a counterexample to the Hirsch conjecture highlights a particular 5-dimensional "prismatoid" polytope. We use the Euler characteristic to give a simple proof that there is no analogous 4-dimensional prismatoid.

This is joint work with Hugh Thomas.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria