CanaDAM 2011 University of Victoria, May 31 - June 3, 2011 www.cms.math.ca//2011

# Contributed Minisymposia

There will be contributed minisymposia in the following areas.

Applications of Graph Theory To Chemistry I
Org: Patrick Fowler (University of Sheffield)

This session and the following one explore applications of Graph Theory to Chemistry. Part I: Conduction and aromaticity in carbon networks, and computer generation of conjectures about graph parameters and chemical invariants.

Patrick Fowler (University of Sheffield), Craig Larson (Virginia Commonwealth University), Milan Randic (National Insitute of Chemistry, Ljubljana), Irene Sciriha (University of Malta).

Applications of Graph Theory to Chemistry II
Org: Wendy Myrvold (University of Victoria)

This session and the previous one explore applications of Graph Theory to Chemistry. Part II: Fullerenes and algorithms for generating graphs representing classes of chemical molecules.

Elizabeth J. Hartung (Syracuse University), Wendy Myrvold (University of Victoria), Nico Van Cleemput (Ghent University), Dong Ye (West Virginia University).

Applications of Matroid Theory in Coding Theory I
Org: Irene Márquez Corbella (University of Valladolid)

This minisymposium is aimed at bringing together researchers from all fields related to the applications of matroid theory in coding theory. Since much of the work related to this subject is still ongoing, the minisymposium will provide a stimulating atmosphere where experts will be able not only to report their recent results, but also to propose new guidelines of research and discuss open questions. It will also give us the opportunity to present the interest and the potential applications of this topic to the rest of the scientific community.

Thomas Britz (University of New South Wales (Australia)), Graham Farr (Monash University (Australia)), Gary Gordon (Lafayette College), Relinde Jurrius (Eindhoven University of Technology (Netherlands)).

Applications of Matroid Theory in Coding Theory II
Org: Edgar Martínez Moro (University of Valladolid)

This minisymposium is aimed at bringing together researchers from all fields related to the applications of matroid theory in coding theory. Since much of the work related to this subject is still ongoing, the minisymposium will provide a stimulating atmosphere where experts will be able not only to report their recent results, but also to propose new guidelines of research and discuss open questions. It will also give us the opportunity to present the interest and the potential applications of this topic to the rest of the scientific community.

Irene Márquez Corbella (University of Valladolid (Spain)), Edgar Martínez Moro (University of Valladolid), Pradeep Sarvepalli (University of British Columbia (Vancouver)), Keisuke Shiromoto (Kumamoto University (Japan)).

Chromatic Numbers of Graphs
Org: Joan Hutchinson (Macalester College)

Many variations on the classic chromatic number of a graph have emerged in recent years, sometimes to illuminate that chromatic number and other times for the sake of the new variation and its applications. In this mini-symposium the variations of list-coloring, co-chromatic number, subchromatic number, and 1-defective colorings will be presented, along with the interaction between colorings as measured by the canonical coloring graph of a graph.

Karen L. Collins (Wesleyan University, Middletown CT 06459-0128), John Gimbel (University of Alaska at Fairbanks), Ruth Haas (Smith College), Joan Hutchinson (Macalester College), Michelle Lastrina (Iowa State University).

Colourings, Independence, and (Forbidden) Subgraphs
Org: Ingo Schiermeyer (Technical University Freiberg, Germany)

There is a great variety of results for vertex-colourings and independence in graphs in terms of forbidden subgraphs. One of the most well-known is the Strong Perfect Graph Theorem. Edwards has shown the following approach: If a graph $G$ has a dominating set $D$, then $3$-colourability can be decided in time $O(3^{|D|} \cdot |E(G)|)$. Using a result of Bacs\'o and Tuza that a $P_5$-free graph has a dominating clique or a dominating $P_3,$ Randerath and Schiermeyer showed that $3$-colourability can be decided in polynomial time for $P_5$-free and $P_6$-free graphs.

Stephan Matos Camacho (Technical University Freiberg, Germany), Anja Kohl (Technical University Freiberg, Germany), Vadim Lozin (University of Warwick, UK), Ingo Schiermeyer (Technical University Freiberg, Germany).

Convexity and Metric Graph Theory I
Org: José Cáceres (Universidad de Almería, Almería (Spain))

In a network, the most natural question about two vertices is whether or not they are connected, and the second one could be asking for the distance between them. Thus the study of graphs as metric spaces has been always an important part of the field. This minisimposium and the following one intend to show those recent developments in metric frameworks as convexity that may lead to new perspectives on old questions.

