**Asymptotic mixing times of the Swendsen-Wang process for the Potts model on the complete graph**

*Discrete Structures and Algorithms (Seminar)*

**by **Tim Garoni

**Institution: **Monash University

**Date: **22/05/2013 2:30pm

**Abstract: **The Potts model is a natural generalization of the well-known Ising model of statistical mechanics, and is intimately related to the Tutte polynomial in algebraic graph theory. The Swendsen-Wang process is a finite Markov chain which has revolutionized the way in which Monte Carlo studies of the Potts model, and many related models, are performed. We will discuss the Swendsen-Wang process for the Potts model with $q \ge 3$ states on the complete graph on $n$ vertices, and obtain the large $n$ asymptotics of the mixing time as a function of temperature. The mixing time is exponentially large in $n$ throughout a non-trivial neighbourhood of the equilibrium transition temperature. Strictly outside this neighbourhood, in the high and low temperature regimes, the mixing time is $O(\log n)$, while at the left boundary it exhibits the non-trivial power-law scaling $\Theta(n^{1/3})$. We will sketch the proof of this result, and (time permitting) discuss how our results might be extended to study mixing times of related processes. No prior knowledge of statistical mechanics will be assumed.

**Spectral theory: hypergraphs and lattice models**

*Discrete Structures and Algorithms (Seminar)*

**by **Zuhe Zhang

**Institution: **The University of Melbourne

**Date: **26/04/2013 2:15pm

**Abstract: **I will first present what I have obtained during the first year of my PhD study. The work is about the application of spectral theory on graphs and lattice models. It includes the investigation of the resistance distance, energy, dimer problem, spanning trees and expansion property of clique-inserted-lattices, the entropy of hard-core model and the spectrum of the subdivison-vertex join and subdivsion-edge join of regular graphs. I will then list some research topics for next two years, focusing on spectral hypergraph theory, that is, studying hypergraphs by using the properties of associated hypermatrices.

**Self-similar Group Actions**

*Discrete Structures and Algorithms (Seminar)*

**by **Tian Sang

**Institution: **The University of Melbourne

**Date: **24/04/2013 11:00am

**Abstract: **Self-similar group actions capture the idea of a group action that is repeated at all scales. This is achieved by considering actions on a rooted tree such that the action of the group repeats at all levels of the tree. Self-similar groups are defined based on the automorphisms of rooted binary trees, and one way to describe this is by an automaton. When we have a self-similar group acting on a binary tree, the associated Schreier graphs help us visualize the group structure. The Schreier graphs together give us a self-similarity graph, which gives interesting insights on geometric group theory, such as the hyperbolicity of the graph and contracting of the group.
This was the Vacation Scholarship project that I worked on with my supervisor Lawrence Reeves last summer. In this talk, I will explain how the self-similar group and self-similarity graph were defined and how to construct Schreier graphs from the given automaton for some concrete examples. I also hope there will be enough time for me to show some Schreier graphs I generated by Python and Sage, and how they provide insights on group structure.

**The number of labeled connected graphs on $n$ vertices modulo a prime power**

*Discrete Structures and Algorithms (Seminar)*

**by **Arun Mani

**Institution: **The University of Melbourne

**Date: **10/04/2013 2:30pm

**Abstract: **We will state and prove some recurrent congruences for the sequence $(c(n) : n \mbox{ a positive integer})$, where $c(n)$ denotes the number of labeled connected graphs on $n$ vertices. In particular, for an odd prime $p$ and positive integers $n$ and $k$, we will show $c(n+p^k) \equiv 2^{(p^k - p^{k-1})/2} c(n+p^{k-1})~ {\rm mod}~{p^k}$. This is joint work with Douglas Stones (Dalhousie University, Canada).

**Mechanism Design without Money for Obnoxious Facility Games**

*Discrete Structures and Algorithms (Seminar)*

**by **Yukun Cheng

**Institution: **Zhejiang University, and Zhejiang University of Finance and Economics

**Date: **27/03/2013 2:30pm

**Abstract: **We will talk about an obnoxious facility game on a network, where the facility is undesirable and all agents try to be as far away from the facility as possible, so that an agent's utility can be measured by the distance from the facility. We will also discuss the obnoxious facility game with a bounded service range on a path, where each facility is not only undesirable but also has a service radius $r$. Thus each agent tries to be far away from the facilities, but still to be served by a facility. In other words, the distance between an agent and her nearest facility is at most $r$ and the utility of an agent is defined as this distance. In a deterministic or randomized mechanism, based on the addresses reported by the selfish agents, the locations or the location distributions of facilities are determined. The aim of the mechanisms is to maximize the obnoxious social welfare, namely the total utilities of all agents. The objective of each agent is to maximize her own utility and she may lie if, by doing so, more benefit can be obtained. A mechanism is called strategy-proof if it enforces all agents to report their true locations. We are interested in strategy-proof mechanisms without money that can be used to decide the facility locations so that the obnoxious social welfare is maximized.
We made the first attempt to studying the obnoxious facility game without or with a bounded service range on different networks and provided different deterministic and randomized mechanisms with provable approximation ratios. Lower bounds on any deterministic strategy-proof mechanism for some networks are also obtained. We will discuss these results and introduce some characterizations of the strategy-proof deterministic mechanisms for different networks.

