**Classifying bent functions**

*Discrete Structures and Algorithms (Seminar)*

**by **Paul Leopardi

**Institution: **The University of Melbourne and Australian Government - Bureau of Meteorology

**Date: **05/10/2017 11:00am

**Abstract: **Bent Boolean functions are fascinating and useful combinatorial objects, whose applications include coding theory and cryptography. In even dimensions, the bent functions are those Boolean functions that are at the maximum Hamming distance from any affine function. The number of bent functions explodes with dimension, and various concepts of equivalence are used to classify them. In 1999 Bernasconi and Codenotti noted that the Cayley graph of a bent function is strongly regular.
This talk describes the concept of extended Cayley equivalence of bent functions, explores the relationship between extended Cayley equivalence and extended affine equivalence of bent functions, and discusses some connections between bent functions, symmetric designs, linear codes, and strongly regular graphs. SageMath scripts and Cocalc worksheets are used to compute and display some of these relationships and connections, for bent functions up to dimension 8.

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

**Preprocessing obstacles for Steiner tree problems in Minkowski planes**

*Discrete Structures and Algorithms (Seminar)*

**by **Marcus Gordon Volz

**Institution: **The University of Melbourne

**Date: **21/09/2017 11:00am

**Abstract: **The obstacle-avoiding Steiner tree problem asks for a shortest embedded network spanning a given set of points such that no part of the network intersects the interiors of a given set of obstacles. The efficiency of exact algorithms for constructing minimum obstacle-avoiding Steiner trees can be improved by reducing the number of vertices and edges that need to be considered for the given obstacles. In this talk we introduce new methods for simplifying the geometry of obstacles for Steiner tree problems in Minkowski planes, and demonstrate their effectiveness by performing experimental results on randomly-generated obstacles in different metrics.

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

**On Benders decomposition**

*Discrete Structures and Algorithms (Seminar)*

**by **Alysson Machado Costa

**Institution: **The University of Melbourne

**Date: **07/09/2017 11:00am

**Abstract: **The first part of this talk will present a brief history/tutorial of the classical Benders decomposition technique (Benders, 1962) and its variants. Then, a new application of the technique to the assembly line balancing problem with setups will be discussed.

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

** Perfect Sequences over the Quaternions and \((4n, 2, 4n, 2n)\)-Relative Difference Sets in \(\mathbb{Z}_n \times Q_8\)**

*Discrete Structures and Algorithms (Seminar)*

**by **Santiago Barrera Acevedo

**Institution: **Monash University

**Date: **29/08/2017 10:00am

**Abstract: **The periodic autocorrelation of a sequence is a measure for how much the sequence differs from its cyclic shifts. If the autocorrelation values for all nontrivial cyclic shifts are 0, then the sequence is perfect. It is well known that sequences with good autocorrelation properties, such as being perfect, have important applications in information technology. However, it is very difficult to construct perfect sequences over 2nd, 4th, and in general over \(n\)th roots of unity. In fact, it is conjectured that perfect sequences over nth roots of unity do not exist for lengths greater than \(n^2\).
Due to the importance of perfect sequences and the difficulty to construct them over \(n\)th roots of unity, there has been some focus on other classes of sequences with good autocorrelation. One of these classes is the family of perfect sequences over the quaternions. In this talk, I will introduce perfect sequences over the quaternion groups \(Q_8\) and \(Q_{24}\). These sequences exhibit interesting symmetry patterns, which I aim to explain via a connection with relative difference sets and Williamson Hadamard matrices.

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

**On Aharoni-Berger's conjecture of rainbow matchings**

*Discrete Structures and Algorithms (Seminar)*

**by **Jane Gao

**Institution: **Monash University

**Date: **24/08/2017 11:00am

**Abstract: **Let \(G\) be a properly edge coloured multigraph with \(m\) colours and let \({\mathcal M}=\{M_1,\ldots, M_m\}\) be the set of \(m\) matchings induced by each colour in \(G\). Assume that every matching in \({\mathcal M}\) has size \(n\). Aharoni and Berger conjectured that if \(G\) is bipartite and \(m=n-1\) then \(G\) contains a full rainbow matching, i.e. a matching that contains exactly one edge from each \(M_i\) for each \(1\le i\le m\). We prove an approximate version of this conjecture. We show that if \(m\le n-n^{c}\), where \(c>9/10\), and \(G\) is simple whereas not necessarily bipartite, then \(G\) contains a rainbow matching if \(n\) is sufficiently large. Our proof proceeds by analysing a randomised algorithm.
This is collaborated work with Reshma Ramadurai, Ian Wanless and Nick Wormald.

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