Robert Bailey (Department of Mathematics and Statistics University of Regina Regina, SK Canada), José Cáceres (Departamento de Estadística y Matemática Aplicada Universidad de Almería Almería, Spain), Alberto Márquez (Departamento de Matemática Aplicada I Universidad de Sevilla Sevilla, Spain), Mercè Mora (Departament de Matemàtica Aplicada II Universitat Politècnica de Catalunya Barcelona, Spain), Michael Young (Iowa State University).

Convexity and Metric Graph Theory II
Org: José Cáceres (Universidad de Almería, Almería (Spain))

In a network, the most natural question about two vertices is whether or not they are connected, and the second one could be asking for the distance between them. Thus the study of graphs as metric spaces has been always an important part of the field. This minisimposium and the previous one intend to show those recent developments in metric frameworks as convexity that may lead to new perspectives on old questions.

Mitre Dourado (COPPE Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ Brazil), Morten Nielsen (Department of Mathematics and Statistics Thompson Rivers University Kamloops, BC Canada), Ortrud R Oellermann (Department of Mathematics and Statistics University of Winnipeg Winnipeg, MB Canada), Ignacio M Pelayo (Departament de Matemàtica Aplicada III Universitat Politècnica de Catalunya Barcelona, Spain).

Covering Arrays, Generalizations and Software Testing Applications I
Org: Peter Danziger (Ryerson University), Lucia Moura (University of Ottawa) and Brett Stevens (Carleton University)

Covering arrays are combinatorial designs that generalize orthogonal arrays, and have been more intensively studied in the past few years. Under the name of test suites for pairwise or combinatorial testing, they have proved very effective for testing hardware and software. This two-part mini-symposium showcases the interplay of covering array theory and applications. It shows how the applications motivated the study of generalizations of covering arrays with interesting ties to other areas of discrete mathematics (graph and hypergraph theory, graph homomorphisms, combinatorial group testing, probability theory). It also overviews current software testing research that supports the use of covering arrays.

Gary Bazdell (Carleton University), Myra Cohen (University of Nebraska - Lincoln), Dan Hoffman (University of Victoria), Elizabeth Maltais (University of Ottawa), Lucia Moura (University of Ottawa).

Covering Arrays, Generalizations and Software Testing Applications II
Org: Peter Danziger (Ryerson University), Lucia Moura (University of Ottawa) and Brett Stevens (Carleton University)

Covering arrays are combinatorial designs that generalize orthogonal arrays, and have been more intensively studied in the past few years. Under the name of test suites for pairwise or combinatorial testing, they have proved very effective for testing hardware and software. This two-part mini-symposium showcases the interplay of covering array theory and applications. It shows how the applications motivated the study of generalizations of covering arrays with interesting ties to other areas of discrete mathematics (graph and hypergraph theory, graph homomorphisms, combinatorial group testing, probability theory). It also overviews current software testing research that supports the use of covering arrays.

Nevena Francetic (University of Toronto), Brady Garvin (University of Nebraska -- Lincoln), Anant Godbole (East Tennessee State University), Sebastian Raaphorst (University of Ottawa).

Designs and Codes I
Org: Peter Dukes (University of Victoria), Esther Lamken (California Institute of Technology) and John van Rees (University of Manitoba)

Codes and Designs have many applications to statistics, communications and engineering. They are also an important component to pure mathematics, especially geometry. This mini-symposium plans to invite many of the top researchers in the field to present their latest results. We hope to have two sessions of 5 speakers each.

Jeff Dinitz (University Of Vermont), Clement Lam (Concordia University), Brett Stevens (Carleton University), Doug Stinson (U. of Waterloo), John van Rees (U. of Manitoba).

Designs and Codes II
Org: Peter Dukes (University of Victoria)

This session is an extension of Designs and Codes I''. The focus is on combinatorial designs and error-correcting codes, with special emphasis on connections between those subjects.

Peter Dukes (University of Victoria), Hadi Kharaghani (University of Lethbridge), Esther Lamken (California Institute of Technology), David Pike (Memorial University of Newfoundland), Alex Rosa (McMaster University).

Edge-Colouring and Structures on Line Graphs
Org: Jessica McDonald (Simon Fraser University)

Different variations of edge-colourings are bound together by the structure of line graphs and the techniques that this structure suggests. Alternating paths play a vital role here, with current progress towards the famous Goldberg-Seymour Conjecture proceeding principally via the method of Tashkinov trees (a sophisticated selection of alternating paths). In this session we shall hear about such progress, as well as recent results on important variants of chromatic index, including circular chromatic index and acyclic list chromatic index.

