Page > 1 > 2 > 3 > 4

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.

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)

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

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)

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.

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.

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.

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.

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.

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.

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)

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.

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.

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.

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.

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.

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!

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.

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.