Invited speakers
Ron Aharoni, Technion - Israel Institute of Technology.
Beyond Hall's Theorem - independent systems of representatives
Hall's theorem provides a necessary and sufficient condition for the existence of an injective choice function for a given collection of sets \( V_i \). In a more general setting, some structure is given on \( \bigcup V_i \) and the requirement is added that the range of the choice function belongs to this structure. For example, that the range is independent in some given matroid (this is the setting of Rado's theorem) or independent in some given graph on \( \bigcup V_i \). The elements chosen are called then an "independent system of representatives" (ISR). Many problems can be formulated in this setting - for example coloring of graphs, or list coloring. ISR problems are typically NP-hard, so no necessary and sufficient condition is expected to be found for their existence, but some tools - topological and algebraic - have been developed that provide sufficient conditions. The talk is a survey of these methods, and of applications of ISR's.
Marston Conder, University of Auckland.
Graph symmetries
This will be a wide-ranging survey of a number of things about symmetries of graphs, including types of symmetry and associated properties, both global and local, similar issues for graph embeddings, theorems on maximum symmetry, constructions for graphs and maps with a high degree of symmetry subject to various constraints, and so on. These will be accompanied by lots of examples and illustrations. I will also mention some recent developments and open problems.
Daniel Horsley,
Monash University.
Embeddings of Steiner triple systems - best possible and better
A Steiner triple system \( (V,\mathcal{B}) \) of order \( v \) is a set \( V \) of \( v \) points together with a collection \( \mathcal{B} \) of triples of those points such that each pair of points appears in exactly one triple. It is known that these exist if and only if \( v \equiv 1,3 \;({\rm mod}\;6) \). If instead each pair of points appears in at most one triple we have a partial Steiner triple system of order \( v\). A partial Steiner triple system \( (U,\mathcal{A}) \) has an embedding of order \( v \) if there is a Steiner triple system \( (V,\mathcal{B}) \) of order \( v \) such that \( U \subseteq V \) and \( \mathcal{A} \subseteq \mathcal{B} \). In 1978 Lindner conjectured that every partial Steiner triple system of order \( u \) has an embedding of order \( v \) for each \( v \geq 2u+1 \) such that \( v \equiv 1,3 \;({\rm mod}\;6) \). After many partial results, a complete proof of this conjecture was obtained in 2009. This result is best-possible in the sense that for each \( u \geq 9 \) there is a partial Steiner triple system of order \( u \) that does not have an embedding of order smaller than \( 2u+1 \). Of course, many partial Steiner triple systems do have embeddings of order smaller than \( 2u+1 \). Much less is known about these embeddings, and there is a wide range of interesting questions concerning them. In this talk I will give an overview of the problem of embedding partial Steiner triple systems and discuss some recent results on embeddings of order smaller than \( 2u+1 \).
Christine O'Keefe, CSIRO.
Confidentiality, privacy and combinatorics
Vast amounts of data are now being generated from scientific research, observational projects, instruments and sensors of many kinds. The need to protect the privacy of individuals in the context of health databases is well-recognised, however confidentiality can also be an issue with business datasets, which often contain commercially sensitive information.
In this talk I will give an introduction to the area of confidentiality protection, including discussing a range of traditional and emerging approaches to disclosure control. I will focus in particular on the use of combinatorial concepts and techniques.
Chris Rodger,
Auburn University.
Enclosing and existence of cycle systems
An \( m \)-cycle system of \( G \) is a partition of the edges of \( G \), each element of which induces an \( m \)-cycle. We consider two scenarios.
If \( G \) happens to be \( \lambda K_v \) then this system said to be an \( m \)-cycle system of order \( v \) and index \( \lambda \). The enclosing problem is to decide when there exists an \( m \)-cycle system of order \( v + u \) and index \( \lambda + \mu \) that contains an \( m \)-cycle system of order \( v \) and index \( \lambda \) in the case where \( u > 0 \) and \( \mu > 0 \) . As one might expect, the problem is more difficult when \( m \) is odd and when \( u \) is small. Work towards solving this problem when \( m \leq 5 \) will be discussed. (If \( \mu = 0 \) then this would be called an embedding.)
If \( G \) can be formed from vertex disjoint copies of \( \lambda_1K_n \) by joining each vertex in each copy to each vertex in each other copy with \( \lambda_2 \) edges then the system is said to be an \( m \)-cycle system with two associate classes. So the existence problem for these graphs involves 4 parameters! It has been solved when \( m \) is 3, 4 or \( |V(G)| \). Other results concern cycle systems of this graph that are required to have extra properties such as being resolvable or gregarious (that is, the vertices in each cycle are required to be spread out as evenly as possible among the copies of \( \lambda_1K_n \)). As time permits, some or all of these results will be discussed.
Frank Ruskey,
University of Victoria, BC.
The mysterious nature of nested recurrence relations
In the 1979 Pulitzer Prize winning book "Gödel, Escher, Bach: an Eternal Golden Braid", Douglas R. Hofstadter introduced the recurrence relation \[ Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2)) \] with \( Q(1) = Q(2) = 1 \). We call this a nested recurrence relation because it has a sub-expression of the form \( \ldots Q(\ldots Q(\ldots)\ldots)\ldots \). Other than composition, the only operations that are used are addition and subtraction.
Some nested recurrence relations have a solution and combinatorial interpretations, while others seemingly do not. For example it is still unknown whether \( Q(n) \) is defined for all \( n \). On the other hand, for the closely related recurrence \[ T(n) = T(n-1-T(n-1)) + T(n-2-T(n-2)) \] with \( T(1) = T(2) = 1 \), the number \( T(n) \) counts the maximum number of leaves at the lowest level in a binary tree with \( n \) nodes. Some nested recurrence relations are undecidable in the sense that there is no algorithm to decide whether, given a set of initial conditions, they are well-defined for all \( n > 0 \). The purpose of this talk is to introduce nested recurrence relations, discuss some of the known results, and present tantalizing open problems.
This is joint work with Marcel Celaya, Steve Tanny, Brad Jackson, Alejandro Erickson and Bram Isgur. <\p>
Carsten Thomassen, Technical University of Denmark.
The weak circular flow conjecture and applications
Tutte's 3-flow conjecture says that every 4-edge-connected graph has an orientation such that, for each vertex \( x \), the indegree of \( x \) equals the outdegree of \( x \) modulo 3. In 1988 Jaeger suggested a weaker conjecture obtained by replacing 4 by a larger (universal) number and called that the weak 3-flow conjecture. He also suggested a stronger conjecture, called the circular flow conjecture. In this talk we indicate a proof of the weak circular flow conjecture (and hence also the weak 3-flow conjecture) and discuss its applications to graph decomposition, group flow, and factors modulo \( k \).
Anders Yeo,
University of Johannesburg.
Fixed-parameter tractability above lower bounds
A problem is fixed-parameter tractable (FPT) if given a parameter \( k \) (often, but not always, related to the solution size) there is an algorithm of complexity \( O(f(k) n^c) \) for instances of size \( n \), where \( f(k) \) is a function and \( c \) is a constant. Therefore, if \( k \) is considered a constant then the problem is polynomial and the exponent does not depend on \( k \). For FPT to be a useful tool we want the parameter, \( k \), to be small. Therefore if there is a (tight) lower bound on the solution size, then a recent approach is to parameterize above this lower bound. For example it is known that one can always satisfy $7/8$'th of all clauses in 3-SAT. So one question could be if we can satisfy \( k \) clauses more than this.
In this talk we will give an introduction to FPT, using a problem from the area of Information Security as an example. This is followed by a discussion of the following two problems.
Satisfying linear equations over \( \mathbb{F}_2 \): We are given variables \( x_1,\ldots ,x_n \) and \( m \) equations of the form \( \sum_{i \in I}x_i = b\) (modulo 2), where \( x_i,b \in \{0, 1\} \) and \( I\subseteq \{1,2,\ldots,n\} \) and each equation has a positive integral weight. Deciding the maximum weight of equations that can be simultaneously satisfied is NP-hard.
Let \( W \) be the sum of all weights. As \( W/2 \) is the average weight of a random solution, there always exists a solution of weight \( W/2 \). We outline how to show that it is FPT to decide if there is a solution of weight \( W/2+k \), where \( k \) is the parameter.
Max-\( r \)-SAT: We are given a formula in conjunctive normal form (CNF) with \( m \) clauses, such that each clause contains \( r \) variables. We want to decide what is the maximum number of clauses we can simultaneously satisfy. As \( (1-2^{-r})m \) is a lower bound on the number of clauses that can be satisfied we will consider the problem of deciding if we can satisfy \( (1-2^{-r})m +k \) clauses.
We will outline how to use the obtained result on satisfying linear equations over \( \mathbb{F}_2 \) (using pseudo-boolean functions as a stepping stone) in order to get FPT results for Max-\( r \)-SAT.