**A modified Benders method for the single and multiple allocation p-hub median problem**

*Discrete Structures and Algorithms (Seminar)*

**by **Hamid Mokhtar

**Institution: **Monash University

**Date: **10/08/2017 11:00am

**Abstract: **We consider the well-known uncapacitated p-hub median problem with multiple allocation (UMApHMP), and single allocation (USApHMP). These problems have received significant attention in the literature because while they are easy to state and understand, they are hard to solve. They also find practical applications in logistics and telecommunication network design. Due to the inherent complexity of these problems, we apply a modified Benders decomposition method to solve large instances of the UMApHMP and USApHMP. The Benders decomposition approach does, however, suffer from slow convergence mainly due to the high degeneracy of subproblems. To resolve this, we apply a novel method of accelerating Benders Method. Our approach outperforms existing results in the literature by more appropriately choosing parameters for the accelerated Benders method, and by solving subproblems more efficiently using minimum cost network flow algorithms. We implement our approach on well-known benchmark data sets in the literature and compare our computational results with existing results. The computational results confirms that our approach is efficient and enables us to solve larger single- and multiple allocation hub median instances.

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

**Hybrid optimisation of vehicle routing problems**

*Discrete Structures and Algorithms (Seminar)*

**by **Edward Lam

**Institution: **The University of Melbourne

**Date: **01/06/2017 10:00am

**Abstract: **We propose a hybrid optimisation method, named Branch-and-Check with Explanations (BCE), that integrates linear programming (LP), constraint programming (CP), and Boolean satisfiability (SAT). BCE features an LP master problem that omits several families of cuts, and a CP subproblem that implements all omitted cuts as constraint propagators. Objective bounds and linear relaxation solutions are computed using the master problem, and then checked by the CP subproblem for feasibility of the omitted constraints. Infeasible solutions are sent to a SAT solver, which performs conflict analysis to derive nogoods. The nogoods are seamlessly translated into cuts for both the LP and CP problems. Experimental results for the Vehicle Routing Problem with Time Windows show that BCE dominates a branch-and-cut model even though it uses general-purpose conflict analysis rather than specialised separation algorithms to generate cuts.

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

**Vertex-transitive graphs with given arc-type**

*Discrete Structures and Algorithms (Seminar)*

**by **Nemanja Poznanovic

**Institution: **The University of Melbourne

**Date: **25/05/2017 11:00am

**Abstract: **Vertex-transitive graphs play a central role in algebraic graph theory. We will begin this talk by discussing some basic properties of these graphs and explaining how they may be classified using the language of arc-types.
The arc-type of a vertex-transitive graph is a partition of the graph's valency written as a sum of the lengths of the orbits of a vertex-stabilizer acting on the neighbourhood of that vertex. Parentheses are used in the partition to denote paired orbits.
A natural question which arises is which integer partitions (marked with parentheses) occur as the arc-type of some vertex-transitive graph. It has been shown by Conder, Pisanski and Zitnik that every marked integer partition except for 2 = 1+1 and 2 = (1+1) is the arc-type of some vertex-transitive graph. Recently, we have extended this result by showing that every marked integer partition except for 1, 1+1 and (1+1) is the arc-type of infinitely many connected Cayley graphs. We will discuss both of these results and some consequences.
No prior knowledge of vertex-transitive graphs is assumed.

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

**A study of cores of vertex-transitive graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Bi Wei

**Institution: **The University of Melbourne

**Date: **18/05/2017 11:00am

**Abstract: **A homomorphism from a graph G to a graph H is a map from V(G) to V(H) such that every edge of G is mapped to an edge of H. A bijective homomorphism from a graph to itself is an automorphism of the graph. A graph is vertex-transitive if any vertex can be mapped to any other vertex by an automorphism. If H is an induced subgraph of G with minimum number of vertices such that there exists a homomorphism from G to H, then H is called a core of G. The core of any graph is unique up to isomorphism. The order of the core of any vertex-transitive graph divides the order of the graph. I will talk about when the vertex set of a vertex-transitive graph can be partitioned into copies of its core. We give a sufficient condition for this to happen.

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

**Are there two non-isomorphic connected graphs that are Ramsey equivalent?**

*Discrete Structures and Algorithms (Seminar)*

**by **Anita Liebenau

**Institution: **Monash University

**Date: **13/04/2017 11:00am