**The Hamiltonian Cycle Problem, Markov Chains and Optimization**

*Discrete Structures and Algorithms (Seminar)*

**by **Professor Jerzy A. Filar

**Institution: **Flinders University

**Date: **18/03/2013 9:00am

**Abstract: **We consider the famous Hamiltonian cycle problem (HCP) embedded in a Markov decision process (MDP). More specifically, we consider the HCP as an optimization problem over the space of occupational measures induced by the MDP’s stationary policies. In recent years, this approach to the HCP has led to a number of alternative formulations and algorithmic approaches involving researchers from a number of countries. In this lecture we focus on a specific embedding due to E. Feinberg from SUNY at Stony Brook. The latter leads to a suitably constructed parametrized polytope of discounted occupational measures that can be used as a domain where Hamiltonian solutions can be sought. It is known that whenever a given graph possesses Hamiltonian cycles, these correspond to certain extreme points of that polytope. It can be demonstrated that a relatively small number of additional constraints and a judicious choice of the value of the discount parameter can ensure that Hamiltonian solutions are no longer rare among extreme points of this modified sub-polytope of occupational measures. The latter observation leads to a promising random walk algorithm on the extreme points of that sub-polytope. We present a conjecture concerning the algorithmic complexity of this algorithm. In addition, we consider the limiting - parameter free - polyhedral region that can serve as a basis for determining non-Hamiltonicity of cubic graphs. Numerical results indicate that determining non-Hamiltonicity of a great majority of non-Hamiltonian cubic graphs is likely to be a problem of polynomial complexity despite the fact that HCP is known to be NP-complete already for cubic graphs.

*For more information: *This is a joint seminar with the Applied Probability Group.
To find the location of the Doug McDonell building, click:
http://maps.unimelb.edu.au/parkville/building/168

**Spectral properties of graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Xiaogang Liu

**Institution: **The University of Melbourne

**Date: **13/02/2013 10:00am

**Abstract: **Computing the spectra of graphs is a fundamental and difficult problem in spectral graph theory. During my Ph.D. I will focus on computation and estimation of the spectra of some families of graphs.
In this talk, I will first talk about what I have obtained during the first year of my Ph.D. I will then discuss some research problems that I plan to study in the next two years.
This is my Ph.D. confirmation presentation.

**Cubic Plane Graphs on a Given Point Set**

*Discrete Structures and Algorithms (Seminar)*

**by **Dr Jens Schmidt

**Institution: **Max-Planck-Institut fur Informatik

**Date: **03/10/2012 1:00pm

**Abstract: **Let P be a set of \(n \geq 4\) points in the plane that is in general position and such that n is even. We investigate the problem whether there is a cubic plane straight-line graph on P. Based on a reduction to the existence of certain diagonals of the boundary cycle of the convex hull of P, we give the first polynomial-time algorithm; the algorithm is constructive and runs in \(O(n^3)\) time. This is joint-work with Pavel Valtr.

**Extremal Graph Theory for Book Embeddings**

*Discrete Structures and Algorithms (Seminar)*

**by **Jessica McClintock

**Institution: **The University of Melbourne

**Date: **26/09/2012 1:00pm

**Abstract: **A "book-embedding" of a graph consists of a linear ordering of the vertices, with the edges partitioned into sets such that no edges in the same set cross. The ordering of vertices is referred to as the "spine" of the book, while the sets of non-crossing edges are called "pages". The minimum number of pages in a book-embedding of a given graph is the "pagenumber" of that graph. Book-embeddings are also commonly referred to as "stack-layouts", as they model operations on a stack. Many of the applications of book-embeddings arise from this relation.
After introducing some of the concepts relevant to the study of book-embeddings and discussing some of their applications, we will describe some of the main results on the pagenumber for classes of graphs, with particular attention being given to results on the pagenumber of planar graphs. We will then give a brief discussion of extremal graph theory, along with some results from this field that consider the extremal graph size with regards to other graph invariants, before discussing extremal results with regards to the pagenumber of graphs.
The original results of this thesis consider "edge-maximal book-embeddings", which are book-embeddings to which no edge can be added without increasing the pagenumber. We prove that the minimum number of edges in a 3-page edge-maximal book-embedding with n vertices is \(\lceil{7n/2}\rceil\). We give an upper bound of \((k+4)n/2\) and a lower bound of \(\sqrt{kn/2}\) on the minimum number of edges in a k-page edge-maximal book-embedding.

