
CARMASponsored Seminar Series: Colloquia, Seminars and More.

[Note: events are listed by descending date.]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Sudeep Stephen, The University of Newcastle
 Title: The Forcing Number of Graphs with Given Girth
 Location: Room VG25, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Mon, 14^{th} Nov 2016
 Abstract:
For a twocoloring of the vertex set of a simple graph $G$ consider the following colorchange rule: a red vertex is converted to blue if it is the only red neighbor of some blue vertex. A vertex set $S$ is called zeroforcing if, starting with the vertices in $S$ blue and the vertices in the complement $V \setminus S$ red, all the vertices can be converted to blue by repeatedly applying the colorchange rule. The minimum cardinality of a zeroforcing set for the graph $G$ is called the zeroforcing number of $G$, denoted by $Z(G)$.
There is a conjecture connecting zero forcing number, minimum degree $d$ and girth $g$ as follows: "If G is a graph with girth $g \geq 3$ and minimum degree $d \geq 2$, then $Z(G) \geq d+ (d2)(g3)$".
I shall discuss a recent paper where the conjecture is proved to be true for all graphs with girth \leq 10.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Brian Alspach, CARMA, The University of Newcastle
 Title: HoffmanSingleton paper of 1964
 Location: Room VG25, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Mon, 7^{th} Nov 2016
 Abstract:
Today's discrete mathematics seminar is dedicated to Mirka Miller. I am going to present the beautiful HoffmanSingleton (1964) paper which established the possible values for valencies for Moore graphs of diameter 2, gave us the HoffmanSingleton graph of order 50, and gave us one of the intriguing still unsettled problems in combinatorics. The proof is completely linear algebra and is a proof that any serious student in discrete mathematics should see sometime. This is the general area in which Mirka made many contributions.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
 Title: The ErdosSzekeres conjecture about points in convex position
 Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Wed, 25^{th} May 2016
 Abstract:
In 1935 Erdos and Szekeres proved that there exists a function f such that among f(n) points in the plane in general position there are always n that form the vertices of a convex ngon. More precisiely, they could prove a lower and an upper bound for f(n) and conjectured that the lower bound is sharp. After 70 years with very limited progress, there have been a couple of small improvements of the upper bound in recent years, and finally last month Andrew Suk announced a huge step forward: a proof of an asymptotic version of the conjecture.
I plan two talks on this topic: (1) a brief introduction to Ramsey theory, and (2) an outline of Suk's proof.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Sudeep Stephen, School of Mathematical and Physical Sciences, The University of Newcastle
 Title: Zero Forcing Number of a Graph
 Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Wed, 18^{th} May 2016
 Abstract:
Zero forcing number, Z(G), of a graph G is the minimum cardinality of a set S of black vertices (whereas vertices in V (G)\S are colored white) such that V (G) is turned black after finitely many applications of "the colorchange rule": a white vertex is converted black if it is the only white neighbor of a black vertex.
Zero forcing number was introduced by the "AIM Minimum Rank – Special Graphs Work Group". In this talk, I present an overview of the results obtained from their paper.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Cyriac Grigorious, The University of Newcastle
 Title: Dimensions of Cayley (Di)graphs
 Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Wed, 27^{th} Apr 2016
 Abstract:
A metric generator is a set W of vertices of a graph G such that for every pair of vertices u,v of G, there exists a vertex w in W with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. In this case the vertex w is said to resolve or distinguish the vertices u and v. The minimum cardinality of a metric generator for G is called the metric dimension. The metric dimension problem is to find a minimum metric generator in a graph G. In this talk I am discussing about the metric dimension and partition dimension of Cayley (di)graphs.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Brian Alspach, CARMA, The University of Newcastle
 Title: Orthogonalizeable groups
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Wed, 6^{th} Apr 2016
 Abstract:
B. Gordon (1961) defined sequenceable groups and G. Ringel (1974) defined Rsequenceable groups. Friedlander, Gordon and Miller conjectured that finite abelian groups are either sequenceable or Rsequenceable. The preceding definitions are special cases of what T. Kalinowski and I are calling an orthogonalizeable group, namely, a group for which every Cayley digraph on the group admits either an orthogonal directed path or an orthogonal directed cycle. I shall go over the history and current status of this topic along with a discussion about the completion of a proof of the FGM conjecture.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
 Title: Discrepancy in graphs
 Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Wed, 30^{th} Mar 2016
 Abstract:
The discrepancy of a graph measures how evenly its edges are distributed. I will talk about a lower bound which was proved by Bollobas and Scott in 2006, and extends older results by Erdos, Goldberg, Pach and Spencer. The proof provides a nice illustration of the probabilistic method in combinatorics. If time allows I will outline how this stuff can be used to prove something about convex hulls of bilinear functions.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Dr Michael Coons, CARMA, The University of Newcastle
 Title: Minimal growth of some structured $\pm 1$sequences
 Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Wed, 16^{th} Mar 2016
 Abstract:
In this talk, I will outline my interest in, and results towards, the Erdős Discrepancy Problem (EDP). I came about this problem as a PhD student sometime around 2007. At the time, many of the best number theorists in the world thought that this problem would outlast the Riemann hypothesis. I had run into some interesting examples of some structured sequences with very small growth, and in some of my early talks, I outlined a way one might be able to attack the EDP. As it turns out, the solution reflected quite a bit of what I had guessed. And I say 'guessed' because I was so young and naïve that my guess was nowhere near informed enough to actually have the experience behind it to call it a conjecture. In this talk, I will go into what I was thinking and provide proof sketches of what turn out to be the extremal examples of EDP.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
 Title: The unionclosed sets conjecture
 Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Wed, 2^{nd} Mar 2016
 Abstract:
Peter Frankl's unionclosed sets conjecture, which dates back to (at least) 1979, states that for every finite family of sets which is closed under taking unions there is an element contained in at least half of the sets. Despite considerable efforts the general conjecture is still open, and the latest polymath project is an attempt to make progress. I will give an overview of equivalent variants of the conjecture and discuss known special cases and partial results.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Dominique Buset, unknown or leave blank,
 Title: The Degree/Diameter Problem for Mixed Graphs
 Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 11:00 am, Thu, 11^{th} Feb 2016
 Abstract:
The Degree/Diameter Problem for graphs has its motivation in the efficient design of interconnection networks. It seeks to find the maximum possible order of a graph with a given (maximum) degree and diameter. It is known that graphs attaining the maximum possible value (the Moore bound) are extremely rare, but much activity is focussed on finding new examples of graphs or families of graph with orders approaching the bound as closely as possible. This problem was first mention in 1964 and has its motivation in the efficient design of interconnection networks. A lot of great mathematician studied this problem and obtained some results but there still remain a lot of unsolved problems about this subject. Our regretted professor Mirka Miller has given a great expansion to this problems and a lot of new results were given by her and her students. One of the problem she was recently interested in, was the Degree/Diameter problem for mixed graphs i.e. graphs in which we allow undirected edges and arcs (directed edges).
Some new result about the upper bound of this Moore mixed graph has been obtained in 2015. So this talk consists on giving the main known results about those graphs.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Paul Leopardi, unknown or leave blank,
 Title: Finding quadrature points in a sparse grid: a downset constrained binary knapsack problem
 Location: Room V31, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 22^{nd} Oct 2015
 Abstract:
A dimension adaptive algorithm for sparse grid quadrature in reproducing kernel Hilbert spaces on products of spheres uses a greedy algorithm to approximately solve a downset constrained binary knapsack problem. The talk will describe the quadrature problem, the knapsack problem and the algorithm, and will include some numerical examples.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
 Title: Combinatorial Nullstellensatz
 Location: Room V31, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 27^{th} Aug 2015
 Abstract:
