Page > 1 > 2 > 3 > 4

Heuristics for Supply Chain Management

Discrete Structures and Algorithms (Seminar)

by Helena Ramalhinho

Institution: Pompeu Fabra University - Spain

Date: 08/07/2015 12:00pm

Abstract: Supply Chain Management (SCM) is related with the management of all activities along a network of organizations to provide a good or a service to final customers. The efficiency of these activities can have a great impact in customer`s satisfaction and cost reduction. However, SCM is not just the sum of activities along the supply chain, but instead, it must consider the organizations, supervision and control of all activities in the chain from an integrated and collaborative perspective aiming to provide a competitive advantage. From this perspective, an increase in the dimension and complexity of the decision problems involved is expected, as several actors with different goals must be considered to efficiently administrate the activities within the supply chain. This talk briefly reviews the main concepts of SCM, identifying relevant decision and optimisation problems and discussing possible solution approaches. Heuristics and Metaheuristics are one of the best optimization tools to be used in solving and providing business insights for the SCM problems. This chapter also describes some successful Metaheuristics approaches to SCM and it examines future research trends. A large number of applications of Metaheuristics to SCM integrating new subjects such as, Open and Big Data, Smart Cities, online decision-making, just to mention a few are foresaw.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Bargaining mechanisms for one-way games

Discrete Structures and Algorithms (Seminar)

by Andres Abeliuk

Institution: NICTA and School of Engineering, The University of Melbourne

Date: 08/07/2015 11:00am

Abstract: The distinguishable feature of the games is that the payoff of some player is determined only by her own strategy and does not depend on actions taken by other players. We show that the equilibrium outcome in one-way games without payments and the social cost of any ex-post efficient mechanism, can be far from the optimum. We also show that it is impossible to design a Bayes-Nash incentive-compatible mechanism for one-way games that is budget-balanced, individually rational, and efficient. To address this negative result, we propose a privacy-preserving mechanism that is incentive-compatible and budget-balanced, satisfies ex-post individual rationality conditions, and produces an outcome which is more efficient than the equilibrium without payments. The mechanism is based on a single-offer bargaining and we show that a randomized multi-offer extension brings no additional benefit.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


A brief history of optimal power flow

Discrete Structures and Algorithms (Seminar)

by Carleton Coffrin

Institution: NICTA Optimisation Research Group

Date: 24/06/2015 11:00am

Abstract: The non-convex nonlinear AC power flow equations form the core of a wide range of power network decision support applications. One of the most notable being the Optimal Power Flow (OPF) problem, which was first described over 50 years ago and now plays an essential role in the minute-by-minute operations of modern power systems. This talk will begin with a review of the foundations of the OPF problem and then show how a sequence of recent discoveries from 2006, 2008, 2012, and 2014 have transformed our understanding of this fundamental power network optimization task. \\ Bio: Carleton Coffrin currently works as a staff researcher in NICTA-ORG's Future Energy Systems initiative where he investigates how optimization technology can aid in building a sustainable energy future. Before joining this group at NICTA, Carleton conducted his Ph.D. studies at Brown University and Los Alamos National Laboratory in the area of hybrid optimization for disaster management, under the supervision of Pascal Van Hentenryck.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Exact algorithms for the incremental network design with shortest paths

Discrete Structures and Algorithms (Seminar)

by Olivia J. Smith

Institution: IBM Australia

Date: 17/06/2015 11:00am

Abstract: Incremental Network Design problems are a recently defined class of problems where a network problem must be solved repeatedly during construction of a subset of the network. The optimal order of construction minimises the total cost. Here we present a variety of exact algorithms for this problem with shortest path as the network problem. We demonstrate that non-LP branching algorithms can perform around 100 times faster than standard MIP on difficult instances.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Graphs, partitions and cosets: G-graphs and their applications

Discrete Structures and Algorithms (Seminar)

by Cerasela Tanasescu

Institution: RMIT University

Date: 10/06/2015 11:00am

Abstract: Interactions between graph theory and group theory have already led to interesting results for both domains. The most famous graphs constructed from groups are Cayley graphs. However, since Cayley graphs are always vertex-transitive and hence regular, they can not be used to model semi-regular networks. This observation motivated the definition in 2005, of a new family of graphs, called G-graphs. They are defined on a group and have many regular properties, but are less restrictive than Cayley graphs. These graphs are semi-regular \(k\)-partite, with chromatic number \(k\) directly given by the group representation, and they can be transitive or not. Like Cayley graphs, their regularity and compact representation motivate their study for the analysis and design of networks and for other application areas such as coding theory. This talk will be organised as follows: First an introduction will set the context of algebraic graph theory and give some definitions as well as first useful results. Then I shall introduce some key concepts and give basic related properties. The third part addresses the question about whether the class of G-multigraphs contains well-known graph classes. Then the previous characterization of G-graphs will be extended, in particular to the infinite case. The fifth part deals with network robustness and investigates some interesting properties of G-(multi)graphs regarding vertex / edge transitivity as well as optimal connectivity. In the final part I give the first complexity results for the recognition of G-graphs exhibiting in particular a polynomial case: canonical abelian G-graphs. Here the close link between a class of G-graphs and some Cayley graphs will be pointed out, and an algorithm that illustrates an approach will be presented. I shall discuss some hardness results for the class of partition intersection graphs that contains G-graphs. I shall conclude my presentation with some future research directions.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Chromatic index of Latin squares and Steiner triple systems

Discrete Structures and Algorithms (Seminar)

by Ian Wanless

Institution: School of Mathematical Sciences, Monash University

Date: 03/06/2015 11:00am

Abstract: The chromatic index of a hypergraph is the smallest number of colours with which the edges can be coloured in such a way that no two intersecting edges have the same colour. Latin squares (LSs) and Steiner Triple Systems (STSs) can be viewed as particularly nice 3-uniform hypergraphs. In this viewpoint, the chromatic index of a LS measures how close it is to having an orthogonal mate. Similarly, the chromatic index of an STS measures how close it is to being resolvable. With these thoughts as motivation, we will investigate what is known about the chromatic index of LSs and STSs. Related questions are how few disjoint transversals a LS can have, and how few disjoint parallel classes a STS can have. These are questions that have recently seen some progress, though there is still much that we do not know.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Theta graphs, bicliques and the alpha conjectures

Discrete Structures and Algorithms (Seminar)

by Kerri Morgan

Institution: Faculty of Information Technology, Monash University

Date: 06/05/2015 11:00am

Abstract: The chromatic polynomial \(P(G; \lambda)\) gives the number of proper colourings of a graph \(G\) in at most \(\lambda\) colours. Which numbers can be roots of the chromatic polynomial is of great theoretical interest and also has applications in statistical mechanics where the partition function generalises the chromatic polynomial. Phase transitions can only occur at a real limit point of the complex roots of this function. Which algebraic numbers can be roots of the chromatic polynomial? While the question largely remains open we present results on roots of chromatic polynomials of families of graphs and look at open conjectures.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Scheduling arc shutdowns to maximise network flow

Discrete Structures and Algorithms (Seminar)

by Patrick Andersen

Institution: School of Mathematics and Statistics, The University of Melbourne

Date: 29/04/2015 11:00am

Abstract: This presentation explores a recently developed type of scheduling problem that combines the two well-studied Operations Research areas of job scheduling and network flow optimisation. The problem involves finding the best way of scheduling routine maintenance jobs for an infrastructure network so as to maximise flow through the network over a time horizon. We will explore the complexity of this problem for simple network types and we will show that for these networks, it is equivalent to a more general type of scheduling problem which can be modelled as well known combinatorial problems in some cases.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Quantum walks on Cayley graphs

Discrete Structures and Algorithms (Seminar)

by Chris Godsil

Institution: University of Waterloo

Date: 27/04/2015 2:00pm

Abstract: If \(X\) is a graph with adjacency matrix \(A\), then, according to physicists, the matrices \[ U(t) = \exp(itA), \quad t\in\mathbb{R} \] describe a so-called continuous quantum walk on \(X\). For a graph theorist, the key problem is to relate interesting features of the walk with properties of the underlying graph. In my talk I present the basic ideas, and discuss work concerned with quantum walks on Cayley graphs for abelian groups. There are many open problems.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Operational mine planning with blending, precedences and state-dependent constraints

Discrete Structures and Algorithms (Seminar)

by Christina Burt

Institution: Department of Computing and Information Systems, The University of Melbourne

Date: 22/04/2015 11:00am

Abstract: We study a planning problem from the mining industry where we are interested in creating a blended product using equipment with state-dependent traversal times. For this problem, state-dependent traversal times occur when new paths are formed over time—explicitly, as material is mined and new paths form—thereby possibly reducing the time cost, for example, to traverse between two points. While Mathematical Programming is a strong methodology for solving some aspects of the problem (including blending and precedences), it is not well equipped to handle the state-dependency. Graph-based search methods, such as A* search, are powerful for solving problems with state-dependent components. This is well studied in the Computer Science field of Automated Planning. However, the side constraints of blending cannot be easily handled. We therefore introduce a MIP-Planning heuristic that is based on a uni-directional decomposition.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Shotgun assembly of labelled graphs

Discrete Structures and Algorithms (Seminar)

by Nathan Ross

Institution: School of Mathematics and Statistics, The University of Melbourne

Date: 15/04/2015 11:00am

Abstract: We consider the problem of reconstructing graphs or labelled graphs from neighborhoods of given radius. The question of inferring a graph is a generalization of the DNA shotgun problem where the graph is an interval and the nodes are labelled by A, C, G, T. The graph shotgun problem is motivated in part by applications in neuroscience. We provide some necessary and some sufficient conditions for correct recovery both in combinatorial terms and for some generative models including Ising model on lattices and Erdos-Renyi random graphs. Joint work with Elchanan Mossel.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Selected topics in spectral graph theory

Discrete Structures and Algorithms (Seminar)

by Xiaogang Liu

Institution: School of Mathematics and Statistics, The University of Melbourne

Date: 08/04/2015 11:00am

Abstract: The spectrum of a graph is the set of eigenvalues of its adjacency matrix together with multiplicities. I will present some results on three topics in spectral graph theory obtained during my PhD. (1) Spectral properties of (quadratic) unitary Cayley graphs Determining the spectra of Cayley graphs is a basic but challenging problem. We obtained formulae for the spectra of unitary Cayley graphs and quadratic unitary Cayley graphs, which are two classes of Cayley graphs on the additive groups of finite commutative rings. Based on these formulae we obtained the spectral moments and energies of such graphs, and classified those which are Ramanujan or hyperenergetic. (2) Spectra of graph operations Graph operations are natural techniques for producing new graphs from old ones, and their spectra have received considerable attention. We introduced three graph operations and expressed the spectra of the resultant graphs by that of the input graphs. As an application we gave a method for constructing new expanders from known ones. (3) Graphs determined by their spectra A basic problem in spectral graph theory with motivations from chemistry is to find out which graphs are determined by their spectra. We proved that some joins and bicyclic graphs such as propeller graphs, dumbbell graphs and theta graphs are determined by their spectra. This is my PhD completion seminar.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Double-normal pairs in finite sets of points

Discrete Structures and Algorithms (Seminar)

by Konrad Swanepoel

Institution: Department of Mathematics, London School of Economics

Date: 01/04/2015 11:00am

Abstract: Given a set \(S\) of \(n\) points in Euclidean space, we call a pair \(\{a,b\}\) of points a double-normal pair if the closed slab bounded by the hyperplanes through \(a\) and \(b\), perpendicular to \(ab\), contains the set \(S\). The double-normal pairs determine a graph on \(S\). We are interested in finding upper bounds for the number of edges of this graph in terms of \(n\). The double-normal graph has not been studied much, but is related to two well-known graphs on sets of points in Euclidean space, as it contains the diameter graph and is contained in the graph of so-called antipodal pairs. We give an overview of some recent developments, some of which is joint work with János Pach.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Two centuries of Euclidean Steiner trees

Discrete Structures and Algorithms (Seminar)

by Martin Zachariasen

Institution: Department of Computer Science, University of Copenhagen

Date: 25/03/2015 10:00am

Abstract: The history of the Euclidean Steiner tree problem, which is the problem of constructing a shortest possible network interconnecting a set of given points in the Euclidean plane, goes back to Gergonne in the early 19th century. In this talk I present some of the contributions of the earliest papers on the Euclidean Steiner tree problem. Furthermore, I link these initial contributions with results from the recent literature on the problem. Joint work with Marcus Brazil, Ronald L. Graham and Doreen A. Thomas.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Boxicity and cubicity of graphs

Discrete Structures and Algorithms (Seminar)

by Sunil Chandran Leela

Institution: Indian Institute of Science

Date: 13/11/2014 2:00pm

Abstract: The minimum non-negative integer \(k\) such that a graph \(G\) can be represented as the intersection graph of axis parallel \(k\)-dimensional boxes is called the boxicity of \(G\). Cubicity is defined in a similar way: Here we restrict the the boxes to be axis parallel unit cubes. In the talk, I will survey the results we obtained regarding boxicity and cubicity over the last few years. I will also explain how these parameters are related to graph minors, partial order dimension, treewidth, bandwidth, etc.

For more information: For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Spectra of Cayley graphs

Discrete Structures and Algorithms (Seminar)

by Xiaogang Liu

Institution: The University of Melbourne

Date: 30/10/2014 2:00pm

Abstract: The spectrum of a graph is the multi-set of eigenvalues of its adjacency matrix. The Cayley graph of a group \(G\) relative to an inverse-closed subset \(S\) of \(G\) is the graph with vertex set \(G\) such that two distinct elements \(x, y \in G\) are adjacent if and only if \(xy^{-1} \in S\). This talk is an introduction to the spectra of Cayley graphs with a focus on the following three topics: 1. Which Cayley graphs are integral? A graph is called integral if all its eigenvalues are integers. It is known that this notion is related to the existence of perfect state transfer in a graph. 2. Which Cayley graphs are Ramanujan? A finite \(r\)-regular graph is called Ramanujan if all its eigenvalues other than \(\pm r\) belong to the interval \([-2\sqrt{r-1},2\sqrt{r-1}]\). It is well known that Ramanujan graphs are important in communication theory and the Ihara zeta function of a Ramanujan graph satisfies an analogue of the Riemann hypothesis. 3. Expander families of Cayley graphs An expander graph can be defined as an \(r\)-regular graph whose eigenvalues other than \(\pm r\) all belong to the interval \([-r(1-t), r(1-t)]\), where \(t>0\) is fixed. It is well known that expander graphs are very efficient as communication networks. In my talk I will mention some basic results and research problems on the topics above.

For more information: For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Negative correlation of spanning forests

Discrete Structures and Algorithms (Seminar)

by Arun Mani

Institution: The University of Melbourne

Date: 23/10/2014 2:00pm

Abstract: Let \(G = (V,E)\) be a graph, and \(F\) be a spanning forest of \(G\) chosen uniformly at random. In this talk, we show that for any pair of adjacent edges \(e, f \in E\), the events \(e \in F\) and \(f \in F\) are negatively correlated. This is joint work with David Wagner at the University of Waterloo.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Bounds on the Profitability of a Durable Good Monopolist

Discrete Structures and Algorithms (Seminar)

by Gerardo Berbeglia

Institution: Melbourne Business School, The University of Melbourne

Date: 16/10/2014 2:00pm

Abstract: A durable good is a long-lasting good that can be consumed repeatedly over time, and a duropolist is a monopolist in the market of a durable good. We consider a durable good market with one seller (the duropolist), \(N\) consumers (whose valuations are \(v_1, \ldots, v_N\)) and a finite horizon of \(T\) time periods. At time period \(t\), the duropolist announces a price \(p_t\) and each consumer decides whether to buy the item or wait. Each consumer \(i\) desires exactly one item and seeks to maximize her utility which is \(v_i - p_t\) if she buys the item in period \(t\). The duropolist seeks a pricing strategy that maximises her total revenue over the \(T\) periods. For such a sequential game, we first characterize the class of subgame perfect equilibria satisfying the standard skimming property. Then, we prove that duropoly profits are always at least as large as static monopoly profits (SMP) - the profit a monopolist for an equivalent consumable good could generate, but never exceed double the SMP. This is in contrasts with previous results on the durable good monopoly problem with an infinite time horizon, in which the duropolist profits are either arbitrarily small or arbitrarily large compared to the SMP. At the end of the talk, we will discuss the existence of equilibria that do not satisfy the standard skimming property as well as a conjecture about the potential duropolist profits under those equilibria.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Selective graph colouring problem: applications and complexity

Discrete Structures and Algorithms (Seminar)

by Marc Demange

Institution: RMIT University

Date: 18/09/2014 2:00pm

Abstract: In this talk I will present the Selective Graph Coloring Problem, a generalization of the standard graph coloring problem as well as several of its possible applications and related complexity results. Given a graph with a partition of its vertex set into several clusters, we want to select one vertex per cluster such that the chromatic number of the subgraph induced by the selected vertices is minimum. This problem appeared in the literature under different names for specific models. Here, we describe different models -- some already discussed in previous papers and some new ones -- in very different contexts under a unified framework based on this graph problem. Each model motivates the problem in some graph classes and we will discuss the related complexity in these classes. This talk presents some selected results from three papers co-authored with T. Ekim (Bogazici University, Istanbul), J. Monnot (CNRS, France), B. Ries (Dauphine University, Paris), C. Tanasescu (ESSEC Business School, Paris) and P. Pop (University of Baia Mare, Romania).


How to optimally interconnect a set of points in the plane

Discrete Structures and Algorithms (Seminar)

by Charl John Ras

Institution: The University of Melbourne

Date: 11/09/2014 2:00pm

Abstract: In this talk I will discuss the power-p Steiner tree problem in the Euclidean plane. I will detail my proof that the problem is in the complexity class exp-APX when p is part of the input, making it one of the hardest optimisation problems. To date there are no efficient algorithms for solving the power-p Steiner tree problem, however, I will talk about recent progress we have made on designing good heuristics. Finally I will briefly present my exact geometric algorithm, based on Voronoi diagrams, which seems tricky to implement, and then I will present two exact MINLP formulations, one of them convex, and show how the geometry of minimum spanning trees leads to valid inequalities for the formulation.


Link Graphs

Discrete Structures and Algorithms (Seminar)

by Bin Jia

Institution: The University of Melbourne

Date: 04/09/2014 2:00pm

Abstract: Graph theory is a branch of mathematics in which pairwise relations between objects are studied. My PhD thesis introduces and investigates a new family of graphs, called link graphs, that generalises the notions of line graphs and path graphs. An s-link is a walk of length s in which consecutive edges are different. We identify a link with its reverse sequence. The s-link graph of a graph G is the graph with vertices the s-links of G, and two vertices are adjacent if the union of their corresponding s-links forms an (s + 1)-link. For example, the 0-link graph of G is G, the 1-link graph of G is the line graph L(G) of G, and the 2-link graph of G is the 2-path graph of G. We give a characterisation that allows us to study the coloring of link graphs. A graph is t-colorable if its vertices can be colored by t colors such that the colors of adjacent vertices are distinct. The chromatic number of G is the minimum number t such that G is t-colorable. We bound the chromatic number of the s-link graph of G by a function of s and the chromatic numbers of G and L(G). As a consequence, the s-link graph of G is 3-colorable for large enough s. By investigating the shunting of s-links, we obtain results about the connectedness and minors of link graphs. The Hadwiger number of G is the maximum number t such that a complete graph of t vertices can be obtained from a subgraph of G by contracting edges. Hugo Hadwiger (1943) conjectured that the Hadwiger number of a finite graph is larger or equal to the chromatic number of that graph. The conjecture has been proved by Reed and Seymour (2004) for line graphs, and hence 1-link graphs. We prove Hadwiger's conjecture for a wide class of link graphs. The aforementioned characterisation can be developed into an algorithm which, for a finite graph H and an integer s, decides whether H is an s-link graph of some graph G, and finds all such G. (There might be infinitely many connected infinite graph G!) This implies that the recognition problem belongs to NP. In the special case that G is simple and of minimum degree at least 3, then G is unique, and the algorithm runs in linear time. Tree-decompositions and better-quasi-orderings of the original graphs of a finite link graph are also investigated. As a byproduct, we generalise a theorem of Ding (1992) as follows: for any infinite sequence of finite or infinite graphs (respectively, of bounded multiplicity), if none of them contains an s-path as a minor, then there are two graphs in the sequence such that the former is a (respectively, an induced) subgraph of the latter. No prior knowledge is needed.

For more information: This is Bin Jia's PhD completion seminar.


Growth Rates of Permutation Classes

Discrete Structures and Algorithms (Seminar)

by Vincent Vatter

Institution: University of Florida

Date: 01/08/2014 2:15pm

Abstract: A permutation class is a set of permutations closed under the natural notion of subpermutation. The resolution, early this century, by Marcus and Tardos of the Stanley-Wilf conjecture has focused attention on the exponential growth rates of these classes. I will discuss the problem of characterizing the growth rates which can occur.


Spectral Theory of Tensors

Discrete Structures and Algorithms (Seminar)

by Liqun Qi

Institution: The Hong Kong Polytechnic University

Date: 12/06/2014 11:00am

Abstract: Spectral graph theory is a well-studied and highly applicable subject. It studies the connection between properties of a graph, and the eigenvalues of a matrix associated with that graph. Comparing with the research of spectral graph theory, the research on spectral hypergraph theory is still on its beginning stage. Recently, due to the development of spectral theory of tensors, spectral hypergraph theory has also made its first stage progress. Several papers appeared on eigenvalues of the adjacency tensor and the Laplacian tensor of a uniform hypergraph. The International Workshop on Spectral Graph and Hypergraph Theory (SGHT2013) was held at Fuzhou University during May 30 - June 2, 2013. More papers appeared after the workshop. In this talk, I will review the development on spectral hypergraph theory.


On aperiodic correlation bounds and generalized Golay complementary pairs

Discrete Structures and Algorithms (Seminar)

by Udaya Parampalli

Institution: Department of Computing and Information Systems, The University of Melbourne

Date: 01/05/2014 12:00pm

Abstract: This is a two part talk covering certain recent results on sequences. In the first part, we visit aperiodic correlation bound of Levenstein and its connection to choosing weight vectors. The Levenshtein bound, as a function of the weight vector, is only known to be tighter than the Welch bound on aperiodic correlation for $K > 3, N > 1$, where $K$ and $N$ denote the set size and the sequence length, respectively. We discuss the bound with respect to a quadratic weight vector and answer the case of the bound $K=3$ and $N > 4$, which was left open in the paper by Levenstein. In the second part, we discuss certain properties of odd length binary $Z$-complementary pairs, which can be seen as generalized Golay pairs. A pair of sequences is called a Golay complementary pair (GCP) if their aperiodic autocorrelation sums are equal to zero for all the non-zero time shifts. The existing known binary GCPs have the sequence lengths of the form $2^a 10^b 26^d$, where $a, b, c$ are non-negative integers. Addressing the length restriction of GCP, Fan et al proposed the binary $Z$-complementary pairs (ZCPs), whose non-trivial aperiodic autocorrelation sums are zero within a window less than the whole sequence length. We introduce an optimality criterion for such objects and explore their connection to almost difference families. $Z$-complementary pairs are useful in interference-free asynchronous multicarrier CDMA communications.


New bounds for sample compression in machine learning theory

Discrete Structures and Algorithms (Seminar)

by Hyam Rubinstein

Institution: The University of Melbourne

Date: 16/04/2014 11:00am

Abstract: This is joint with Ben Rubinstein (Melbourne CIS) and Peter Bartlett (Berkeley and QUT) The sample compression problem is a fundamental question which was proposed more than 25 years ago. It completes the equivalence between learnability (bounded Vapnik-Chervonenkis dimension) and having a sample compression scheme for concept classes. We have been studying this problem using ideas from combinatorial geometry and topology. In particular, the most common approach is to try to embed a VC-d class into a maximum class of VC dimension equal to a (fixed) polynomial in d. The reason is that maximum classes (those with maximum cardinality for their VC dimension) have natural compression schemes which are inherited by any subset class. In previous work, we characterised maximum classes in terms of their cubical structure, as special types of contractible complexes. Moreover a class having VC dimension at most d is equivalent to having a complete union of n-d-1 cubes in the complement of the class. In this talk, a new bound will be given that an increase of VC dimension from d to at least 2d is required for this approach to compression. We introduce the concept of deficiency D, which is the difference of cardinality between a maximum class and a concept class of the same VC dimension d. It will be shown that any VC-d class has a compression scheme of dimension at most d+D.

For more information: contact: Sanming Zhou. email: sanming@unimelb.edu.au Please note the unusual location, day and time.


Tree-Width and Dimension

Discrete Structures and Algorithms (Seminar)

by Gwenael Joret

Institution: The University of Melbourne

Date: 10/04/2014 12:00pm

Abstract: Over the last 30 years, researchers have investigated connections between dimension for posets and planarity for graphs. In this talk I will present an extension of this line of research to structural graph theory, with a particular focus on tree-width. Joint work with Piotr Micek, Kevin G. Milans, William T. Trotter, Bartosz Walczak, and Ruidong Wang.


Nowhere-zero 3-flows in arc-transitive graphs on solvable groups

Discrete Structures and Algorithms (Seminar)

by Sanming Zhou

Institution: The University of Melbourne

Date: 03/04/2014 12:00pm

Abstract: A celebrated conjecture of Tutte asserts that every 4-edge-connected graph has a nowhere-zero 3-flow. Recently we proved with Xiangwen Li that, if a graph of valency at least four admits a solvable group of automorphisms acting transitively on its arc set, then it admits a nowhere-zero 3-flow. I will talk about this result and its proof. This is an update of a talk given at Monash University in October 2013. The present result covers all graphs admitting solvable arc-transitive groups of automorphisms, while in 2013 we were only able to prove the same result for nilpotent groups.


Two-arc-transitive Cayley graphs of odd order

Discrete Structures and Algorithms (Seminar)

by Binzhou Xia

Institution: Peking University

Date: 27/03/2014 12:00pm

Abstract: A graph is 2-arc-transitive if its automorphism group is transitive on the set of oriented paths of length two. In this talk I will introduce the coset graph approach to constructing 2-arc-transitive graphs, and give a complete classification of ``basic" 2-arc-transitive Cayley graphs of odd order. It turns out that cycles of odd length are the only 3-arc-transitive Cayley graphs of odd order, indicating the rarity of highly symmetrical Cayley graphs. The classification is based on the classification of factorizations of almost simple groups with one factor of odd order, which is of independent interest in group theory.


Minors and Tutte invariants for alternating dimaps

Discrete Structures and Algorithms (Seminar)

by Graham Farr

Institution: Monash University

Date: 20/03/2014 12:00pm

Abstract: A graph H is a minor of a graph G if it can be obtained from G by a sequence of deletions and/or contractions of edges. Minors play a central role in graph theory, in characterising graph properties and in counting various structures associated with graphs. The theory of minors is intimately related to duality in graphs and matroids. The foundations of the modern theory of minors were laid by Tutte, and have their historical roots in his famous 1940 paper (with Brooks, Smith and Stone) on ``squaring the square''. Tutte published a lesser known paper, on ``triangulating the triangle'', in 1948, which introduced a generalisation of duality, called triality or trinity, which applies to alternating dimaps (i.e., orientably embedded digraphs in which the edges incident at a vertex are directed alternately into, and out of, the vertex). This talk will describe a theory of minors for alternating dimaps, based on three fundamental operations related by Tutte's triality. The theory has many analogies with standard minor theory. However, these minor operations are non-commutative. This makes their theory more difficult, but we are still able to establish some of the kinds of results one would hope for in a theory of minors, such as excluded minor characterisations and enumerative invariants that obey linear recurrence relations analogous to the deletion-contraction relation for the Tutte polynomial. We will also mention connections with other combinatorial contexts in which minor-type operations, related by a triality, have been defined and studied. This talk will be close to one I gave at 37ACCMCC at UWA in Perth, Dec 2013.


Flexibility and the Steiner ratio conjecture

Discrete Structures and Algorithms (Seminar)

by David Kirszenblat

Institution: The University of Melbourne

Date: 27/02/2014 12:00pm

Abstract: Steiner trees are minimal networks with applications in the design of communication and transportation networks as well as microchips. The Steiner ratio is a measure for the performance of a Steiner minimal tree compared with that of a minimum spanning tree. In 1968, Gilbert and Pollak gave a conjecture for the lower bound for the Steiner ratio. In this talk, I will briefly describe the history of the Euclidean Steiner tree problem as well as some previous approaches towards verifying the ratio conjecture. I will then provide an overview of the ideas used to tackle the eight point case.


Clique-colouring in planar graphs

Discrete Structures and Algorithms (Seminar)

by Liying Kang

Institution: Shanghai University

Date: 13/02/2014 11:00am

Abstract: Let G be a graph without isolated vertices. A clique-transversal set of G is a subset of the vertex set of G which meets all cliques of G, where a clique is a complete subgraph maximal under inclusion having at least two vertices. The clique-transversal number of G is the cardinality of a minimum clique-transversal set of G. A k-clique-coloring of G is a k-coloring of its vertices such that no clique is monochromatic. All planar graphs have been proved to be 3-clique-colorable by Mohar and Skrekovski. Erd\"{o}s et al. proposed to find sharp estimates on the clique-transversal number for planar graphs. In this talk we first show that every outerplanar graph of order n has clique-transversal number at most 3n/5 and this bound is tight. Secondly, we prove that every claw-free planar graph, other than an odd cycle, is 2-clique-colorable and we present a polynomial-time algorithm to find its 2-clique-coloring. As a by-product of the result, we obtain a tight upper bound on the clique-transversal number for claw-free planar graphs.


On treewidth and graph minors

Discrete Structures and Algorithms (Seminar)

by Daniel Harvey

Institution: The University of Melbourne

Date: 11/02/2014 11:00am

Abstract: Treewidth and the Hadwiger number are key, related parameters in the fields of structural and algorithmic graph theory. Treewidth plays a pivotal role in the famous Graph Minor Theorem by Robertson and Seymour; the Hadwiger number is key to Hadwiger's conjecture, an important unsolved question in modern mathematics. We discuss several results on these topics, including determining the treewidth for the class of line graphs, an algorithm for quickly finding complete minors in graphs of high average degree, and some results on Hadwiger's conjecture for the class of circular arc graphs.

For more information: This is Daniel Harvey's Ph.D. Completion Seminar.


Combinatorial geometry of point sets with collinearities

Discrete Structures and Algorithms (Seminar)

by Michael Payne

Institution: The University of Melbourne

Date: 20/01/2014 11:00am

Abstract: During my candidature I have studied various combinatorial problems relating to the geometry of point sets in the Euclidean plane. The unifying theme is that all the problems involve point sets that are not in general position, but have some collinearities. Topics addressed include: Dirac's conjecture related to the maximum degree of visibility graphs, Erd\"{o}s' general position subset selection problem, connectivity properties of visibility graphs, visibility in bichromatic point sets, and empty pentagons in point sets with collinearities. In this talk I will describe some of this work, give some insight into the various methods we have used, and mention some interesting questions that remain open.

For more information: This is Michael Payne's Ph.D. Completion Seminar.


Skew-spectra and skew energy of oriented graphs

Discrete Structures and Algorithms (Seminar)

by Xueliang Li

Institution: Nankai University

Date: 05/12/2013 11:00am

Abstract: The skew energy of an oriented graph was introduced by Adiga, Balakrishnan and So in 2010, as one of various generalizations of the energy of an undirected graph. Let \(G\) be a simple undirected graph, and \(G^{\sigma}\) be an oriented graph of \(G\) with the orientation \(\sigma\)and skew-adjacency matrix \(S(G^{\sigma})\). The skew-spectra of \(G^{\sigma}\) is the spectra of the skew-adjacency matrix \(S(G^{\sigma})\). The skew energy of the oriented graph \(G^{\sigma}\) is defined as the sum of the norms of all the eigenvalues of \(S(G^{\sigma})\). In this talk, we survey most of the known results on the skew-spectra and skew energy of oriented graphs.


Local 2-geodesic transitivity of graphs

Discrete Structures and Algorithms (Seminar)

by Alice Devillers

Institution: The University of Western Australia

Date: 07/11/2013 2:30pm

Abstract: An $s$-geodesic in a graph is a shortest path connecting two vertices at distance $s$. We say that a graph is locally transitive on $s$-geodsics if the stabiliser of any vertex is transitive on the $s$-geodesics starting at that vertex. Being locally transitive on $s$-geodesic is not a monotone property: if an automorphism group $G$ of a graph $\Gamma$ is locally transitive on $s$-geodesics, it does not follow that $G$ is locally transitive on shorter geodesics. This situation is in stark contrast with the properties of $s$-arc transitivity. A graph is called locally $(G, s)$-arc transitive if the stabiliser of any vertex $v$ in $G$ is transitive on the s-arcs starting at $v$. It can easily be proved that a locally $s$-arc transitive graph is also locally $t$-arc transitive for all $t < s$ if and only if every vertex has valency at least two, or $s = 2$ and the graph is a star. In this talk, I will show a nice characterisation of all graphs that are locally transitive on 2-geodesics, but not locally transitive on 1-geodesics.


Cores of vertex-transitive graphs

Discrete Structures and Algorithms (Seminar)

by Ricky Rotheram

Institution: The University of Melbourne

Date: 10/10/2013 11:00am

Abstract: A homomorphism between two graphs $\Gamma$ and $\Psi$ is a map $\phi:V(\Gamma)\rightarrow V(\Psi)$, where for $x,y\in V(\Gamma)$, $\phi(x)$ is adjacent to $\phi(y)$ in Y whenever $x$ and $y$ are adjacent in X. The core of a graph $\Gamma$ is the smallest graph $\Gamma^\ast$ for which there exist homomorphisms $\Gamma\rightarrow\Gamma^\ast$ and $\Gamma^\ast\rightarrow \Gamma$. Thus cores are fundamental to our understanding of general graph homomorphisms. It is known that for a vertex-transitive graph $\Gamma$, $\Gamma^\ast$ is vertex-transitive, and that $\left|V(\Gamma^\ast)\right|$ divides $\left|V(\Gamma)\right|$. In this talk I outline my thesis, where I use these results to determine the cores of all imprimitive symmetric graphs of order $pq$, where $p< q$ are prime.


Geometric range assignment and min-power centres

Discrete Structures and Algorithms (Seminar)

by Charl John Ras

Institution: The University of Melbourne

Date: 19/09/2013 11:00am

Abstract: One of the most important problems in the optimal design of wireless ad hoc radio networks is that of power minimisation. The most appropriate model is the ``power efficient range assignment problem", where communication ranges are assigned to all nodes such that total power is minimised, and where it is assumed that the power of each node is proportional to its assigned communication range raised to an exponent $\alpha>1$. Solving the range assignment problem whilst allowing for the introduction of a bounded number of additional nodes anywhere in the plane constitutes a very general and highly applicable geometric network problem, which has only been solved in certain restricted settings. A first step towards this goal is a solution to the ``min-power centre problem", where exactly one new node is introduced. We use farthest point Voronoi diagrams and Delaunay triangulations to provide a complete geometric description of the min-power centre of a finite set of nodes in the Euclidean plane when cost is a quadratic function. This leads to a new sub-quadratic time algorithm for its construction. We also construct an upper bound for the performance of the centroid as an approximation to the quadratic min-power centre.


Trails of triples in Steiner triple systems

Discrete Structures and Algorithms (Seminar)

by Daniel Horsley

Institution: Monash University

Date: 29/08/2013 11:00am

Abstract: A Steiner triple system consists of a set of points and a collection of triples of points such that every pair of points occurs in exactly one triple. In this talk I will discuss the problem of finding a Steiner triple system whose triples can be ordered in such a way that every $m$ consecutive triples are disjoint. This obviously has consequences for the problem of finding a Steiner triple system whose triples can be partitioned into partial parallel classes (sets of pairwise disjoint triples) of specified sizes. These two problems have applications to the analysis of erasure codes for disk arrays and to that of codes for unipolar communication.


Partial orderings, linearisation and computable approximations

Discrete Structures and Algorithms (Seminar)

by Anthony W. Morphett

Institution: The University of Melbourne

Date: 08/08/2013 11:00am

Abstract: It was proved by Szpilrajn (1930) that every partial ordering (poset) can be extended to a linear (total) ordering. Such an extension is called a linear extension. Bonnet (1969) showed that a well-founded partial ordering has a well-founded linear extension; that is, the linearisation process can preserve well-foundedness. The same is true for scatteredness. The original proofs of these results were not constructive. In this talk we will discuss the extent to which these results hold effectively, and examine how (in)computable the linearisation process may be.


Eigenvalues of Cayley graphs

Discrete Structures and Algorithms (Seminar)

by Sanming Zhou

Institution: The University of Melbourne

Date: 01/08/2013 11:00am

Abstract: Cayley graphs are important objects of study in algebraic graph theory. They also play significant roles in numerous applications. For many applications, it is essential to understand the eigenvalues of the Cayley graphs involved. In this talk I will give a short review of some of the recent progresses on spectra of Cayley graphs with emphasis on unitary Cayley graphs on commutative rings and integral Cayley graphs on Abelian groups.


Page > 1 > 2 > 3 > 4