Programme of the DIAMANT symposium
Hotel Veldenbos, Nunspeet
31 May and 1 June 2012

arrival and coffee
Ronald de Wolf
Exponential Lower Bounds for Polytopes in Combinatorial Optimization
We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut problem and the stable set problem. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs. Joint work with Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary.
Jop Briët  Violating the Shannon capacity of a graph with quantum entanglement
The Shannon capacity of a graph G gives the maximum asymptotic rate at which messages can be sent with zero probability of error through a noisy communication channel with confusability graph G. This extensively studied graph parameter disregards the fact that on atomic scales, Nature behaves in line with quantum mechanics. Entanglement, arguably the most counterintuitive feature of the theory, turns out to be a useful resource for communication across noisy channels. In this talk I present a large and simple family of graphs for which the entangled capacity exceeds the Shannon capacity, adding to two isolated examples found earlier by Leung, Mancinska, Matthews, Ozols and Roy (2012), which show that entanglement can increase the asymptotic rate of zero-error communication over discrete memoryless channels. Joint work with Harry Buhrman and Dion Gijswijt.
Rob Eggermont
Degree bounds on tree models
Tree models are families of probability distributions used in modelling the evolution of a number of extant species from a common ancestor. One method to describe these models is to view a family as a set in the m-fold tensor product of a vectorspace V, where m is the number of extant species, and to try to find polynomial equations that determine its Zariski closure. One important question in this area of research is the following: Can we bound the degree of the equations we need independently of the number of extant species? In this talk, I will tell a bit more about these models and will explain how to prove the existence a bound on the degree of the needed equations by constructing an infinite limit of models of a specific form.
Janne Kool
Dynamics measured in a non-Archimedean field
The study of dynamical systems using measure-theoretic methods has shown to be extremely useful. In almost all results real or complex valued measures are used. However, there exists theories in which measures take values in other fields, in particular non-Archimedean fields. In this talk I will discuss natural translation of several notions, e.g., probability measures, isomorphic transformations, conjugate transformations, from classical dynamical systems to a non-Archimedean setting.
Jinbi Jin
Multiplication by n on elliptic curves over arbitrary rings
For elliptic curves over fields given by a Weierstrass equation, it is one of the basic facts that the multiplication by n map can be given in terms of so-called division polynomials. In this talk, I will generalise this fact for elliptic curves given by a Weierstrass equation over arbitrary rings.
Christiane Frougny
On parallel addition in non-standard numeration systems
16:45-17:40 It is well known that addition in a classical numeration system has a worst time linear complexity, which is too low to design an efficient arithmetical unit. In 1961, Avizienis gave a parallel algorithm for addition in base 10 with digit set {-6, -5, ..., 5, 6} where the carry does not propagate. This gives a constant time complexity (in parallel). In the language of symbolic dynamics, such an addition is a sliding block code function, also called a local function. The Avizienis technique is mainly used to fasten multiplication and division algorithms.
In this talk we consider positional numeration systems where the base is an algebraic number beta, |beta|>1. We show that when all the algebraic conjugates of beta have a modulus different from 1, it is possible to find a finite alphabet of signed digits on which parallel addition is possible. This algorithm is a generalisation of the one of Avizienis. The algorithm is quite simple, but the obtained alphabet can be larger than necessary. We then give lower bounds on the minimal cardinality of an alphabet of contiguous integer digits allowing parallel addition. We then develop several cases on which the lower bound is attained: negative base, complex base -1+i, quadratic Pisot units. We also consider the case of a rational base a/b, b >1. Work in collaboration with Edita Pelantová and Milena Svobodová (CTU, Prague)
Friedrich Eisenbrand
Diameter of Polyhedra: Limits of abstraction and new upper bounds
One of the most prominent mysteries in convex geometry is the question whether the diameter of a polyhedron can be bounded by a polynomial function in the dimension and its number of facets. The best known upper bound is n^{ log d +1}  (Kalai & Kleitman 1992) while no super linear lower bound is known. In this talk I will explain that this quasi polynomial bound also holds for very simple abstractions of polyhedral graphs and I will provide a super linear lower bound in this abstract setting. I will also discuss new upper bounds on the diameter of polyhedra that are polynomial in the maximum sub-determinant of the defining matrix and the dimension. This new bound improves upon a previous result of Dyer and Frieze in the setting of polyhedra defined by totally unimodular matrices.
The talk is based on joint work with N. Bonifas, N. Hähnle, S. Razborov, M. Niemeier and T. Rothvoss.
Rutger Kuyper   Logic & Probability
We will study a non-classical logic in which the universal quantifier is interpreted as 'for almost all x' (in the sense of 'with high probability') instead of 'for all x', but in which the existential quantifier retains its classical interpretation. This way, one can decide if a formula holds in some model by amassing enough (but a finite amount of) evidence, unlike in classical logic. The mathematical theory behind our logic diverges from the classical theory at various points and the proofs require different techniques. In this talk, I will introduce the logic and give an overview of the results we have obtained so far.
Shoumin Liu
Brauer algebras of non-simply laced type
It is a very classical knowledge that simple groups of Lie types of non-simply laced type can be attained from the simply laced ones by considering nontrivial automorphisms of their Dynkin diagrams. This idea was extended to a more general theory called admissible partition by Muhlherr in the 1990s. In this talk, we apply these ideas to the Brauer algebras of simply-laced type which are studied by
Cohen, Frenk and Wales and dene Brauer algebras of non-simply laced type by generators and relations. We prove that they are free, compute their ranks and find bases by use of combinatorial data on their root systems; we also prove their cellularity in the sense of Graham and Lehrer.
Guus Regts
On limits of edge coloring models
11:30-11:50 In this talk we consider limits of edge coloring models. Any linear function h on the polynomial ring in n variables is called an n-color edge coloring model. The partition function of h is a graph parameter p(F,h) (where F is a graph). We call a sequence (h^i) of edge coloring models convergent if for every simple graph F, the sequence(p(F_i,h)) has a limit. In this talk I will describe limit objects for convergent sequences of real edge coloring models; they can be seen as elements of the (real) polynomial ring in infinitely many variables. This work is closely related to and inspired by the recent theory of graph limits developed by Lovász, Szegedy and others. I will also say something about this relation. This talk is based on joint work with A. Schrijver.
Andrea Siviero
Equidistribution of the Galois module structure of ring of integers with given local behavior
Let K be a number field and let G be a finite abelian group. A couple of years ago Melanie Wood studied the probabilities of various splitting types of a fixed prime in a random G-extension of K. When the number fields are counted by conductor, she proved that the probabilities are as predicted by a heuristic and independent at distinct primes. In the same period Adebisi Agboola studied the asymptotic behavior of the number of tamely ramified G-extensions of K with ring of integers of fixed realizable class as a Galois module, proving that an equidistribution result exists when the extensions are counted by conductor. One natural question is: are the two distributions of Wood and Agboola independent? In this talk I will briefly give the answer to this question when we require a totally split local behavior.
Piotr Zwiernik
Graphical Gaussian models and their groups
Let G be an undirected graph with n nodes. Let S(G) be the set of all (n x n) real symmetric, positive definite matrices with zeros corresponding to non-edges of G.  We describe the stabilizer of S(G) in GL_n(R) of the model, in the natural action of GL_n(R) on symmetric matrices. The main motivation for this work is in statistics, where S(G) is identified with the graphical Gaussian model on G. Our results have important consequences for the study of the maximum likelihood inference for this model class. This is a joint work with Jan Draisma and Sonja Kuhnt.
14:00-14:20 tea
Sam Payne
Tropical Brill-Noether theory
Classical Brill-Noether theory studies the geometry of special divisors on smooth projective curves, with special attention to the existence of special divisors on the general curve of genus g. One fundamental result of the theory, called the Brill-Noether Theorem and due to Griffiths and Harris, says that a general curve of genus g has a divisor of degree d that moves in a linear system of dimension r if and only if g is at least (r+1)(g-d+r). The original proof uses a degeneration to a rational curve with g nodes, plus a very subtle transversality argument for certain associated Schubert cycles. I will present a new ``tropical" approach to the Brill-Noether Theorem, using the combinatorics of chip-firing, and the theory of ranks of divisors on graphs, introduced by Baker and Norine. This talk is based on joint work with Filip Cools, Jan Draisma, and Elina Robeva.

