 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 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 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 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 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 link]
 CARMA OANT SEMINAR
 Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
 Title: A Social Welfare Optimal Sequential Allocation Procedure
 Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
 Access Grid Venue: CARMA [ENQUIRIES]
 Time and Date: 3:00 pm, Tue, 8^{th} Oct 2013
 Abstract:
There exist a variety of mechanisms to share indivisible goods between agents. One of the simplest is to let the agents take turns to pick an item. This mechanism is parameterized by a policy, the order in which agents take turns. A simple model of this mechanism was proposed by Bouveret and Lang in 2011. We show that in their setting the natural policy of letting the agents alternate in picking items is optimal. We also present a number of potential generalizations and extensions.
This is joint work with Nina Narodytska and Toby Walsh.
 [Permanent link]
 CARMA COLLOQUIUM
 Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
 Title: Incremental network design for minimum spanning trees
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 4:00 pm, Thu, 29^{th} Aug 2013
 Abstract:
(Joint work with Konrad Engel and Martin Savelsbergh)
In an incremental network design problem we want to expand an existing network over several time periods, and we are interested in some quality measure for all the intermediate stages of the expansion process. In this talk, we look at the following simple variant: In each time period, we are allowed to add a single edge, the cost of a network is the weight of a minimum spanning tree, and the objective is to minimize the sum of the costs over all time periods. We describe a greedy algorithm for this problem and sketch a proof of the fact that it provides an optimal solution. We also indicate that incremental versions of other basic network optimization problems (shortest path and maximum flow) are NPhard.
 [Permanent 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 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 link]
 CARMA COLLOQUIUM
 Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
 Title: Maximal antichains on two levels of the Boolean lattice
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 4:00 pm, Thu, 28^{th} Oct 2010
 Abstract:
We are looking at families of finite sets, more specifically subsets of [n]={1,2,...,n}. In particular, we are interested in antichains, that means no member of the family is contained in another one. In this talk we focus on antichains containing only sets of two different cardinalities, say k and l, and study the question what the smallest size of a maximal antichain is (maximal in the sense that it is impossible to add any kset or lset without violating the antichain property). This can be nicely reformulated as a problem in extremal (hyper)graph theory, looking similar to the TurĂ¡n problem on the maximum number of edges in a graph without a complete subgraphs on l vertices. We sketch the solution for the case (k,l)=(2,3), conjecture an optimal construction for the case (k,l)=(2,4) and present some asymptotic bounds for this case.
 [Permanent link]