**The Computational Geometry of Comparing Shapes**

*Discrete Structures and Algorithms (Seminar)*

**by **Professor Helmut Alt

**Institution: **Freie Universitat Berlin

**Date: **19/09/2012 1:00pm

**Abstract: **The lecture will be a survey on methods from computational geometry for comparing patterns and shapes that we developed within our work group at Freie Universitaet Berlin. In particular, we will present the ideas and complexity considerations for the computation of two distance measures for shapes, namely the Hausdorff distance and the Frechet distance. Whereas the former is easier to compute, the latter better captures the similarity of shapes as perceived by human observers. Whereas the Frechet distance of curves is efficiently computable, for surfaces it seems computationally intractable and, in fact, is not even known to be computable at all. We will close with some application examples of this theory.

**The epsilon-net story**

*Discrete Structures and Algorithms (Seminar)*

**by **Professor Janos Pach

**Institution: **Renyi Institute (Budapest) and EPFL (Lausanne)

**Date: **29/08/2012 1:00pm

**Abstract: **In 1986, Haussler and Welzl introduced the notion of epsilon-nets and adapted a theorem of Vapnik-Chervonenkis to establish the existence of small epsilon-nets in hypergraphs (range spaces) of small "dimension." Since then epsilon-net theory has been successfully applied in machine learning, in discrete and computational geometry and elsewhere. It has been an outstanding open problem to determine the size of the smallest epsilon-net that can be found in every hypergraph. We summarize the last chapter of the story, and describe some recent geometric constructions found by the speaker and by Gabor Tardos.

**Describing lengths of walks in directed graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Anthony Widjaja Lin

**Institution: **Oxford University

**Date: **02/05/2012 10:00am

**Abstract: **Consider an arbitrary directed graph G and fix a source node s and a sink node t. Is there a nice way to describe the set of *lengths* of walks from s to t? This is a subcase of a more general problem from the theory of automata on words (a subarea of computer science) with a simple graph-theoretic formulation. In this talk, we will show that the set of lengths of walks from s to t can be described as a union of a small number of arithmetic progressions (i.e. sets of the form {a+bn : n is a natural number}), each of small size. [More precisely, a union of quadratically many arithmetic progressions with offsets quadratic in the size of G and periods linear in the size of G.] Furthermore, the computation of this set can be done in polynomial time. This original proof of this result, which is called
Chrobak-Martinez Theorem, has a subtle mistake. The talk will describe
the corrected proof of the result.

**Correlation inequalities for the Tutte polynomial of a graph (continued)**

*Discrete Structures and Algorithms (Seminar)*

**by **Arun Mani

**Institution: **The University of Melbourne

**Date: **18/04/2012 10:00am

**Abstract: **In this final part of this series of talks, I will give a more detailed account of my research on correlation inequalities of the Tutte polynomial of a graph. We will also take a closer look at applying these inequalities to obtain approximations of the asymptotic growth rate of the Tutte polynomial of a two-dimensional square lattice as its dimensions tend to infinity. I will then close with a discussion of the numerous unresolved research problems in the topic.

**Correlation inequalities for the Tutte polynomial**

*Discrete Structures and Algorithms (Seminar)*

**by **Dr Arun Mani

**Institution: **The University of Melbourne

**Date: **04/04/2012 10:00am

**Abstract: **In this second of the two part talk, I will introduce a family of correlation inequalities for the Tutte polynomial of a graph. I will discuss how this arises naturally from fundamental combinatorial questions on a graph. I will then talk about the following topics of my research on these inequalities:
i) theoretical tools to establish these inequalities,
ii) applying the inequalities to obtain approximations for the Potts model partition function in Statistical Mechanics, and
iii) their potential as a general approximation technique for the Tutte polynomial.
Along the way, we will see that there are several interesting fundamental questions on the topic that are still unresolved and very much wide open for further research.

**An introduction to the Tutte polynomial of a graph**

*Discrete Structures and Algorithms (Seminar)*

**by **Dr Arun Mani

**Institution: **The University of Melbourne

**Date: **28/03/2012 10:00am

**Abstract: **The Tutte polynomial of a graph is a two variable polynomial that is of central importance in many counting problems. For example, if $T(G;x,y)$ is the Tutte polynomial of a connected graph $G$, then $T(G;1,1)$ and $T(G;1,2)$ give its number of spanning trees and connected subgraphs, respectively, while $k|T(G;1-k,0)|$ is its number of proper $k$-colourings.
In this first introductory half of a two part talk, I will give an overview of the Tutte polynomial with particular focus on the following three topics:
i) its combinatorial significance,
ii) its role in Statistical Mechanics, and
iii) the computational complexity of computing its coefficients or evaluating it at various points.
These form the background material for my talk the following week, where I will introduce a family of inequalities for the Tutte polynomial and discuss its implications on all three of the above topics.