**Abstract: **A graph G is Ramsey for a graph H if every 2-colouring of the edges of G contains a monochromatic copy of H (not necessarily induced). Two graphs H and H' are called Ramsey equivalent if every graph G is either Ramsey for both, H and H', or for neither.
It may be surprising that the complete graph on k vertices is not Ramsey equivalent to any other connected graph. In fact, we do not know any two connected (non-isomorphic) graphs H and H' that are Ramsey equivalent.
In this talk, I will introduce the concept of Ramsey equivalence and show its connections to other questions in Ramsey theory, survey previous results and report on recent progress in the area.

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

**TBA**

*Discrete Structures and Algorithms (Seminar)*

**by **Joyce Zhang

**Institution: **The University of Melbourne

**Date: **23/03/2017 11:00am

**Abstract: **Using a stochastic discrete model for urban traffic flow, we study Macroscopic Fundamental Diagrams (MFD) and the cross-correlations between density and flow of arterial road networks. With homogeneously distributed densities, we find a well-defined MFD and a monotonic relation between the cross-correlation and density. The results suggest that the cross-correlation is a natural indicator of traffic phases and vanishes when the network is at capacity. The density spatial heterogeneity has strong impact on the MFD and cross-correlation curve. A case study of perimeter control strategies based on MFD and cross-correlation is conducted. The simulation results suggest that, even with anisotropic traffic demands, both control strategies can improve the network performance in terms of both the traffic flow and density heterogeneity.

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

**A nice proof of Wei's duality theorem**

*Discrete Structures and Algorithms (Seminar)*

**by **Thomas Britz

**Institution: **The University of New South Wales

**Date: **09/03/2017 11:00am

**Abstract: **The Tutte polynomial was once an esoteric object known only to the then small community of combinatorialists. That changed when Greene (1976) pointed out the connection between this polynomial and weight enumerators, and how that connection provided a beautifully simple proof of the MacWilliams Identity (MacWilliams 1963) of coding theory fame. The Tutte polynomial is now of wide interest and appeal to the broader mathematical community who have found it lurking disguised in numerous areas of mathematics. Despite its present prominence, few are aware of how the Tutte polynomial provides another beautifully simple proof of a second celebrated duality theorem from coding theory, namely Wei’s Duality Theorem (Wei 1991). This proof, due to Duursma (2004), deserves better exposure, so this talk will present Duursma’s proof.

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

**Monotone expanders and applications**

*Discrete Structures and Algorithms (Seminar)*

**by **David Wood

**Institution: **Monash University

**Date: **21/02/2017 11:00am

**Abstract: **Expanders are classes of highly connected graphs that are of fundamental importance in graph theory, with numerous applications in
computer science, group theory and number theory. In a breakthrough
result that resolved an old open problem in complexity theory, Jean Bourgain recently constructed so-called d-monotone bipartite expanders, for some constant d. We consider the question of how small can d be. We answer this question by constructing 3-monotone expanders, which is best possible since 2-monotone graphs are planar. Similarly, we construct bipartite expanders that have 3-page book embeddings, 2-queue layouts, and 4-track layouts. All these results are best possible. The talk will only assume an elementary background in graph theory. Joint work with Vida Dujmović and Anastasios
Sidiropoulos.

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

**Analysis of Networks: Privacy in Bayesian Statistics and selected topics in Lattice Models**

*Discrete Structures and Algorithms (Seminar)*

**by **Zuhe Zhang

**Institution: **The University of Melbourne

**Date: **20/10/2016 11:00am

**Abstract: **We study privacy in the Bayesian paradigm, adopting the recent framework of differential privacy which asserts that a private statistics release mechanism should not reveal individual data. The focus of the work is on a posterior sampling algorithm that preserves differential privacy by placing conditions on the priors. We prove bounds on the sensitivity of the posterior to the data, which delivers a measure of robustness, from which differential privacy follows within a decision-theoretic framework. We provide bounds on the mechanism’s utility and on the distinguishability of datasets. These bounds are complemented by a novel application of Le Cam's method to obtain lower bounds. We also explore inference on probabilistic graphical models in terms of graph structure.
In parallel, we study enumeration problems and expansion properties of certain subgraphs of lattices. This will cover the investigation of the graph energy, dimer problem, spanning trees and expansion property of clique-inserted-lattices, the entropy of number of independent sets on 4-8-8 lattice and the monomer dimer problem on randomly triangulated grid graphs proposed by Brendan McKay.

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

**Wide containers in Gaussian networks**

*Discrete Structures and Algorithms (Seminar)*

**by **Adib Surani

**Institution: **The University of Melbourne

**Date: **06/10/2016 11:00am

**Abstract: **A Gaussian network is a Cayley graph modelled on a quotient ring of the Gaussian integers. Many circulant graphs and tori turn out to themselves be Gaussian networks, so this gives us a useful algebraic structure with which to study them. We will introduce the notion of wide containers as a tool for measuring fault tolerance in interconnection networks, and demonstrate that that the Gaussian networks exhibit good reliability under this measure.

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

