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

Hypergraph Decompositions
Org: Shonda Gosselin (University of Winnipeg)

ROBERT BAILEY, University of Regina
Generalized covering designs as hypergraph covers  [PDF]

The idea of {\em generalized covering designs} provides a simultaneous generalization of covering designs and covering arrays. An equivalent formulation is as a covering of a complete uniform hypergraph with respect to a specified partition of the vertex set. This equivalence will be explained in this talk, as will some related problems.

ANDREA BURGESS, Ryerson University
Generalized packing designs and hypergraph packings  [PDF]

In 2009, Peter Cameron introduced a generalization of $t$-designs; these generalized designs may be viewed as particular decompositions of an associated hypergraph into complete $t$-uniform hypergraphs. We consider a similar generalization of packing designs, encompassing structures such as ordinary packings and packing arrays. We examine the relationship between generalized packings and hypergraph packing problems, provide bounds on generalized packing numbers, and discuss connections between generalized packings and various combinatorial designs.

(Joint work with Robert Bailey)

SHONDA GOSSELIN, University of Winnipeg
Regular or vertex-transitive q-complementary hypergraphs  [PDF]

If a complete uniform hypergraph can be decomposed into $q$ isomorphic hypergraphs which are permuted cyclically by some permutation of the vertex set, then each hypergraph in the decomposition is called {\em $q$-complementary}, as these objects generalize self-complementary graphs. We present necessary and sufficient conditions on the order of a vertex-transitive $q$-complementary hypergraph. These hypergraphs correspond to large sets of $q$ isomorphic designs. We also construct regular self-complementary uniform hypergraphs of all possible orders.

MATEJA SAJNA, University of Ottawa
Regular self-complementary uniform hypergraphs  [PDF]

A {\em $k$-uniform hypergraph} $(V,E)$ is said to be {\em self-complementary} if it is isomorphic to its complement $(V,V^{(k)}-E)$, and {\em $t$-subset-regular} if every $t$-subset of $V$ lies in the same number of edges. In this talk, we discuss necessary and sufficient conditions on $n$, $k$, and $t$ for there to exist a $t$-subset-regular self-complementary $k$-uniform hypergraph of order $n$.

A. PAWEL WOJDA, AGH University of Science and Technology, Cracow, Poland
Cyclic partitions of complete hypergraphs  [PDF]

Let $V_n = \{ 1,2,\ldots,n\}$. A {\em cyclic $q$-partition} of a complete $k$-hypergraph $\mathcal{K}^{(k)}_n=(V_n,{V_n \choose k})$ is a partition of the edge set $V_n \choose k$ of the form $\{E,E^\theta,E^{\theta^2}, \ldots, E^{\theta^{q-1}}\}$, where $\theta$ is a permutation of the set $V_n$. We give a necessary and sufficient condition for $\theta$ to be a cyclic $q$-partition of $\mathcal{K}^{(k)}_n$. We deduce the characterisations of cyclic $q$-partitions of hypergraphs $\mathcal{K}^{K}_n=(V_n,\bigcup_{k\in K}{V_n \choose k})$ for some $K \subset V_{n-1}$.

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