**Hadwiger's Conjecture for Symmetric Graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Bin Jia

**Institution: **The University of Melbourne

**Date: **21/03/2012 10:00am

**Abstract: **In graph theory, Hadwiger's conjecture states that, every simple graph of chromatic number $t$ has a minor isomorphic to the complete graph $K_t$. My proposed PhD research topic is to verify this conjecture for various families of graphs with certain symmetries. Therefore, my research lies in the intersection of two major disciplines, namely structural and algebraic graph theories. The former discipline is focused on graph coloring and minors, while the latter studies algebraically defined graphs, such as circulant graphs, Cayley graphs and symmetric graphs, etc.

**Wide Containers in Gaussian Networks**

*Discrete Structures and Algorithms (Seminar)*

**by **Muhammad Adib Surani

**Institution: **The University of Melbourne

**Date: **29/02/2012 10:00am

**Abstract: **A Gaussian network is a Cayley graph modelled on a quotient ring of the Gaussian integers. Indeed, many circulant graphs and tori are isomorphic to Gaussian networks, and so this provides a useful algebraic structure with which to study them. Many highly sought after properties in interconnection networks and coding theory (e.g. diameter, shortest paths) can be easily obtained under this framework. The concept of wide containers will also be introduced to unify the properties of connectivity and diameter.

**Stacks, Queues, Deques and their Representation as Graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Prof. Franz Brandenburg

**Institution: **University of Passau, Germany

**Date: **25/01/2012 10:00am

**Abstract: **Stacks and queues are fundamental data structures. They express the LIFO (last-in, first out) and FIFO (first-in, first-out) principles and are the basis for depth first and breadth first search. Stacks and queues are a specialization of a deque, which allows the insertion and removal of objects on its left and right ends. In Java 6 the class Arraydeque implements a deque and is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue. We consider classes of graphs which represent the input-ouput behaviour of these data structures, and call them stack, queue, or deque graphs. Then the input-output actions on a stack are correct if and only if the stack graph is planer. Accordingly, queue graphs have a planar representation on a cylinder and the deque graphs are characterized by planar graphs on the cylinder with additional arches. Hence, we can state: correct if and only if planar. We study properties of the classes of stack, queue and deque graphs, which are subclasses of planar graphs. By Yannakakis result every planar graphs can be represented by four stacks. In particular, one stack graphs are two queue graphs, and one queue graphs are two stack graphs. Our latest result states that in terms of graphs a deque dominates two stacks exactly by the difference between a Hamilton cycle and a Hamilton path in planar graphs. We close with challenging open problems that are related to stacks and queues.

**Vertices of high degree in the preferential attachment tree**

*Discrete Structures and Algorithms (Seminar)*

**by **Graham Brightwell

**Institution: **London School of Economics, UK

**Date: **15/11/2011 11:00am

**Abstract: **The preferential attachment tree is the most basic model of evolving web graphs and social networks. At each stage of the process, a new vertex is added and joined to one of the existing vertices, with each vertex chosen with probability proportional to its current degree. In probability theory, this is also known as a Yule process.
Much is known about this model, including the fact that the numbers of vertices of each small degree follow a ``power law''. Here we study in detail the degree sequence of the preferential attachment tree, looking at the vertices of large degrees as well as the numbers of vertices of each fixed degree.
This is joint work with Malwina Luczak.

**Albertson's conjecture and 5-coloring non-planar graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Janos Barat

**Institution: **Monash University

**Date: **08/11/2011 11:00am

**Abstract: **A graph is planar, if it can be drawn in the plane without edge crossings. It follows from the Euler-formula, that any planar graph has a vertex of degree at most 5. Therefore, using a greedy coloring algorithm, we can trivially color the vertices of a planar graph by 6 colors.
It is still easy to prove that 5 colors suffice. What happens if we allow some edge crossings in the drawing? Can we still 5 color the vertices? Is there any connection between the minimum number of crossings in a drawing of a graph G and its chromatic number? Both of these graph parameters are hard to compute. Still, Mike Albertson formulated a conjecture in 2007 that for any r-chromatic G, the crossing number of G is at least the crossing number of $K_r$, the complete graph on $r$ vertices. This conjecture is a weakening of Hajos conjecture, and it includes the 4 color theorem as a subcase. We will show that this conjecture follows from some known results up to a factor of 4. It is also true for r at most 16, despite the fact that we only know the crossing number of $K_r$ for $r$ at most 12.

**First-Fit chain partitioning of partial orders**

*Discrete Structures and Algorithms (Seminar)*

**by **Gwenael Joret

**Institution: **Université Libre de Bruxelles

**Date: **25/10/2011 11:00am