**Thompson's group F and the Lodha-Moore group**

*Discrete Structures and Algorithms (Seminar)*

**by **Lawrence Reeves

**Institution: **The University of Melbourne

**Date: **01/09/2016 11:00am

**Abstract: **I will give an introductory talk to Thompson's group F and the Lodha-Moore group with an emphasis on their combinatorial properties.

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

**Equitable candy sharing**

*Discrete Structures and Algorithms (Seminar)*

**by **Grant Cairns

**Institution: **La Trobe University

**Date: **04/08/2016 11:00am

**Abstract: **The candy sharing game has been used in competitions and extension activities for students for over 50 years. Children, sitting in a circle, each have a nonnegative number of candies in front of them. A whistle is blown and each child with more than one candy passes one candy to the left and one to the right. The sharing process is repeated until a fixed state is attained, or the system enters a periodic cycle. This paper treats the case where the total number of candies equals the number of children. For a given initial distribution of candies, a necessary and sufficient condition is given for the system to ultimately attain the equitable distribution in which each child has one candy.

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

**Stochastic linear-quadratic optimisation with ambiguity in distribution**

*Discrete Structures and Algorithms (Seminar)*

**by **Jie Sun

**Institution: **Curtin University of Technology

**Date: **27/07/2016 2:00pm

**Abstract: **Solving stochastic optimisation problems often requires full information on distribution of the random variables involved. When such information is not available, an alternative scheme is to use the distributional robust optimisation approach that only requires partial information on the distribution. In addition to wide coverage of applications, the distributional robust model may result in a conic optimization problem and therefore avoid ``curse of dimensionality" that has been a major obstacle of solution to classical stochastic optimisation problems.

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

**Fast extraction of the backbone of projected bipartite networks**

*Discrete Structures and Algorithms (Seminar)*

**by **Jessica Liebig

**Institution: **RMIT University

**Date: **28/04/2016 11:00am

**Abstract: **The study of complex networks has received much attention over the past few decades, presenting a simple, yet efficient means of modelling and understanding complex systems. The majority of network science literature focuses on simple, so called one-mode networks. In the real world, however, we often find systems that are best represented by bipartite networks that are commonly analysed by examination of their one-mode projection.
One-mode projections are naturally very dense and noisy networks and hence the most relevant information may be hidden. One way to reveal hidden information is the extraction of significant edges, forming the backbone of the projection. Existing methods are computationally expensive.
In this talk, I will introduce a computationally inexpensive method for extracting the backbone of projected bipartite networks. I will demonstrate that the edge weights of projections follow a Poisson binomial distribution and that finding the expected weight distribution of a random bipartite projection only requires knowledge of the bipartite degree distributions.

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

**A few families of Cayley graphs as structures of communication networks**

*Discrete Structures and Algorithms (Seminar)*

**by **Hamid Mokhtar

**Institution: **The University of Melbourne

**Date: **21/04/2016 11:00am

**Abstract: **PhD Completion Seminar
We study network design problems and parameters that measure efficiency of communication networks. We obtain bounds on arc-forwarding and edge-forwarding indices and give an approximation algorithm for optical index problem for 4-regular circulant graphs. We study recursive cubes of rings by using algebraic tools. We give a shortest path routing and obtain asymptotic Wiener index and forwarding indices for such graphs. We propose cube-connected circulants as an efficient model for interconnection networks and study its embedding and forwarding index problems.

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

**Critical and subcritical scaling limits of random planar maps with connectivity constraints**

*Discrete Structures and Algorithms (Seminar)*

**by **Yuting Wen

**Institution: **The University of Melbourne

**Date: **14/04/2016 11:00am

**Abstract: **Part I: (Joint work with Louigi Addario-Berry) We show that a uniform quadrangulation, its largest 2-connected block, and its largest simple block jointly converge to the same Brownian map in distribution for the Gromov-Hausdorff-Prokhorov topology. We start by deriving a local limit theorem for the asymptotics of maximal block sizes, extending the result by Banderier, Flajolet, Schaeffer and Soria. The resulting diameter bounds for pendant submaps of random quadrangulations straightforwardly lead to Gromov-Hausdorff convergence. To extend the convergence to the Gromov-Hausdorff-Prokhorov topology, we show that exchangeable ``uniformly asymptotically negligible'' attachments of mass simply yield, in the limit, a deterministic scaling of the mass measure.
Part II: For each \(n\in\mathbb{N}\), let \(\mathbf{Q}_n\) be a uniform rooted quadrangulation, endowed with an appropriate measure, of size \(n\) conditioned to have \(r(n)\) vertices in its root block. We prove that for a suitable function \(r(n)\), after rescaling graph distance by \(\left(\frac{21}{40\cdot r(n)}\right)^{1/4}\), \(\mathbf{Q}_n\) converges to a random pointed measured non-compact metric space \(\mathcal{S}\), in the local Gromov-Hausdorff-Prokhorov topology; the space \( \mathcal{S}\) is built by identifying a uniform point of the Brownian map with the distinguished point of the Brownian plane.

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

