CanaDAM 2015
Université de la Saskatchewan, 1 - 4 juin 2015

Structural properties of graphs II

ANDRZEJ CZYGRINOW, Arizona State University
Cycle factors in 3-uniform hypergraphs  [PDF]

In 1993, Aigner and Brandt showed that if G is a graph on n vertices of minimum degree (2n-1)/3, then G contains any 2-factor on n vertices. In this talk, we will consider similar problems for 3-uniform hypergraphs. In particular, we will discuss co-degree conditions for the existence of factors consisting of loose cycles.

DARYL FUNK, Simon Fraser University
Biased graphs, group-labelled graphs, and well-quasi-ordering  [PDF]

We present the following surprising results: For each $r \geq 3$, there exist infinite antichains of biased graphs on $r$ vertices, infinite antichains of frame matroids of rank $r$, and infinite antichains of lift matroids of rank $r$. We construct such antichains using a topological characterisation of those biased graphs that are \emph{group-labelled} -- i.e., obtained by \emph{labelling} the edges of a graph with elements of a group. (No prior knowledge of biased graphs or matroids will be assumed.)

This is joint work with Matt DeVos (SFU) and Irene Pivotto (University of Western Australia).

KAREN GUNDERSON, University of Bristol
Friendship Hypergraphs  [PDF]

For $r\ge2$, an $r$-uniform hypergraph is called a friendship $r$-hypergraph if every set $R$ of $r$ vertices has a unique `friend' - a vertex $x\notin R$ with the property that for each subset $A\subseteq R$ of size $r-1$, the set $A\cup\{x\}$ is a hyperedge. In the case $r=2$, the Friendship Theorem of Erdos, Renyi and Sos states that the only friendship graphs consist of triangles with a single common vertex. For $r\geq3$, there exist infinite classes of friendship $r$-hypergraphs. In this talk, I shall describe new results on both upper and lower bounds on the size of friendship hypergraphs.

MUHAMMAD ALI KHAN, University of Calgary
Edge cover and edge decomposition polynomials of hypergraphs  [PDF]

We introduce two new polynomials for hypergraphs, namely the \textit{edge cover polynomial} and the \textit{edge decomposition polynomial}, as the generating functions of the number of edge coverings and edge decompositions of a hypergraph, respectively. We study the algebraic and combinatorial properties of these polynomials and develop a recursive procedure for computing these polynomials based on the operations of vertex and edge deletion. It turns out that these polynomials can be used to enumerate the tilings (resp. coverings) of any bounded region of a lattice by finitely many lattice animals. Examples include counting the tilings of a rectangle by polyominoes.

SEAN MCGUINNESS, Thompson Rivers University
Toric ideals, a conjecture of White, and a base exchange property for group labeled graphs.  [PDF]

We examine a conjecture of White relating to the Toric ideal of a matroid. It was shown by Blasiak that the Toric ideal of a graphic matroid is generated by quadratic binomials. We extend this result by showing that the Toric ideal associated with the matroid of a group labeled graph is also generated by quadratic binomials, when the group has odd order. Similar to Blasiak, the proof of this involves transforming one collection of bases into another using a sequence of symmetric exchanges.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Saskatchewan