**Abstract: **By Dilworth's theorem, every partial order P can be partitioned into w chains, where w is the maximum size of an antichain in P (called the
width of P).
A natural greedy algorithm to construct a chain partition of P with few chains is First-Fit: Consider the elements of P in some order and put each element v in the first chain that fits, that is, the first chain C where v is comparable to all elements in C.
It has been known for a long time that First-Fit uses O(w) chains on interval orders of width w, and it was conjectured that this remains
true more generally for partial orders without two incomparable chains
of length k, for fixed k (for k=2, these are exactly the interval orders).
In this talk I will present a proof of this conjecture. This is joint work with Kevin G. Milans (U. South Carolina).

**Untangling Planar Graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Vida Dujmovic

**Institution: **Carleton University, Ottawa, Canada

**Date: **18/10/2011 11:00am

**Abstract: **Problems involving reconfigurations of geometric objects appear in all areas of science and engineering. Motivated by applications in gaming, we study reconfigurations of geometric graphs (that is, straight-line
drawings of graphs with possibly lots of edge crossings). To untangle a
geometric planar graph means to move some of its vertices so that the resulting geometric graph has no crossings. A popular on-line game, called, Planarity, asks a player to untangle a given geometric planar graph. The problem has also been studied in mathematical circles. We
answer an open problem by Pach and Tardos [Discrete Comput. Geom., 2002] by providing the first polynomial lower bound for untangling geometric
planar graphs.

**Small Graph Minors**

*Discrete Structures and Algorithms (Seminar)*

**by **David Wood

**Institution: **The University of Melbourne

**Date: **13/09/2011 11:00am

**Abstract: **A fundamental result in structural graph theory states that every graph with large average degree contains a large complete graph as a minor. We prove this result with the extra property that the minor is "small" with respect to the order of the whole graph. Other related results will be explored. Joint work with Samuel Fiorini, Gwenael Joret, and Dirk Theis.

**Wide Containers in Gaussian Networks**

*Discrete Structures and Algorithms (Seminar)*

**by **Muhammad Surani

**Institution: **The University of Melbourne

**Date: **06/09/2011 11:00am

**Abstract: **A Gaussian network is a Cayley graph modelled on a quotient ring of the Gaussian integers. Indeed, many circulant graphs and tori are isomorphic to Gaussian networks, and so this provides a useful algebraic structure with which to study them. Many highly sought after properties in interconnection networks and coding theory (e.g. diameter, shortest paths) can be easily obtained under this framework. The concept of wide containers will also be introduced to unify the properties of connectivity and diameter.

**Linear and cyclic metric labelling problems for complete m-ary trees**

*Discrete Structures and Algorithms (Seminar)*

**by **Kelvin Yang Li

**Institution: **The University of Melbourne

**Date: **16/08/2011 11:00am

**Abstract: **The frequency assignment problem is concerned with assigning frequency to each transmitter such that the maximum span of the frequency is minimized under some distance constraints. In reality the closer two transmitters are, the larger the separation between their frequencies are required to be. Such problems can be turned into graph labelling problems. Given a positive integer h, an L(h,1,1)-labelling of a graph is an assignment of non-negative integers to its vertices such that adjacent vertices receive labels differing by at least h and vertices with distance 1 or 2 apart receive distinct labels. The span of such a labelling is the difference between the maximum and minimum labels used. The objective is to find the minimum span over all L(h,1,1)-labellings.
In this talk we will discuss recent results on the L(h,1,1)-labelling problem and its cyclic version for complete m-ary trees.

**A construction of imprimitive symmetric graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Bin Jia

**Institution: **Department of Mathematics and Statistics, The University of Melbourne

**Date: **30/05/2011 4:15pm

**Abstract: **Let G be a finite simple graph without isolated vertices. An automorphism of G is a permutation of its vertices that preserves the adjacency and non-adjacency relations. G is called symmetric if any arc (ordered pair of adjacent vertices) can be mapped to any other arc by some automorphism. G is imprimitive with respect to an arc-transitive subgroup of its automorphism group if its vertex set admits a non-trivial partition P that is invariant under the action of the subgroup. In this case the quotient graph is defined to have vertex set P such that two blocks are adjacent if and only if an edge of G between them exists.
For any two adjacent blocks of P, if not all vertices of one block have neighbours in the other, then G is not a multicover of the quotient graph. In this case we give a combinatorial method for reconstructing the imprimitive graph from certain natural local structures of its quotient.
This talk is aimed at a general audience. We will display most of ideas and results by pictures. The talk is based on joint work with Lu and Wang.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Unitary graphs, and classification of a family of symmetric graphs with complete quotients**

*Discrete Structures and Algorithms (Seminar)*

**by **A/Prof Sanming Zhou

**Institution: **Department of Mathematics and Statistics, The University of Melbourne

**Date: **23/05/2011 4:15pm