**Generalized thrackle and graph surface embeddings**

*Discrete Structures and Algorithms (Seminar)*

**by **Yian Xu

**Institution: **The University of Western Australia

**Date: **22/03/2016 10:00am

**Abstract: **A thrackle on a surface X is a graph of size e and order n drawn on X such that every two distinct edges of G meet exactly once either at their common endpoint, or at a proper crossing. An unsolved conjecture of Conway (1969) asserts that e is at most n for every thrackle on a sphere. Until now, the best known bound is that e is at most 1.428n. By using discharging rules we show that e is at most 1.4n. Furthermore we show that the following are equivalent: G has a drawing on X where every two edges meet an odd number of times (a generalized thrackle); G has a drawing on X where every two edges meet exactly once (a one-thrackle); G has a special embedding on a surface whose genus differs from the genus of X by at most one.

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

**The thickness of Schubert cells and Schubert varieties**

*Discrete Structures and Algorithms (Seminar)*

**by **Jon Xu

**Institution: **The University of Melbourne

**Date: **10/03/2016 11:00am

**Abstract: **I will discuss thickness functions on Schubert cells and Schubert varieties, and how they can be used to detect the existence of objects coming from finite geometry (such as maximal caps, ovoids, and spreads). This is joint work with Arun Ram and John Bamberg.
If I manage to find the time to do the research before the talk, I will also talk about balanced independent sets of Schubert varieties and Schubert cells (building on Adib's talk).

*For more information: *Online participation via Zoom is welcome.
Contact: Sanming Zhou. email: sanming@unimelb.edu.au

**Sets on a plane**

*Discrete Structures and Algorithms (Seminar)*

**by **Muhammad Adib Surani

**Institution: **The University of Melbourne

**Date: **03/03/2016 11:00am

**Abstract: **An independent set of a bipartite graph is called balanced if it contains exactly half its elements in each partite set. In this talk, we will demonstrate a puzzle-like approach for finding large balanced independent sets in the incidence graph of Desarguesian projective planes. We will examine the previous best-known bounds for this problem, and also compare our approach against plain brute-forcing. Finally, we will generalise this problem to higher-dimensional projective spaces, before discussing the isoperimetric problem as the original motivation for this problem.

*For more information: *Online participation via Zoom is welcome.
Contact: Sanming Zhou. email: sanming@unimelb.edu.au

**Degree bounded geometric network design**

*Discrete Structures and Algorithms (Seminar)*

**by **Patrick Andersen

**Institution: **The University of Newcastle

**Date: **09/02/2016 11:00am

**Abstract: **PhD Confirmation Seminar
Geometric network design is a well-studied area with a broad range of applications spanning various industries. It is used in the development of computer networks, telecommunications networks, transportation systems, electrical grids, water supply systems, and in many more such settings where there are measurable distances between the various objects of a given network. For this project, the focus will be on designing optimal geometric networks with degree bound restrictions, i.e., we impose conditions on the number of connections that each object in our network possesses. These kinds of conditions are often necessary in the design of real world networks, where it may be infeasible to allow an arbitrary number of connections to an object due to physical limitations. This simple restriction can drastically alter the optimal solutions of network design problems, as well as the complexity of finding said solutions. The project will explore various geometric network design problems with degree bound restrictions, where the focus will be on all of the following design stages: the development of mathematical tools to model and understand the problems, the application of these tools to the construction of new algorithms, and the performance analysis of algorithms by mathematical means and by coding the algorithms and performing simulations.

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

**Lower and bound theorems for almost simplicial polytopes**

*Discrete Structures and Algorithms (Seminar)*

**by **Guillermo Pineda-Villavicencio

**Institution: **Federation University Australia

**Date: **19/11/2015 11:00am

**Abstract: **What is the largest number of facets, ridges, ..., edges of a simplicial \(d\)-polytope with a given number of vertices? A simplicial \(d\)-polytope is a polytope in which every facet is a \((d-1)\)-simplex. In 1970 McMullen answered the aforementioned question. The result is known as the Upper Bound theorem for simplicial polytopes. Equally, we can ask: what is the smallest number of facets, ridges, ..., edges of such a polytope with a given the number of vertices. Between 1971 and 1973 Barnette answered the latter question, proving the Lower Bound theorem for simplicial polytopes. Both results are considered major achievements in the combinatorial theory of polytopes. Both McMullen and Barnette also characterised the extreme polytopes.\\
In this talk we consider almost simplicial polytopes, that is, polytopes in which every facet, with at most one exception, is a simplex. This notion generalises the notion of simplicial polytopes. We prove lower and upper bounds theorems and characterise the extreme cases.\\
If time permits, I will present the proof of the lower bound theorem.\\
This is a joint work with Eran Nevo (Hebrew University of Jerusalem), Julien Ugon (Federation University Australia) and David Yost (Federation University Australia).

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

**The value set size of a random polynomial over finite fields**

*Discrete Structures and Algorithms (Seminar)*

**by **Jason Z. Gao

**Institution: **Carleton University, Canada

**Date: **05/11/2015 11:00am

**Abstract: **Polynomials over finite fields have been studied extensively and they have important applications to cryptography. In this talk we consider the so called indexed polynomials over finite fields and introduce a simple model for random polynomials over a finite field with a prescribed index. We will show that the value set size is asymptotically normal. The main techniques involved are inclusion-exclusion and asymptotic estimation of high moments of a relevant random variable. The method also applies to the study of the union of random sets which appears in statistical sampling theory.

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

**Homomorphism of signed (bipartite) graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Reza Naserasr

**Institution: **CNRS, France

**Date: **29/10/2015 11:00am

**Abstract: **We introduce the notion of homomorphisms of signed graphs and show how coloring results on minor closed families of graphs can strongly be strengthened using this notion. We then focus our attention on the restriction of this notion on signed bipartite graphs. We present an equivalent formulation of the Hadwiger conjecture using our terminology and then we show that
naturally expected extensions do not hold.\\
This is based on a joint work with Eric Sopena, Edita Rollova and several other colleagues.

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

**Ramsey-type theorems for lines in 3-space**

*Discrete Structures and Algorithms (Seminar)*

**by **Michael Payne

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

**Date: **22/10/2015 11:00am

**Abstract: **A classic result of Ramsey states that every sufficiently large graph contains a clique or independent set of size \(k\), where `sufficiently large' depends on \(k\). This marked the beginning of Ramsey theory, which studies the conditions under which a desired substructure must exist in a large discrete structure.\\
In this talk I will discuss results of this kind related to arrangements of lines in Euclidean 3-space. For example, we will see that every arrangement of \(n\) lines contains \(cn^{1/3}\) lines that either all pairwise intersect or are all pairwise disjoint (for some positive constant \(c\)). The proofs rely on recent incidence counting theorems
about lines, such as that proved by Guth and Katz in their solution of
the Erd\"{o}s distinct distances problem.\\
This is joint work with Jean Cardinal and Noam Solomon.

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

**Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments**

*Discrete Structures and Algorithms (Seminar)*

**by **Gerardo Berbeglia

**Institution: **Melbourne Business School, The University of Melbourne

**Date: **15/10/2015 11:00am

**Abstract: **A central problem in revenue management, known as the assortment problem, consists in deciding which subset of products to offer to consumers in order to maximise revenue. A simple algorithm is to select the best assortment out of all those that are constructed by fixing a threshold revenue \(r\) and then choosing all products with revenue at least \(r\). This is known as the revenue-ordered assortments strategy. We provide a precise analysis of how well revenue-ordered assortments approximate the optimum revenue when customers are rational in the following sense: the probability of selecting a specific product from the set being offered cannot increase if the offer set is enlarged. The corresponding discrete choice models form a broad class of models which includes all discrete choice models based on random utility. Our analysis of revenue-ordered assortments match and unify known results for certain models, and improves the best known results for others, such as for the Mixed Multinomial Logit model recently studied by Rusmevichientong et al (2014). An appealing feature of our analysis is that it is simple and relies only on the above-mentioned rationality property, and yet it is best possible even for very specific models within the class. We also show that a large class of problems known as envy-free pricing problems can be seen as assortment problems for a specifically constructed discrete choice model that satisfies the rationality property. In this context, revenue-ordered assortments turn out to be equivalent to the well-studied uniform pricing algorithm.\\
Joint work with Gwena\"{e}l Joret

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

**Embedding parameters in interconnection networks**

*Discrete Structures and Algorithms (Seminar)*

**by **Sundara Rajan

**Institution: **The University of Newcastle

**Date: **08/10/2015 11:00am

**Abstract: **Graph embedding is an important technique that maps a guest graph into a host graph, usually an interconnection network. Many applications can be modeled as graph embedding. In architecture simulation, graph embedding has been known as a powerful tool for implementation of parallel algorithms or simulation of different interconnection networks. The quality of an embedding can be measured by certain cost criteria, namely dilation, congestion and wirelength. My talk mainly focuses on dilation and wirelength on network embeddings.

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

**A family of symmetric graphs with complete quotients**

*Discrete Structures and Algorithms (Seminar)*

**by **Teng Fang

**Institution: **Peking University

**Date: **01/10/2015 11:00am

**Abstract: **A graph \(\Gamma\) is called \(G\)-symmetric if it admits \(G\) as a group of automorphisms acting transitively on the set of ordered pairs of adjacent vertices of \(\Gamma\). If in addition the vertex set of \(\Gamma\) admits a nontrivial \(G\)-invariant partition \(\cal{B}\) such that for any two distinct blocks \(B, C \in \cal{B}\), exactly one vertex of \(B\) has no neighbour in \(C\), then the quotient graph of \(\Gamma\) relative to \(\cal{B}\) is a complete graph and is almost multi-covered by \(\Gamma\). In this case there arises a natural 2-\((|\cal{B}|, m+1, \lambda)\) design with point set \(\cal{B}\) that admits \(G\) as a 2-point-transitive and block-transitive group of automorphisms, and moreover either \(\lambda = 1\) or \(\lambda = m+1 \ge 2\). In the former case all graphs \(\Gamma\) have been classified. In this seminar I will talk about a classification for the latter case with an emphasis on the methodologies used to achieve our results. \\
Joint work with Binzhou Xia and Sanming Zhou.

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

**Cyclotomic graphs and perfect codes**

*Discrete Structures and Algorithms (Seminar)*

**by **Sanming Zhou

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

**Date: **24/09/2015 11:00am

**Abstract: **A perfect \(e\)-code in a graph \(X\) is a subset \(C\) of the vertex set of \(X\) such that every vertex of \(X\) is at distance no more than \(e\) to exactly one vertex in \(C\). Given a group \(G\) and an inverse-closed subset \(S\) of \(G\) excluding the identity element, the Cayley graph of \(G\) with respect to \(S\) is the graph with vertex set \(G\) such that \(x\) and \(y\) are adjacent if and only if \(xy^{-1} \in S\). The well known Hamming codes can be thought as perfect 1-codes in the corresponding Hamming graphs. \\
I will talk about perfect codes in two families of Cayley graphs defined on a quotient ring of the ring of algebraic integers in a cyclotomic field. The study of such Cayley graphs was motivated by the need of constructing perfect codes as well as interconnection networks efficient for information transmission.

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

**Arc-transitive graphs with 2-arc-transitive quotients**

*Discrete Structures and Algorithms (Seminar)*

**by **Sanming Zhou

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

**Date: **17/09/2015 11:00am

**Abstract: **An \(s\)-arc of a graph is a sequence of \(s+1\) vertices such that any two consecutive vertices in the sequence are adjacent and any three consecutive vertices are distinct, where \(s \geq 0\) is an integer. A graph is called \((G,s)\)-arc-transitive if it admits \(G\) as a group of automorphisms acting transitively on its set of \(s\)-arcs. A \((G, 1)\)-arc-transitive graph is called a \(G\)-arc-transitive graph or \(G\)-symmetric graph. \\
Beginning with Tutte's seminal work (1947) on cubic symmetric graphs, the study of symmetric graphs and highly arc-transitive graphs has a long history but is still an active research area. \\
In this talk we will review progress in the study of \(G\)-arc-transitive graphs \(\Gamma\) admitting a \((G, 2)\)-arc-transitive quotient with respect to a nontrivial \(G\)-invariant partition of the vertex set of \(\Gamma\).

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

**Permanental polynomial of a graph**

*Discrete Structures and Algorithms (Seminar)*

**by **Xiaogang Liu

**Institution: **Northwestern Polytechnical University, China

**Date: **09/09/2015 12:00pm

**Abstract: **Let \(G\) be a graph on \(n\) vertices. Let \(A(G)\) denote the adjacency matrix of \(G\). The permanental polynomial of \(G\) is defined to be the permanent of the matrix \(xI_n-A(G)\), where \(I_n\) is the identity matrix of size \(n\). The per-spectrum of \(G\) is the multi-set of the roots of its permanental polynomial. In this talk, we will survey some known results on the permanental polynomial and the per-spectrum of a graph.

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

**Problems and challenges in network study**

*Discrete Structures and Algorithms (Seminar)*

**by **Shui Yu

**Institution: **School of Information Technology, Deakin University

**Date: **03/09/2015 11:00am

**Abstract: **Network is pervasive in our society. However, human understanding of networks is quite limited today. In this talk, we present the problems and challenges we meet in our research fields from the perspective of computer science. The content involves the problems and challenges in topology study in modern networks, dynamical feature investigation of malicious networks, unprecedented network related problems in the era of Big Data. Moreover, we will also show some interesting problems in computer science, such as mathematical analysis on power law, privacy measurement, and so on.

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

**Birthday problem, discrete logarithm and parallel computing**

*Discrete Structures and Algorithms (Seminar)*

**by **Jie Wang

**Institution: **Peking University

**Date: **20/08/2015 11:00am

**Abstract: **In this talk we will begin with the well-known birthday problem, the elliptic curve discrete logarithm problem (ECDLP) and one of its applications in cryptography -- Diffie-Hellman key exchange protocol. Then we will focus on how to solve ECDLP. Pollard \(\rho\)-algorithm, Floyd's Cycle-finding algorithm and Brent algorithm will be introduced. Finally, we will present a parallel approach of Pollard \(\rho\)-algorithm with distinguished set.

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

**On approximating target set selection**

*Discrete Structures and Algorithms (Seminar)*

**by **Tony Wirth

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

**Date: **13/08/2015 11:00am

**Abstract: **We study the Target Set Selection problem introduced by Kempe, Kleinberg, and Tardos (2003). This problem models influence in a network, in a sequence of rounds. A set of nodes is made ``active" initially. In each subsequent round, a vertex is activated if at least a certain number of its neighbors are(already) active. In the minimization version, the goal is to activate a small set of vertices initially - a target set - so that activation spreads to the entire graph. For the bounded-round version, where the goal is to activate all the vertices in r rounds, we provide an approximation algorithm. Assuming a conjecture on the hardness of Planted Dense Subgraph, we establish hardness results for this version, and show that they translate to general Target Set Selection, establishing a hardness of \(n^{1/2-\epsilon}\) for all \(\epsilon > 0\). This is the first polynomial hardness result for Target Set Selection. Finally, we also show an \(n^{1-\epsilon}\) hardness result for the undirected maximization version of the problem, thus establishing that the undirected case is as hard as the directed case.
Joint work with Moses Charikar, Andrew Chester and Yonatan Naamad.

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

**Fast densest subgraph in a stream**

*Discrete Structures and Algorithms (Seminar)*

**by **Tony Wirth

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

**Date: **06/08/2015 11:00am

**Abstract: **Dense subgraphs indicate interesting structures in many real-world
graphs, including social networks, web-link graphs, and biological
networks. The densest subgraph problem admits a polynomial-time
algorithm, but there is a simpler factor-two approximation. Bahmani et
al. showed how to run the latter algorithm using only \(O(n \log n)\) bits of space; however, in theory, it might require \(\Omega(\log n)\) passes over the stream. Recently, this approach has been extended to evolving graphs, in which an edge is selected for deletion uniformly at random.
Very recent work by Bhattacharya et al. has designed a one-pass
factor-four approximation for maintaining a densest subgraph in a
dynamic stream. Though for a static graph this algorithm becomes a two
approximation, it potentially has a large update time.
In this paper, we offer two approaches to speed up Bahmani et al.'s
algorithm (so that it operates in one pass) on a static graph. For a
general stream, our algorithm runs in \(O(n^(4/3) \log^2 n)\) space; for a
random-arrival stream, it runs in \(O(n \log^2 n)\) space. As we confirm in our experiments, each of these approaches has small update time.
Joint work with Martin Kwok and Kewen Liao

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

**Joint vehicle and crew routing and scheduling**

*Discrete Structures and Algorithms (Seminar)*

**by **Edward Lam

**Institution: **NICTA, The University of Melbourne

**Date: **30/07/2015 11:00am

**Abstract: **Traditional vehicle routing problems implicitly assume only one crew operates a vehicle for the entirety of its journey. However, this assumption is violated in many applications arising in humanitarian and military logistics. We present a Joint Vehicle and Crew Routing and Scheduling Problem, in which crews are able to interchange vehicles, resulting in space and time interdependencies between vehicle routes and crew routes. We propose a constraint programming model that overlays crew routing constraints over a standard vehicle routing problem. The constraint programming model uses a novel optimization constraint that detects infeasibility and bounds crew objectives. Experimental results demonstrate significant benefits of using constraint programming over mixed-integer programming and a vehicle-then-crew sequential approach.

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