Noga Alon's Combinatorial Nullstellensatz, published in 1999, is a statement about polynomials in many variables and what happens if one of these vanishes over the set of common zeros of some others. In contrast to Hilbert's Nullstellensatz, it makes strong assumptions about the polynomials it is talking about, and this leads a tool for producing short and elegant proofs for numerous old and new results in combinatorial number theory and graph theory. I will present the proof of the algebraic result and some of the combinatorial applications in the 1999 paper.
 Download: Seminar slides (208K)
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Dr Yuqing Lin, School of Electrical Engineering and Computer Science, The University of Newcastle
 Title: Edge disjoint perfect matchings in regular graph
 Location: Room V31, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 13^{th} Aug 2015
 Abstract:
Existing of perfect matchings in regular graph is a fundamental problem in graph theory, and it closely model many real world problems such as broadcasting and network management. Recently, we have studied the number of edge disjoint perfect matching in regular graph, and using some wellknown results on the existence of perfect matching and operations forcing unique perfect matchings in regular graph, we are able to make some pleasant progress. In this talk, we will present the new results and briefly discuss the proof.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Paul Samuel, Kuwait University
 Title: Convex Partition and Graph Embedding
 Location: Room V31, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 6^{th} Aug 2015
 Abstract:
Partitioning is a basic fundamental technique in graph theory. Graph partitioning technique is used widely to solve several combinatorial problems. We will discuss the role of edge partitioning techniques on graph embedding. The graph embedding includes some combinatorial problems such as bandwidth problem, wirelength problem, forwarding index problem etc and in addition includes some cheminformatics problems such as Wiener Index, Szeged Index, PI index etc. In this seminar, we study convex partition and its characterization. In addition, we also analyze the relationship between convex partition and some other edge partitions such as Szeged edge partition and channel edge partition. The graphs that induce convex partitions are bipartite. We will discuss the difficulties in extending this technique to nonbipartite graphs.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Padraig Ó Catháin , unknown or leave blank,
 Title: Unbiased bases, uncertainty principles and trades in Hadamard matrices
 Location: Room VG25, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 1:00 pm, Wed, 27^{th} May 2015
 Abstract:
Arising originally from the analysis of a family of compressed sensing matrices, Ian Wanless and I recently investigated a number of linear algebra problems involving complex Hadamard matrices. I will discuss our main result, which relates rankone submatrices of Hadamard matrices to the number of nonzero terms in a representation of a fixed vector with respect to two unbiased bases of a finite dimensional vector space. Only a basic knowledge of linear algebra will be assumed.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Paul Leopardi, unknown or leave blank,
 Title: Twin bent functions, Cayley graphs, and RadonHurwitz theory
 Location: Room VG25, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 1:00 pm, Wed, 29^{th} Apr 2015
 Abstract:
I have recently [2] shown that each group $Z_2^{2m}$ gives rise to a pair of bent functions with disjoint support, whose Cayley graphs are a disjoint pair of strongly regular graphs $\Delta_m[1]$, $\Delta_m[1]$ on $4^m$ vertices. The two strongly regular graphs are twins in the sense that they have the same parameters $(\nu, k, \lambda, \mu)$. For $m < 4$, the two strongly regular graphs are isomorphic. For $m \geq 4$, they are not isomorphic, because the size of the largest clique differs. In particular, the largest clique size of $\Delta_m[1]$ is $\rho(2^m)$ and the largest clique in $\Delta_m[1]$ has size at least $2^m$, where $\rho(n)$ is the HurwitzRadon function. This nonisomorphism result disproves a number of conjectures that I made in a paper on constructions of Hadamard matrices [1].
[1] Paul Leopardi, "Constructions for Hadamard matrices, Clifford algebras, and their relation to amicability  antiamicability graphs", Australasian Journal of Combinatorics, Volume 58(2) (2014), pp. 214–248.
[2] Paul Leopardi, "Twin bent functions and Clifford algebras", accepted 13 January 2015 by the Springer Proceedings in Mathematics and Statistics (PROMS): Algebraic Design Theory and Hadamard Matrices (ADTHM 2014).
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
 Title: Combinatorics of data recovery in distributed databases
 Location: Room VG25, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 1:00 pm, Wed, 1^{st} Apr 2015
 Abstract:
I will discuss a combinatorial problem coming from database design. The problem can be interpreted as maximizing the number of edges in a certain hypergraph subject to a recoverability condition. It was solved recently by the high school student Max Aehle, who came up with a nice argument using the polynomial method.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Dr Yuqing Lin, School of Electrical Engineering and Computer Science, The University of Newcastle
 Title: The number of maximal state circles of plane graphs
 Location: Room V106, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 2:00 pm, Thu, 5^{th} Mar 2015
 Abstract:
It is well known that there is a onetoone correspondence between signed plane graphs and link diagrams via the medial construction. The relationship was once used in knot tabulations in the early time of study in knot theory. Indeed, it provides a method of studying links using graphs. Let $G$ be a plane graph. Let $D(G)$ be the alternating link diagram corresponding to the (positive) $G$ obtained from the medial construction. A state $S$ of $D$ is a labeling each crossing of $D$ by either $A$ or $B$. Making the corresponding split for each crossing gives a number of disjoint embedded closed circles, called state circles. We call a state which possesses maximum number of state circles a maximum state. The maximum state is closely related to the genus of the corresponding link, thus has been studied. In this talk, we will discuss some of the recent progress we have made on this topic.
 [Permanent event link]
 CARMA COMBINATORICS SEMINAR
 Speaker: Dr Paul Leopardi, Australian National University
 Title: Twin bent functions and Clifford algebras
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 25^{th} Sep 2014
 Abstract:
It is known that the function s defined on an ordering of the 4^m monomial
basis matrices of the real representation of the Clifford algebra Cl(m, m),
where s(A) = 0 if A is symmetric, s(A) = 1 if A is skew, is a bent function.
It is perhaps less well known that the function t, where t(A) = 0 if A is
diagonal or skew, t(A) = 1 otherwise, is also a bent function, with the
same parameters as s. The talk will describe these functions and their
relation to Hadamard difference sets and strongly regular graphs.
The talk was originally presented at ADTHM 2014 in Lethbridge this year.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Indra Rajasingh, School of Advanced Sciences, VIT University
 Title: Improved bound for LocatingTotal Domination Number of Regular Graphs
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 28^{th} Aug 2014
 Abstract:
A locatingtotal dominating set (LTDS) in a connected graph G is a total dominating set $S$ of $G$ such that for every two vertices $u$ and $v$ in $V(G)S$, $N(u) \cap S \neq N(v) \cap S$. Determining the minimum cardinality of a locatingtotal dominating set is called as the locatingtotal dominating problem and it is denoted as $\gamma_t^l (G)$. We have improved the lower bound obtained by M.A.Henning and N.D.Rad [1]. We have also proved that the bound obtained is sharp for some special families of regular graphs.
[1] M. A. Henning and N. J. Rad, Locatingtotal dominations in graphs, Discrete Applied Mathematics, 160(2012), 19861993.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Brian Alspach, CARMA, The University of Newcastle
 Title: The Oberwolfach Problem ReVisited
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 4:00 pm, Thu, 15^{th} May 2014
 Abstract:
This year is the fiftieth anniversary of Ringel's posing of the wellknown graph decomposition problem called the Oberwolfach problem. In this series of talks, I shall examine what has been accomplished so far, take a look at current work, and suggest a possible new avenue of approach. The material to be presented essentially will be selfcontained.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Brian Alspach, CARMA, The University of Newcastle
 Title: The Oberwolfach Problem ReVisited
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 4:00 pm, Thu, 8^{th} May 2014
 Abstract:
This year is the fiftieth anniversary of Ringel's posing of the wellknown graph decomposition problem called the Oberwolfach problem. In this series of talks, I shall examine what has been accomplished so far, take a look at current work, and suggest a possible new avenue of approach. The material to be presented essentially will be selfcontained.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Brian Alspach, CARMA, The University of Newcastle
 Title: The Oberwolfach Problem ReVisited
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 4:00 pm, Thu, 17^{th} Apr 2014
 Abstract:
This year is the fiftieth anniversary of Ringel's posing of the wellknown graph decomposition problem called the Oberwolfach problem. In this series of talks, I shall examine what has been accomplished so far, take a look at current work, and suggest a possible new avenue of approach. The material to be presented essentially will be selfcontained.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Brian Alspach, CARMA, The University of Newcastle
 Title: The proof of ManickamMiklosSinghi
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 4:00 pm, Thu, 10^{th} Apr 2014
 Abstract:
: In this final talk of the sequence we will sketch Blinovsky's recent proof of the conjecture: Whenever n is at least 4k, and A is a set of n numbers with sum 0, then there are at least (n1) choose (k1) subsets of size k which have nonnegative sum. The nice aspect of the proof is the combination of hypergraph concepts with convex geometry arguments and a BerryEsseen inequality for approximating the hypergeometric distribution. The not so nice aspect (which will be omitted in the talk) is the amount of very tedious algebraic manipulation that is necessary to verify the required estimates. There are slides for all four MMS talks here.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Brian Alspach, CARMA, The University of Newcastle
 Title: From EKR to MMS
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 4:00 pm, Thu, 3^{rd} Apr 2014
 Abstract:
The ErdosKoRado (EKR) Theorem is a classical result in combinatorial set theory and is absolutely fundamental to the development of extremal set theory. It answers the following question: What is the maximum size of a family F of kelement subsets of the set {1,2,...,n} such that any two sets in F have nonempty intersection?
In the 1980's Manickam, Miklos and Singhi (MMS) asked the following question: Given that a set A of n real numbers has sum zero, what is the smallest possible number of kelement subsets of A with nonnegative sum? They conjectured that the optimal solutions for this problem look precisely like the extremal families in the EKR theorem. This problem has been open for almost 30 years and many partial results have been proved. There was a burst of activity in 2012, culminating in a proof of the conjecture in October 2013.
This series of talks will explore the basic EKR theorem and discuss some of the recent results on the MMS conjecture.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Brian Alspach, CARMA, The University of Newcastle
 Title: From EKR to MMS
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 4:00 pm, Thu, 20^{th} Mar 2014
 Abstract:
The ErdosKoRado (EKR) Theorem is a classical result in combinatorial set theory and is absolutely fundamental to the development of extremal set theory. It answers the following question: What is the maximum size of a family F of kelement subsets of the set {1,2,...,n} such that any two sets in F have nonempty intersection?
In the 1980's Manickam, Miklos and Singhi (MMS) asked the following question: Given that a set A of n real numbers has sum zero, what is the smallest possible number of kelement subsets of A with nonnegative sum? They conjectured that the optimal solutions for this problem look precisely like the extremal families in the EKR theorem. This problem has been open for almost 30 years and many partial results have been proved. There was a burst of activity in 2012, culminating in a proof of the conjecture in October 2013.
This series of talks will explore the basic EKR theorem and discuss some of the recent results on the MMS conjecture.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Brian Alspach, CARMA, The University of Newcastle
 Title: From EKR to MMS
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 4:00 pm, Thu, 13^{th} Mar 2014
 Abstract:
The ErdosKoRado (EKR) Theorem is a classical result in combinatorial set theory and is absolutely fundamental to the development of extremal set theory. It answers the following question: What is the maximum size of a family F of kelement subsets of the set {1,2,...,n} such that any two sets in F have nonempty intersection?
In the 1980's Manickam, Miklos and Singhi (MMS) asked the following question: Given that a set A of n real numbers has sum zero, what is the smallest possible number of kelement subsets of A with nonnegative sum? They conjectured that the optimal solutions for this problem look precisely like the extremal families in the EKR theorem. This problem has been open for almost 30 years and many partial results have been proved. There was a burst of activity in 2012, culminating in a proof of the conjecture in October 2013.
This series of talks will explore the basic EKR theorem and discuss some of the recent results on the MMS conjecture.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Ilaria Castellano, University of Bari Aldo Moro
 Title: The Rough Cayley Graph
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 7^{th} Nov 2013
 Abstract:
The rough Cayley graph is the analogue in the context of topological groups of the standard Cayley graph, which is defined for finitely generated group. It will be shown how it is possible to associate such a graph to a compactly generated totally disconnected and locally compact (t.d.l.c.) group and how the rough Cayley graph represents an important tool to study the structure of this kind of group.
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Rajan Bharati, Loyola College
 Title: Conditional Resolvability in Graphs
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 2:00 pm, Tue, 5^{th} Nov 2013
 Abstract:
Let $G$ be a connected graph with vertex set $V$ and edge set $E$. The distance $d(u,v)$ between two vertices $u$ and $v$ in $G$ is the length of a shortest $uv$ path in $G$. For an ordered set $W = \{w_1, w_2, ..., w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the code of $v$ with respect to $W$ is the $k$vector
\begin{equation}
C_W(v)=(d(v,w_1),d(v,w_2), ..., d(v,w_k)).
\end{equation}
The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct codes with respect to $W$. A resolving set for $G$ containing a minimum number of vertices is called a minimum resolving set or a basis for $G$. The metric dimension, denoted, $dim(G)$ is the number of vertices in a basis for $G$. The problem of finding the metric dimension of an arbitrary graph is NPcomplete.
The problem of finding minimum metric dimension is NPcomplete for general graphs. Manuel et al. have proved that this problem remains NPcomplete for bipartite graphs. The minimum metric dimension problem has been studied for trees, multidimensional grids, Petersen graphs, torus networks, Benes and butterfly networks, honeycomb networks, Xtrees and enhanced hypercubes.
These concepts have been extended in various ways and studied for different subjects in graph theory, including such diverse aspects as the partition of the vertex set, decomposition, orientation, domination, and coloring in graphs. Many invariants arising from the study of resolving sets in graph theory offer subjects for applicable research.
The theory of conditional resolvability has evolved by imposing conditions on the resolving set. This talk is to recall the concepts and mention the work done so far and future work.
 [Permanent event link]
 CARMAGTA DISCRETE MATHEMATICS SEMINAR
 Speaker: Dr Joe Ryan, School of Electrical Engineering and Computer Science, The University of Newcastle
 Title: Subgraph degree/diameter problem
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 10^{th} Oct 2013
 Abstract:
TBA
 [Permanent event link]
 CARMAGTA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Edy Tri Baskoro, Institut Teknologi Bandung (ITB)
 Title: Necessary Conditions for the existence of Almost Moore Digraphs
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 26^{th} Sep 2013
 Abstract:
It is well known that the Moore digraph, namely a diregular digraph of degree d,
diameter k and order 1 + d + d 2 + ... + d k , only exists if d = 1 or k = 1. Let
(d,k)digraph be a diregular digraph of degree d ≥ 2, diameter k ≥ 2 and order
d+d 2 +...+d k , one less than the Moore bound. Such a (d,k)digraph is also called
an almost Moore digraph.
The study of the existence of an almost Moore digraph of degree d and diameter k
has received much attention. Fiol, Allegre and Yebra (1983) showed the existence
of (d,2)digraphs for all d ≥ 2. In particular, for d = 2 and k = 2, Miller and
Fris (1988) enumerated all nonisomophic (2,2)digraphs. Furthermore, Gimbert
(2001) showed that there is only one (d,2)digraph for d ≥ 3. However for de
gree 2 and diameter k ≥ 3, it is known that there is no (2,k)digraph (Miller and
Fris, 1992). Furthermore, it was proved that there is no (3,k)digraph with k ≥ 3
(Baskoro, Miller, Siran and Sutton, 2005). Recently, Conde, Gimbert, Gonzáles,
Miret, and Moreno (2008 & 2013) showed that no (d,k)digraphs exist for k = 3,4
and for any d ≥ 2. Thus, the remaining case still open is the existence of (d,k)
digraphs with d ≥ 4 and k ≥ 5.
Several necessary conditions for the existence of (d,k)digraphs, for d ≥ 4 and
k ≥ 5, have been obtained. In this talk, we shall discuss some necessary conditions
for these (d,k)digraphs. Open problems related to this study are also presented.
 [Permanent event link]
 CARMAGTA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Mirka Miller, School of Mathematical and Physical Sciences, The University of Newcastle
 Title: Degree/Diameter Problem
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 12^{th} Sep 2013
 Abstract:
The degree/diameter problem is to find the largest possible order of a graph (or digraph) with given maximum degree (or maximum outdegree) and given diameter. This is one of the unsolved problems in Extremal Graph Theory. Since the general problem is difficult many variations of the problem have been considered, including bipartite, vertextransitive, mixed, planar, etc.
This talk is part of a series started in May. The provisional schedule is
 10 May Novi Bong: Proof of the nonexistence of undirected Moore graphs for diameter 2 and 3 (Hoffman and Singleton, 1960)
 5 September Guillermo PinedaVillavicencio: New results in the degree/diameter problem for surfaces
 12 September Mirka Miller: Repeats and mixed Moore graphs
 19 September Mirka Miller: Constructions of large graphs and digraphs
 26 September Edy Tri Baskoro: Repeat permutations in almost Moore digraphs
 Midsemester break
 10 October Joe Ryan: Subgraph degree/diameter problem
 Another break...to be continued in November
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Dr Guillermo PinedaVillavicencio, Collaborative Research Network, The University of Ballarat
 Title: On the maximum order of graphs embedded in surfaces
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 5^{th} Sep 2013
 Abstract:
Joint work with David Wood (Monash University, Australia) and Eran Nevo (BenGurion University of the Negev, Israel).
The maximum number of vertices of a graph of maximum degree $\Delta\ge 3$ and diameter $k\ge 2$ is upper bounded by $\Delta^{k}$. If we restrict our graphs to certain classes, better upper bounds are known. For instance, for the class of trees there is an upper bound of $2\Delta^{\lfloor k/2\rfloor}$. The main result of this paper is that, for large $\Delta$, graphs embedded in surfaces of bounded Euler genus $g$ behave like trees. Specifically, we show that, for large $\Delta$, such graphs have orders bounded from above by
\begin{cases} (c_0g+c_1)\Delta^{\lfloor k/2\rfloor} & \text{if $k$ is even}\\
(c_0g^2+c_1)\Delta^{\lfloor k/2\rfloor} & \text{if $k$ is odd}
\end{cases}
where $c_0,c_1$ are absolute constants.
With respect to lower bounds, we construct graphs of Euler genus $g$, odd diameter and orders $(c_0\sqrt{g}+c_1)\Delta^{\lfloor k/2\rfloor}$, for absolute constants $c_0,c_1$.
Our results answer in the negative a conjecture by Miller and Širáň (2005). Before this paper, there were constructions of graphs of Euler genus $g$ and orders $c_0\Delta^{\lfloor k/2\rfloor}$ for an absolute constant $c_0$. Also, Šiagiová and Simanjuntak (2004) provided an upper bound of $(c_0g+c_1)k\Delta^{\lfloor k/2\rfloor}$ with absolute constants $c_0,c_1$.
 [Permanent event link]
 CARMAGTA DISCRETE MATHEMATICS INSTRUCTIONAL SEMINAR
 Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
 Title: Dependent Random Choice II
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 17^{th} Nov 2011
 Abstract:
We look at (parts of) the survey paper Dependent Random
Choice by Jacob Fox and Benny Sudakov: http://arxiv.org/abs/0909.3271. The abstract of the paper says "We describe a simple and yet
surprisingly powerful probabilistic technique which shows how to find in
a dense graph a large subset of vertices in which all (or almost all)
small subsets have many common neighbors. Recently this technique has
had several striking applications to Extremal Graph Theory, Ramsey
Theory, Additive Combinatorics, and Combinatorial Geometry. In this
survey we discuss some of them." My plan for the seminar is to start
with a quick recap of the classics of extremal (hyper)graph theory (i.e.
Turan, Ramsey, RamseyTuran), then look at some simple examples for the
probabilistic method in action, and finally come to the striking
applications mentioned in the quoted abstract. Only elementary
probability is required.
 [Permanent event link]
 CARMAGTA DISCRETE MATHEMATICS INSTRUCTIONAL SEMINAR
 Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
 Title: Review of "Dependent Random Choice"
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 10^{th} Nov 2011
 Abstract:
We look at (parts of) the survey paper Dependent Random Choice by Jacob Fox and Benny Sudakov: http://arxiv.org/abs/0909.3271
The abstract of the paper says "We describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently this technique has had several striking applications to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. In this survey we discuss some of them."
My plan for the seminar is to start with a quick recap of the classics of extremal (hyper)graph theory (i.e. Turan, Ramsey, RamseyTuran), then look at some simple examples for the probabilistic method in action, and finally come to the striking applications mentioned in the quoted abstract.
Only elementary probability is required.
 [Permanent event link]
 CARMAGTA DISCRETE MATHEMATICS SEMINAR
 Speaker: Dr Uwe Leck, Department of Mathematics and Computer Science, University of WisconsinSuperior
 Title: Orthogonal Double Covers of Graphs
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 4:00 pm, Tue, 28^{th} Jun 2011
 Abstract:
The concept of orthogonal double covers (ODC) of graphs originates in questions concerning database constraints and problems in statistical combinatorics and in design theory. An ODC of the complete graph $K_n$ by a graph $G$ is a collection of $n$ subgraphs of $K_n$, all isomorphic to $G$, such that any two of them share exactly one edge, and every edge of $K_n$ occurs in exactly two of the subgraphs. We survey some of the main results and conjectures in the area as well as constructions, generalizations and modifications of ODC.
 [Permanent event link]
 CARMAGTA DISCRETE MATHEMATICS SEMINAR
 Speaker: Ian Roberts, Charles Darwin University
 Title: The interplay of Extremal set theory and combinatorial designs
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:30 pm, Tue, 28^{th} Jun 2011
 Abstract:
The talk will focus on recent results or work in progress, with some open problems which span both Combinatorial Design and Sperner Theory. The work focuses upon the duality between antichains and completely separating systems. An antichain is a collection $\cal A$ of subsets of $[n]=\{1,...,n\}$ such that for any distinct $A,B\in\cal A$, $A$ is not a subset of $B$. A $k$regular antichain on $[m]$ is an antichain in which each element of $[m]$ occurs exactly $k$ times. A CSS is the dual of an antichain. An $(n,k)CSS \cal C$ is a collection of blocks of size $k$ on $[n]$, such that for each distinct $a,b\in [n]$ there are sets $A,B \in \cal C$ with $a \in AB$ and $b \in BA$. The notions of $k$regular antichains of size $n$ on $[m]$ and $(n,k)CSS$s in $m$ blocks are dual concepts. Natural questions to be considered include: Does a $k$regular antichain of size $n$ exist on $[m]$? For $k
 [Permanent event link]
 CARMAGTA DISCRETE MATHEMATICS INSTRUCTIONAL SEMINAR
 Speaker: Prof Brian Alspach, CARMA, The University of Newcastle
 Title: The EdmondsFulkerson matroid partition theorem
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 5^{th} May 2011
 Abstract:
We meet this Thursday at the usual time when I will show you a nice application of the EdmondsFulkerson matroid partition theorem, namely, I'll prove that Paley graphs have Hamilton decompositions (an unpublished result).
 [Permanent event link]
 CARMA DISCRETE MATHEMATICS SEMINAR
 Speaker: Prof Brian Alspach, CARMA, The University of Newcastle
 Title: Discrete Maths Seminar: Introductions
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 24^{th} Feb 2011
 Abstract:
This is a discrete mathematics instructional seminar commencing 24 Februaryto meet on subsequent Thursdays from 3:004:00 p.m. The seminar will focus on "classical" papers and portions of books.
 [Permanent event link]