**Abstract: **A finite graph is called symmetric if its automorphism group is transitive on the set of arcs (ordered pairs of adjacent vertices) of the graph. This is to say that all arcs have the same status in the graph. I will talk about a family of symmetric graphs, called the unitary graphs, whose vertices are flags of the Hermitian unital (a special block design) and whose adjacency relations are determined by certain elements of the underlying finite fields. Such graphs admit the unitary groups as groups of automorphisms, and they play a significant role in our classification of a family of symmetric graphs with complete quotients. I will also talk about this classification and some combinatorial properties of the unitary graphs. This talk is based on joint work with M. Giulietti, S. Marcugini and F. Pambianco.

*For more information: *contact: David Wood. email> woodd@unimelb.edu.au

**On Anti-Collusion Codes and Tracing Algorithms for Multimedia Fingerprinting**

*Discrete Structures and Algorithms (Seminar)*

**by **Ying Miao

**Institution: **Department of Social Systems and Management, University of Tsukuba, Japan

**Date: **21/03/2011 4:15pm

**Abstract: **Multimedia fingerprinting is an effective technique to trace the sources
of pirate copies of copyrighted multimedia information. AND anti-collusion
codes (AND-ACCs) were introduced to construct fingerprints resistant to
the averaging collusion attack on multimedia contents. In this talk, we first
point out some flaws in Trappe et al.'s hard-detection tracing algorithm
based on AND-ACC, then introduce logical anti-collusion codes (LACCs)
to improve the traceability of multimedia fingerprinting. It reveals that
frameproof codes have traceability for multimedia contents, which were
widely considered as having no traceability for generic digital contents.
We also introduce separable codes, which can be used to construct
LACCs by a composition method. Several upper bounds on the sizes of
separable codes are derived, and optimal separable codes of short
length are constructed by means of combinatorial structures such as finite
projective planes and cyclic difference matrices. These optimal separable
codes of short length can be used to produce good LACCs of long length.
We notice that the size of a code corresponds to the number of authorized
users in a multimedia fingerprinting system, and the length of a code
corresponds to the number of orthogonal basis signals in a multimedia
content.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Constraint Satisfaction Problems and Universal Algebra**

*Discrete Structures and Algorithms (Seminar)*

**by **Marcel Jackson

**Institution: **School of Engineering and Mathematical Sciences, La Trobe University, Melbourne

**Date: **07/03/2011 4:15pm

**Abstract: **It is well known that the task of deciding whether or not a finite graph is 2-colourable is rather easy, while the task of deciding whether or not a finite graph is 3-colourable is a familiar NP-complete problem. These problems fall into the general class of computational problems that ask for the existence of a function from some given combinatorial object (the vertices of the graph to be coloured) into some fixed domain (the colours) subject to preservation of certain given constraints (adjacent vertices are coloured differently). In other words, they are constraint satisfaction problems.
A very large number of natural computational problems can be interpreted as constraint satisfaction problems, and classifying the computational complexity of CSPs has received quite intense attention over the past decade. Each CSP (with fixed target domain) is solvable in the class NP, but a very influential conjecture of Feder and Vardi is that a dichotomy holds: such a problem is either NP-complete or is solvable in polynomial time.
This talk will be aimed at a general audience: we introduce the basic notions and the practical and theoretical motivations for studying the complexity of CSPs, with a particular focus on introducing the techniques from universal algebra that have informed most recent progress on the dichotomy conjecture.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Genetic Algorithms and Configurations of Points**

*Discrete Structures and Algorithms (Seminar)*

**by **Ruy Fabila-Monroy

**Institution: **Departamento de Matematicas, Cinvestav, Mexico

**Date: **28/02/2011 4:15pm

**Abstract: **Let S be a set of n points in general position in the plane (no three on a line). Many problems in combinatorial geometry deal with counting the number of certain geometric configurations in S. For example, if we draw all the line segments joining pair of points, how many of them will cross? Of course this number will vary depending on the actual choice of S. So normally lower and upper bounds are sought. A part of this process involves searching for sets of points achieving (or being close as possible) to these bounds. For example, searching for the set that minimizes the number of crossings in the above problem. This is in general a difficult task. Few techniques are known and in many cases there is a big gap between the theoretical bound and the best example. In this presentation, I will talk about how I have been using genetic algorithms to search for these extreme examples and the results obtained so far.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Set Cover Algorithms for very large datasets**

*Discrete Structures and Algorithms (Seminar)*

**by **Tony Wirth

**Institution: **University of Melbourne

**Date: **31/08/2010 12:00pm

