• CARMA DISCRETE MATHEMATICS SEMINAR
  • Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
  • Title: Suk's proof of the asymptotic Erdos-Szekeres conjecture
  • Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Wed, 1st Jun 2016
  • Abstract:

    I continue the discussion of the Erdos-Szekeres conjecture about points in convex position with an outline of the recent proof of an asymptotic version of the conjecture.

  • [Permanent link]


  • CARMA DISCRETE MATHEMATICS SEMINAR
  • Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
  • Title: The Erdos-Szekeres conjecture about points in convex position
  • Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Wed, 25th 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 n-gon. 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, 30th 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 union-closed sets conjecture
  • Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Wed, 9th Mar 2016
  • Abstract:

    I'll continue to discuss Frankl's union-closed sets conjecture. In particular I'll present two possible approaches (local configurations and averaging) and indicate obstacles to proving the general case using these methods.

  • [Permanent link]


  • CARMA DISCRETE MATHEMATICS SEMINAR
  • Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
  • Title: The union-closed sets conjecture
  • Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Wed, 2nd Mar 2016
  • Abstract:

    Peter Frankl's union-closed 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: The Kemnitz conjecture and other zero-sum problems
  • Location: Room V31, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Thu, 10th Sep 2015
  • Abstract:

    I will complete the proof of the Kemnitz conjecture and make some remarks about related zero-sum problems.

  • [Permanent link]


  • CARMA DISCRETE MATHEMATICS SEMINAR
  • Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
  • Title: Using polynomials to prove things in combinatorics
  • Location: Room V31, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Thu, 3rd Sep 2015
  • Abstract:

    After briefly describing a few more simple applications of Alon's Nullstellensatz, I will present in detail Reiher's amazing proof of the Kemnitz conjecture regarding lattice points in the plane.

  • Download: Seminar slides (148K)
  • [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, 27th 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, 1st 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, 8th 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, 29th 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 NP-hard.

  • [Permanent link]


  • CARMA DISCRETE MATHEMATICS INSTRUCTIONAL SEMINAR
  • Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
  • Title: Dependent Random Choice III
  • Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Thu, 24th Nov 2011
  • Abstract:

    Thomas will be finishing his talks this Thursday where he will finish looking at (parts of) the survey paper Dependent Random Choice by Jacob Fox and Benny Sudakov: http://arxiv.org/abs/0909.3271

  • [Permanent link]


  • CARMA-GTA 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, 17th 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, Ramsey-Turan), 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-GTA 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, 10th 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, Ramsey-Turan), 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, 28th 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 k-set or l-set 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]