Mathematics cluster DIAMANT

Upcoming events

Diamant symposium
28-11-2019 - 29-11-2019

News - more news

Full professor position in Discrete Mathematics in Delft

Delft Institute of Applied mathematics, Delft University of Technology, seeks a full Professor in the field of Discrete Mathematics. A description of the position can be found here. The deadline for applications is January 15, 2019.

ERC Starting grant for Daniel Dadush

Daniel Dadush (CWI) has been awarded an ERC Starting Grant of 1.5 ME for his proposal ‘Towards a Quantitative Theory of Integer Programming’. With this grant, Dadush aims to revolutionize the understanding of integer programming (IP), the most popular method used today for finding optimal solutions to real-world optimization problems.

Read more.

VICI grant for Nikhil Bansal

Nikhil Bansal has been awarded a Vici grant of 1.5 ME. He is one of the 35 academics to receive this grant from NWO in 2018. Bansal aims to use his grant to develop new algorithmic methods to make discrete decisions in a continuous way. He expects this to lead to applications in the fields of logistics, bio-informatics, chip design and machine learning.

Read more.

3 DIAMANT PhD positions awarded

NWO, following a shortlist provided by the DIAMANT board, has decided to award 3 PhD positions to young DIAMANT members: Dion Gijswijt (TU Delft), Jan Steffen Müller (RUG) and Arno Kret (UvA).
Read more.