**Abstract: **The problem of Set Coverâ€”to find the smallest subcollection of sets that covers some universeâ€”is at the heart of many data and analysis tasks. It arises in a wide range of settings, including operations research, machine learning, planning, data quality and data mining.
Although finding an optimal solution is NP-hard, the greedy algorithm is widely used, and typically finds solutions that are close to optimal.
However, a direct implementation of the greedy approach, which picks the set with the largest number of uncovered items at each step, does not behave well when the input is very large and disk resident. The greedy algorithm must make many random accesses to disk, which are unpredictable and costly in comparison to linear scans. In order to scale Set Cover to large datasets, we provide a new algorithm which finds a solution that is provably close to that of greedy, but which is much more efficient to implement using modern disk technology. Our experiments show a ten-fold improvement in speed on moderately-sized datasets, and an even greater improvement on larger datasets.
This paper is joint work with Graham Cormode and Howard Karloff, both at AT&T Labs-Research, and will appear in CIKM 2010.
Biosketch:
Tony Wirth received the BSc (Hons) and MSc degrees from the University of Melbourne, and the MA and PhD degrees at Princeton University.
Tony's research interests are based around theoretical computer science, including graph algorithms, approximation algorithms, algorithms on external memory, communication complexity, adaptive sampling, and sequence analysis problems in bioinformatics. Tony joined the Department of Computer Science and Software Engineering as a lecturer in 2005; the day after this seminar, he will become a senior lecturer.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Some new results on the degree-diameter and the degree-girth problems, both asymptotic and non-existential**

*Discrete Structures and Algorithms (Seminar)*

**by **Guillermo Pineda-Villavicencio

**Institution: **University of Ballarat

**Date: **26/08/2010 2:00pm

**Abstract: **The degree-diameter problem aims to find the largest possible order of a graph with given degree and diameter, while the degree-girth problem aims to find the smallest possible order of a graph with given degree and girth. In this context the Moore bound constitutes both an upper bound on the order of a graph of given maximum degree and diameter, and a lower bound on the order of a graph of given minimum degree and odd girth.
Graphs missing or exceeding the Moore bound by e are called graphs with defect or excess e, respectively. With the exception of the degree 57 and diameter 2, Moore graphs have been fully characterized, so have been the graphs with defect or excess 1. However, graphs with defect or excess 2 represent a wide unexplored area. In the talk I present both asymptotic and non-existentence results on the class of graphs with defect or excess 2.
Joint work with Charles Delorme (UniversitÃ© Paris-Sud)

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Optimal gossiping protocol in the Gaussian and Eisenstein-Jacobi networks.**

*Discrete Structures and Algorithms (Seminar)*

**by **Pongphat Taptagaporn

**Institution: **The University of Melbourne

**Date: **29/07/2010 2:00pm

**Abstract: **The Gaussian and Eisenstein-Jacobi (EJ for short) networks are graphs induced by the Gaussian and EJ integers respectively. We look at communication
protocols in these graphs, and here we focus on gossiping; where every
vertices send a distinct message to all the other vertices in the graph.
We will find the exact values of the gossip time and show that they are optimal under the store-and-forward, all-port and full-duplex model for
gossiping. We will also look at the edge and arc-forwarding indices in
all-to-all routing.
Studies of these graphs were previously motivated by coding theory as they were known to generate "perfect" codes. More recently we have found that these graphs exhibit close connections to first-kind Frobenius graphs,
circulant graphs and tori.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Some wonderful conjectures (but almost no theorems) at the boundary between analysis, combinatorics and probability**

*Discrete Structures and Algorithms (Seminar)*

**by **Alan Sokal

**Institution: **University College London/New York University

**Date: **29/07/2010 10:00am

**Abstract: **I discuss some analytic and combinatorial properties of the entire function
$F(x,y) = \sum\limits_{n=0}^\infty \frac{x^n}{n!} y^{n(n-1)/2}$.
This function (or formal power series) arises in numerous problems in enumerative combinatorics, notably in the enumeration of connected graphs.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Sudoku: Strategy Versus Structure**

*Discrete Structures and Algorithms (Seminar)*

**by **Professor Scott Provan

**Institution: **Department of Statistics and Operations Research, University of North Carolina

**Date: **15/06/2010 2:15pm

**Abstract: **Sudoku puzzles have become wildly popular in just the last few years, and quite a school has developed around classifying solution strategies for Sudoku puzzles. We give a simply-described set of strategies that solves about 90% of all Sudoku puzzles. This strategy class has two
interesting properties: one associated with the formulation of these puzzles as a set of interlocking assignment problems, and the other with their representation as the unique nonnegative solution to the associated set of assignment equations. We discuss this strategy, and indicate some interesting research problems in the area.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Gossiping and routing in second-kind Frobenius graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **A/Prof Sanming Zhou

**Institution: **Department of Mathematics and Statistics, The University of Melbourne

**Date: **25/05/2010 2:15pm

