Page > 1 > 2 > 3 > 4

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.

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.

On Benders decomposition

Discrete Structures and Algorithms (Seminar)

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Wide containers in Gaussian networks

Discrete Structures and Algorithms (Seminar)

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.

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.

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.

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.

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.

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.

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.

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.

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)

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.

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).

The value set size of a random polynomial over finite fields

Discrete Structures and Algorithms (Seminar)

by Jason Z. Gao

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.

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.

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.

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

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.

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.

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.

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$$.

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.

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.

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.

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.

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

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.