39th
Australasian Conference on Combinatorial
Mathematics
and
Combinatorial Computing
The
University of
Queensland
| Home | About the speakers | Accommodation | Local information | Program | Student Information | Registration | Abstracts |
Peter
Cameron
Four precious jewels
I will talk about some aspects of four remarkable objects: the countable random graph (or Rado graph), the rational numbers (as ordered set), the Urysohn metric space, and the pseudo-arc. These objects appear in many different areas of mathematics, but they have certain features in common: they can be constructed as suitable limits of finite combinatorial structures; many of their properties can be investigated by combinatorial techniques; and they provide mechanisms for some very interesting interactions between combinatorics and other parts of mathematics (for example, the KPT theorem connecting Ramsey theory with topological dynamics).
Four precious jewels
I will talk about some aspects of four remarkable objects: the countable random graph (or Rado graph), the rational numbers (as ordered set), the Urysohn metric space, and the pseudo-arc. These objects appear in many different areas of mathematics, but they have certain features in common: they can be constructed as suitable limits of finite combinatorial structures; many of their properties can be investigated by combinatorial techniques; and they provide mechanisms for some very interesting interactions between combinatorics and other parts of mathematics (for example, the KPT theorem connecting Ramsey theory with topological dynamics).
Saad
El-Zanati
On Decomposing Regular Graphs and Multigraphs into Isomorphic Trees and Forests
Let \( H \) and \( G \) be graphs or multigraphs such that \( G \) is a subgraph of \( H \). A \( G \)-decomposition of \( H \) is a set \( \Delta=\{G_1,G_2,\dots,G_t\} \) of pairwise edge-disjoint subgraphs of \( H \) each of which is isomorphic to \( G \) and such that each edge of \( H \) occurs in exactly one \( G_i \). Graham and Häggkvist have conjectured that every tree with \( n \) edges decomposes every \( 2n \)-regular graph as well as every \( n \)-regular bipartite graph. These conjectures have been confirmed for a small number of cases. We believe the Graham and Häggkvist Conjectures extend to forests with \( n \) edges. We have also recently conjectured that every tree with \( n \) edges decomposes every \( 2n \)-regular multigraph with edge multiplicity at most \( 2 \). In this talk, we report on some recent results related to variations of these conjectures.
On Decomposing Regular Graphs and Multigraphs into Isomorphic Trees and Forests
Let \( H \) and \( G \) be graphs or multigraphs such that \( G \) is a subgraph of \( H \). A \( G \)-decomposition of \( H \) is a set \( \Delta=\{G_1,G_2,\dots,G_t\} \) of pairwise edge-disjoint subgraphs of \( H \) each of which is isomorphic to \( G \) and such that each edge of \( H \) occurs in exactly one \( G_i \). Graham and Häggkvist have conjectured that every tree with \( n \) edges decomposes every \( 2n \)-regular graph as well as every \( n \)-regular bipartite graph. These conjectures have been confirmed for a small number of cases. We believe the Graham and Häggkvist Conjectures extend to forests with \( n \) edges. We have also recently conjectured that every tree with \( n \) edges decomposes every \( 2n \)-regular multigraph with edge multiplicity at most \( 2 \). In this talk, we report on some recent results related to variations of these conjectures.
Nevena
Francetić
Group divisible coverings and related structures
Group divisible coverings, GDCs, are a covering generalization of group divisible designs. More formally, a \( (t,k) \)-GDC of type \( g^u \) is a triple \( (V,\mathcal{G},\mathcal{B}) \), where \( V \) is a set of \( gu \) points, \( \mathcal{G} \) is a partition of \( V \) into \( u \) subsets of size \( g \), called groups, and \( \mathcal{B} \) is a collection of \( k \) subsets of \( V \), called blocks, such that (1) no pair of points belonging to the same group is contained in a block, (2) every set of \( t \) points which intersects \( t \) distinct groups is contained in at least one block. Group divisible coverings are related to many well-studied families of combinatorial designs. For example, group divisible designs, orthogonal and covering arrays, BIBDs, projective planes, \( t \)-designs, and coverings are equivalent to specific families of GDCs. Note that the block size of these well-known combinatorial structures varies in relation to the number of the groups (or points). Here, we consider the block size \( k \) of GDCs to be an integer function of the number of groups \( g \), \( k=k(g) \). We observe how the size and nature of GDCs changes when \( k \) has different orders of magnitude compared to \( g \) and how this impacts the approach to studying GDCs and the related structures.
Group divisible coverings and related structures
Group divisible coverings, GDCs, are a covering generalization of group divisible designs. More formally, a \( (t,k) \)-GDC of type \( g^u \) is a triple \( (V,\mathcal{G},\mathcal{B}) \), where \( V \) is a set of \( gu \) points, \( \mathcal{G} \) is a partition of \( V \) into \( u \) subsets of size \( g \), called groups, and \( \mathcal{B} \) is a collection of \( k \) subsets of \( V \), called blocks, such that (1) no pair of points belonging to the same group is contained in a block, (2) every set of \( t \) points which intersects \( t \) distinct groups is contained in at least one block. Group divisible coverings are related to many well-studied families of combinatorial designs. For example, group divisible designs, orthogonal and covering arrays, BIBDs, projective planes, \( t \)-designs, and coverings are equivalent to specific families of GDCs. Note that the block size of these well-known combinatorial structures varies in relation to the number of the groups (or points). Here, we consider the block size \( k \) of GDCs to be an integer function of the number of groups \( g \), \( k=k(g) \). We observe how the size and nature of GDCs changes when \( k \) has different orders of magnitude compared to \( g \) and how this impacts the approach to studying GDCs and the related structures.
Catherine
Greenhill
Sampling and counting using Markov chains
A Markov chain is a simple stochastic process which is "memoryless": the next state depends only on the current state, not on the entire history. Classical Markov chain theory investigated conditions under which the distribution of the current state of the chain would converge to a unique stationary distribution. About 30 years ago, motivated by applications in statistical physics and computer science, a new question emerged: how quickly does the Markov chain tend to its unique stationary distribution, as a function of the size of the state space?
I will aim to give a flavour of some of the breakthrough results in the use of Markov chains for sampling and counting, the methods which have been used to prove them, and connections with statistical physics.
Sampling and counting using Markov chains
A Markov chain is a simple stochastic process which is "memoryless": the next state depends only on the current state, not on the entire history. Classical Markov chain theory investigated conditions under which the distribution of the current state of the chain would converge to a unique stationary distribution. About 30 years ago, motivated by applications in statistical physics and computer science, a new question emerged: how quickly does the Markov chain tend to its unique stationary distribution, as a function of the size of the state space?
I will aim to give a flavour of some of the breakthrough results in the use of Markov chains for sampling and counting, the methods which have been used to prove them, and connections with statistical physics.
Penny
Haxell
Matchings in tripartite hypergraphs
A matching in a hypergraph is a set of disjoint edges. It is a well-known difficult problem to give good lower bounds on the maximum size of a matching in a hypergraph in terms of other natural parameters. Here we focus on the special case of tripartite hypergraphs: those for which the vertex set can be partitioned into three parts, such that each edge contains exactly one vertex from each part. If a tripartite hypergraph is \( r \)-regular (meaning that each vertex is in exactly \( r \) edges) with \( n \) vertices in each class then it has a matching of size at least \( n/2 \), and this is tight for certain special hypergraphs. We investigate how this bound can be improved for all other hypergraphs.
Matchings in tripartite hypergraphs
A matching in a hypergraph is a set of disjoint edges. It is a well-known difficult problem to give good lower bounds on the maximum size of a matching in a hypergraph in terms of other natural parameters. Here we focus on the special case of tripartite hypergraphs: those for which the vertex set can be partitioned into three parts, such that each edge contains exactly one vertex from each part. If a tripartite hypergraph is \( r \)-regular (meaning that each vertex is in exactly \( r \) edges) with \( n \) vertices in each class then it has a matching of size at least \( n/2 \), and this is tight for certain special hypergraphs. We investigate how this bound can be improved for all other hypergraphs.
Jonathan
Jedwab
2048 Ideas for Turning Combinatorial Research into a Game
What could be achieved if combinatorial research were as enticing and addictive as playing a great computer game like 2048? What are the key design attributes of such a "research game"? I’ll explore these questions in light of some recent joint research projects with students, exposing aspects of the research process that are usually omitted from the final published version. Prior addiction to 2048 will not be assumed.
2048 Ideas for Turning Combinatorial Research into a Game
What could be achieved if combinatorial research were as enticing and addictive as playing a great computer game like 2048? What are the key design attributes of such a "research game"? I’ll explore these questions in light of some recent joint research projects with students, exposing aspects of the research process that are usually omitted from the final published version. Prior addiction to 2048 will not be assumed.
Gordon
Royle
Graph homomorphisms, endomorphisms and cores
A homomorphism from a graph \( G \) to a graph \( H \) is a mapping \( \varphi: V(G) \to V(H) \), not necessarily injective, that maps edges of \( G \) to edges of \( H \). Homomorphisms into complete graphs are the same as graph colourings, and many colouring-type parameters of graphs can be defined as the existence of homomorphisms into other specific families of graphs. Homomorphic equivalence (that is, the existence of homomorphisms in both directions between two graphs) is an equivalence relation, and each equivalence class contains a unique smallest graph, called a core (or the core of any of the graphs in the equivalence class). If a graph is highly structured, then the core often inherits some of this structure - for example, cores of vertex-transitive graphs are vertex-transitive, but the full extent to which "vertex-transitive" can be replaced by other properties is not known. In this talk, I will discuss a number of results and problems related to graph homomorphisms, endomorphisms (i.e., homomorphisms from a graph to itself) and cores.
Graph homomorphisms, endomorphisms and cores
A homomorphism from a graph \( G \) to a graph \( H \) is a mapping \( \varphi: V(G) \to V(H) \), not necessarily injective, that maps edges of \( G \) to edges of \( H \). Homomorphisms into complete graphs are the same as graph colourings, and many colouring-type parameters of graphs can be defined as the existence of homomorphisms into other specific families of graphs. Homomorphic equivalence (that is, the existence of homomorphisms in both directions between two graphs) is an equivalence relation, and each equivalence class contains a unique smallest graph, called a core (or the core of any of the graphs in the equivalence class). If a graph is highly structured, then the core often inherits some of this structure - for example, cores of vertex-transitive graphs are vertex-transitive, but the full extent to which "vertex-transitive" can be replaced by other properties is not known. In this talk, I will discuss a number of results and problems related to graph homomorphisms, endomorphisms (i.e., homomorphisms from a graph to itself) and cores.
Charles
Semple
Counting Phylogenetic Networks
The number of phylogenetic (evolutionary) trees on \( \ell \) taxa is a classical result in mathematical phylogenetics dating back to Schröder's work in 1870. This result also gives the number of such trees on \( n \) labelled vertices. In contrast, the number of phylogenetic networks on \( n \) labelled vertices is unknown. In this talk, we provide some answers to the problems of counting the numbers of phylogenetic networks. This is joint work with Colin McDiarmid and Dominic Welsh (University of Oxford).
Counting Phylogenetic Networks
The number of phylogenetic (evolutionary) trees on \( \ell \) taxa is a classical result in mathematical phylogenetics dating back to Schröder's work in 1870. This result also gives the number of such trees on \( n \) labelled vertices. In contrast, the number of phylogenetic networks on \( n \) labelled vertices is unknown. In this talk, we provide some answers to the problems of counting the numbers of phylogenetic networks. This is joint work with Colin McDiarmid and Dominic Welsh (University of Oxford).