**Abstract: **Two kinds of Cayley graphs associated with finite Frobenius groups exhibit interesting routing properties, making them attractive candidates (at least in theory) for modelling interconnection networks.
In this talk I will focus on gossiping and routing in second-kind Frobenius graphs. In the case when the kernel of the Frobenius group
involved is abelian of odd order, we find the exact value of the minimum gossiping time for such a graph under the store-and-forward, all-port and full-duplex model and prove that the graph admits optimal
gossiping schemes with the following properties: messages are always
transmitted along shortest paths; each arc is used exactly once at each time step; at each step after the initial one the arcs carrying the message originated from a given vertex form a perfect matching. In the case when the kernel of the Frobenius group is abelian of even order, we give an upper bound on the minimum gossiping time under the same model. As examples we will discuss a family of second-kind
Frobenius graphs which contains all Paley graphs and connected generalized Paley graphs.
This talk is based on joint work with Xin Gui Fang at Peking University.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Cayley Graphs, Finite State Automata and Group Automata**

*Discrete Structures and Algorithms (Seminar)*

**by **Dr Andrei Kelarev

**Institution: **School of Information Technology and Mathematical Sciences, University of Ballarat

**Date: **18/05/2010 2:15pm

**Abstract: **Cayley graphs are closely related to the concepts of finite state
automata and group automata. In particular, finite state automata
are generalisations of the Cayley graphs, since every Cayley graph
can be regarded as a finite state automaton. Group automata form
an important subclass of the class of all finite state automata. On the
other hand, Cayley graphs are capable of accomplishing all tasks
performed by the finite state automata. These relations lead to new
open questions concerning the influence of the theoretical
properties of the Cayley graphs on their possible applications in
directions where finite state automata have been used, including
such areas as bioinformatics, data mining, computer graphics, and
internet security.
A.V. Kelarev, C.E. Praeger,
On transitive Cayley graphs of groups and semigroups,
European J. Combinatorics 24(2003)(1), 59â€“72.
A. Kelarev, J. Ryan, J. Yearwood,
Cayley graphs as classifiers for data mining: The influence
of asymmetries, Discrete Mathematics 309(2009)(17),
5360â€“5369.

*For more information: *contact: David Wood. email woodd@unimelb.edu.au

**The many formulae that count Latin squares**

*Discrete Structures and Algorithms (Seminar)*

**by **Douglas S Stones

**Institution: **Monash University

**Date: **11/05/2010 2:15pm

**Abstract: **A Latin square is an $n \times n$ matrix containing
$n$ distinct symbols such that each row and each column
contains each symbol exactly once. Latin squares are widely
used for designing experiments and in error-correcting codes.
However, merely counting Latin squares poses a significant
problem and many prior attempts have subsequently been
proved faulty. Despite some claims to the contrary, there are
many formulae for the number of Latin squares. In this talk,
we will give a survey of these formulae and their history which
stretches all the way back to MacMahon in 1898!

*For more information: *Contact: David Wood. email woodd@unimelb.edu.au

**Colouring the Plane**

*Discrete Structures and Algorithms (Seminar)*

**by **Michael Payne

**Institution: **Department of Mathematics and Statistics, The University of Melbourne

**Date: **04/05/2010 2:15pm

**Abstract: **The Chromatic Number of the Plane problems asks for the least number of colours required to colour the plane so that points distance one
apart receive different colours. Created in 1950, the problem has resisted all attempts to improve on the initial bounds (between 4 and
7) found soon afterwards. Of course, faced with such resistance mathematicians have studied many variations on the problem and found
some interesting results. I will talk about some such variations, namely the study of measurable colourings, graphs whose measurable and
general chromatic numbers differ, colourings of large subgraphs of the plane, and perhaps more if time permits.

*For more information: *contact: David Wood. email woodd@unimelb.edu.au

**Chromatic factorisation and Galois groups of chromatic polynomials**

*Discrete Structures and Algorithms (Seminar)*

**by **Keri Morgan

**Institution: **Clayton School of Information Technology, Monash University

**Date: **27/04/2010 2:15pm

**Abstract: **The chromatic polynomial P(G,k) gives the number of proper
k-colourings of a graph G. This polynomial is also studied in statistical
mechanics where the limit points of the zeros give possible locations of
physical phase transitions.
We say P(G,k) has a chromatic factorisation, if P(G,k)=P(H1,k)P(H2,k)/P(Kr,k)
for some graphs H1 and H2 and some r>=0. Any clique-separable graph,
that is, a graph that can be obtained by identifying an r-clique in H1 with an
r-clique in H2, has a chromatic factorisation. A graph is said to be strongly
non-clique-separable if it is neither clique-separable nor chromatically
equivalent to any clique-separable graph.
We identified strongly non-clique-separable graphs that have chromatic
factorisations. We give an overview of some of our results on these
chromatic factorisations including giving an infinite family of strongly
non-clique-separable graphs that have chromatic factorisations.
We then give a summary of the Galois groups of chromatic polynomials
of degree at most 10. We are interested in identifying the relationships
between graphs that have chromatic polynomials with the same Galois group.
We give some families of graphs that have chromatic polynomials with the
same Galois group.

*For more information: *contact: David Wood. email woodd@unimelb.edu.au