Luis Goddyn (Simon Fraser University), Andrew King (Columbia University), Oguz Kurt (The Ohio State University), Jessica McDonald (Simon Fraser University), Diego Scheide (Simon Fraser University).

Embeddings and Geometric Representations of Graphs
Org: Debra Boutin (Hamilton College)

This mini-symposium will explore the connections between abstract graphs and geometry (broadly defined). Some of the topics that naturally arise in this area are: interval graphs (vertices correspond to intervals of the real line, edges to intersecting intervals) or rectangle visibility graphs (vertices correspond to rectangles in the plane, edges to rectangle that can \lq\lq see" each other), geometric graphs (straightline drawings of graphs in the plane), graphs embedded on surfaces (edges don't cross and are not necessarily straight).

Dan Archdeacon (University of Vermont), Andrew Beveridge (Macalester College), Sally Cockburn (Hamilton College), Alice Dean (Skidmore College), Mark Ellingham (Vanderbilt University).

Exact Combinatorics with Applications in Physics
Org: Marni MISHNA (Simon Fraser University)

Physics is a rich source of inspiration for discrete mathematics. This minisymposium will focus on combinatorial work related to physics which is exact in nature rather than purely statistical. Such work can be quite varied both combinatorially and physically, but is unified in flavour and in the interplay of the fields. It is exciting because frequently not only does the physics inform the combinatorics, but also the combinatorics can be brought to bear nontrivially on interesting physical problems. Important examples include renormalization Hopf algebras in quantum field theory and exact enumeration of self avoiding walks in polymer physics.

Loic Foissy (Universite Reims), Philippe Nadeau (University of Vienna), Chris Soteros (University of Saskatoon), Stu Whittington (University of Toronto), Karen Yeats (Simon Fraser University).

Finite Fields in Combinatorics I
Org: Daniel Panario (Carleton University)

In this minisymposium, several topics of combinatorics where finite fields play an important role are presented. The talks show the use of finite fields to construct combinatorial objects and to prove interesting results in areas such as designs, graphs, latin squares, codes and sequences, finite geometries, among others.

Tim Alderson (University of New Brunswick (Saint John)), Shonda Gosselin (University of Winnipeg), Petr Lisonek (Simon Fraser University), Daniel Panario (Carleton University), David Thomson (Carleton University).

Finite Fields in Combinatorics II
Org: Daniel Panario (Carleton University)

In this minisymposium, several topics of combinatorics where finite fields play an important role are presented. The talks show the use of finite fields to construct combinatorial objects and to prove interesting results in areas such as designs, graphs, latin squares, codes and sequences, finite geometries, among others.

Aiden Bruen (University of Calgary), Sudhir Ghorpade (Indian Institute of Technology), Kai-Uwe Schmidt (Simon Fraser University), Brett Stevens (Carleton University), Qiang Wang (Carleton University).

Org: Aidan Roy and Ada Chan (University of Waterloo and York University)

A {\em generalized Hadamard matrix} is a complex $n \times n$ matrix $H$ such that all entries of $H$ have the same absolute value, and $HH^* = nI$. Like real Hadamard matrices, generalized Hadamards often have interesting combinatorial properties and constructions. However, they also have a number of important applications. In quantum information theory, certain generalized Hadamards correspond to optimal tomographic measurements. In the theory of Type II matrices, they are closely connected to association schemes. In this minisymposium, we bring together people from various backgrounds to discuss the latest results and encourage communication between quantum information theorists and combinatorialists.

Robert Craigen (University of Manitoba), Hadi Kharaghani (University of Lethbridge), Aidan Roy (University of Waterloo), Alyssa Sankey (University of New Brunswick).

Geometric Representations of Graphs I
Org: Stefan Felsner (Technische Universitaet Berlin)

Visualizations and representations of graphs by means of intersections or contacts of geometric objects have been widely investigated. Classical examples are interval graphs and Koebe circle representations. When representations are given they can sometimes be exploited in optimization problems. In many instances these problems are hard for general graphs but become polynomial-time solvable when restricted to intersection or contact graphs with a given representations. Another class of problems is to compute the representation or to decide whether it exists. In this minisymposium we highlight some recent developments in this active area at the intersection of graph theory and discrete geometry.

Matthew Francis (University of Toronto), Jan Kratochvil (Charles University, Prague), Tobias Müller (CWI, Amsterdam), Torsten Ueckerdt (Technische Universitaet Berlin), Sue Whitesides (University of Victoria, BC).

Geometric Representations of Graphs II
Org: Jan Kratochvil (Charles University, Prague, Czech republic)

Visualizations and representations of graphs by means of intersections or contacts of geometric objects have been widely investigated. Classical examples are interval graphs and Koebe circle representations. When representations are given they can sometimes be exploited in optimization problems. In many instances these problems are hard for general graphs but become polynomial-time solvable when restricted to intersection or contact graphs with a given representations. Another class of problems is to compute the representation or to decide whether it exists. In this minisymposium we highlight some recent developments in this active area at the intersection of graph theory and discrete geometry.

Stefan Felsner (Technische Universitaet, Berlin, Germany), Daniel Gonçalves (LIRMM, Montpellier, France), Anna Lubiw (University of Waterloo), George Mertzios (University of Haifa, Israel), Marcus Schaefer (DePaul University, Chicago, U.S.A.).

Graph Searching
Org: Anthony Bonato (Ryerson University), Nancy Clarke (Acadia University) and Boting Yang (University of Regina)

In graph searching a set of searchers pursue intruders in a two-player game played on a graph. The rules of the game may vary according to the capabilities of the players such as relative speed, sensor capabilities, or visibility. There has been much recent interest in graph searching, resulting in a wealth of structural, algorithmic, and probabilistic results. The main aim of the minisymposium (co-organized with Nancy Clarke and Boting Yang) is to bring together leading researchers in the field. The proposed speakers will cover such topics as Cops and Robbers and its variants, sweeping, graph cleaning, and firefighting.

Nancy Clarke (Acadia), Danny Dyer (Memorial), Geňa Hahn (Montréal), Gary MacGillivray (Victoria), Richard Nowakowski (Dalhousie).

Hypergraph Decompositions
Org: Shonda Gosselin (University of Winnipeg)

This minisymposium showcases recent results involving hypergraph decompositions and their relation to combinatorial designs. We define and construct cyclic decompositions of complete uniform hypergraphs and complete multipartite hypergraphs, and examine their connection to both self-complementary graphs and large sets of designs. We also investigate covering and packing versions of Peter Cameron's generalized $t$-designs, which correspond to special coverings and packings of hypergraphs.

Robert Bailey (University of Regina), Andrea Burgess (Ryerson University), Shonda Gosselin (University of Winnipeg), Mateja Sajna (University of Ottawa), A. Pawel Wojda (AGH University of Science and Technology, Krakow, Poland.).

Optimal Design of Experiments
Org: Julie Zhou (University of Victoria)

The goal of this session is to bring together leading researchers in the areas of optimal design of experiments to exchange and discuss research ideas, and to encourage interactions between researchers in statistics and researchers in discrete mathematics. Research results in combinatorics and numerical algorithms are very useful to construct optimal designs. Five leading researchers in optimal design of experiments have tentatively agreed to give talks in this proposed session.

Ching-Shui Cheng (University of California, Berkeley), John Stufken (University of Goergia), Boxin Tang (Simon Fraser University), Weng Kee Wong (University of California, Los Angeles), Jane Ye (University of Victoria).

Spectral Graph Theory
Org: Bojan Mohar and Steve Kirkland (Simon Fraser University)

Spectral graph theory is an important part of discrete mathematics with applications in many areas such as computer science, chemistry, network design and coding theory. One of the main goals of the theory is to deduce the principal properties of a graph from the spectral information furnished by one or more of the matrices associated with it. This minisymposium will showcase some of such connections and their applications.

Azhvan Sheikh Ahmady (Simon Fraser University), Steve Butler (University of California, Los Angeles), Sebastian Cioaba (University of California, San Diego), Bojan Mohar (Simon Fraser University), Vlado Nikiforov (University of Memphis).

Structured Graphs and Algorithms
Org: Jing Huang and Gary MacGillivray (University of Victoria)

Combinatorial problems that are hard for general graphs are sometimes efficiently solvable for graphs belonging to classes like chordal, bi-arc, interval graphs, local tournaments, and the like. In some instances, for example the list homomorphism problem, it is precisely membership in such a class that distinguishes the polynomial and NP-complete instances of the problem. The speakers in this minisymposium will present results on the structure of graphs belonging to various special classes, and the complexity of combinatorial problems on such graphs.

Jorgen Bang-Jensen (University of Southern Denmark), Ross Churchley (University of Victoria), Mathew Francis (Charles University), Jing Huang (University of Victoria), Ragnar Nevries (University of Rostock).

Handling of online submissions has been provided by the CMS.