Programme of the DIAMANT/EIDMA symposium, 29-30 May 2008
||Arrival and coffee|
|11:00-11:55||Mai Gehrke||Pseudo-varieties of finite algebras and duality theory
||Birkhoff's Variety Theorem in universal algebra states that a class ofsimilar algebras is closed under homomorphic images, subalgebras, andproducts if and only if the class is given by equational properties.Reitermann's Theorem is a similar result for classes of finitealgebras, but here one must consider generalised identities obtained byusing terms from a topological (profinite) completion of theappropriate free algebra.
In joint work with Jean-Eric Pin and Serge Grigorieff we haveshown that Reitermann's theorem is a special case of the generaltopological duality theory that relates various non-classical logicswith their relational semantics.
We give a general introduction to this work and illustrate with applications in the theory of finite state automata.
||Curves over finite fields with many rational points|
|(Leiden)||The question how many points a curve over a finite field can have (interms of the base field and the genus of the curve) is natural andelegant, but also remarkably interesting in relation to coding theory.In the case where the cardinality of the base field is the square of aprime number, Ihara and Vladut proved that certain families of modularcurves are optimal in the sense that they attain the so-calledDrinfeld-Vladut upper bound for the number of rational points divided bythe genus.The goal of this talk is to explain a method, due to Elkies, to writedown (very explicitly) equations for such curves and (a bit lessexplicitly) most of their rational points. The construction relies onthe fact that a cyclic isogeny of elliptic curves can, roughly speaking,be specified as a sequence of isogenies of low degree.|
||The Alcuin number of a graph|
||We consider the generalization of Alcuin's river crossing problem(also known as the wolf, goat, and cabbage puzzle) to arbitrary graphs.Now the man has to transport the vertices of a graph across the river.If two of them are connected by an edge, they are conflicting and thuscannot be left alone together without human supervision.We derive algorithmical, and complexity theoretical results around this problem.Joint work with Cor Hurkens and Gerhard Woeginger.|
|14:45-15:10||Jaroslaw Byrka||New Algorithms for Approximate Nash Equilibria in Bimatrix Games|
|(Eindhoven and CWI)||We consider the problem of computing additively approximate Nashequilibria in non-cooperative two-player games.We first provide a simple algorithm, that achieves a0.38197-approximation, which is exactly the same factor as the algorithmof Daskalakis, Mehta and Papadimitriou. This algorithm is then tuned,improving the approximation error to 0.36392.Our method is relatively fast, as it requires solving only one linearprogram and it is based on using the solution of an auxiliary zero-sumgame as a starting point.We also exhibit a simple reduction that allows us to compute approximateequilibria for multi-player games by using algorithms for two-playergames.|
||Another step in formalizing Fermat's Last Theorem|
||My master's thesis involves a project in mechanized theorem proving. Starting from scratch I tried to formally prove the cases n=4and n=3 of Fermat's Last Theorem. One motivation for this research is the list of 'ten challenging research problems in computer science' fromJan Bergstra, leaded by: "Formalize and verify by computer a proof of Fermat's Last Theorem."
In my talk I will give an impression of what it is like for a mathematician to get started with proof assistants, with a special focus on number theory in 'Isabelle'.
||Thomas Hales||The Kepler conjecture and the Flyspeck project|
||The Kepler conjecture asserts that no packing of congruent ballsin three dimensional Euclidean space has density greater than the face-centeredcubic packing. It has now been nearly ten years since the proof ofthat conjecture was completed. The proof runs hundreds of pages andrelies on long computercalculations. This talk will describe the original proof and givedetails about an ongoing project, called Flyspeck, designed to give aformal proof ofthis result.|
||Secretary Problems and Online Auction Design|
|(CWI)||This talk considers the problem of online auction design, or auctions for bidders who arrive and depart over time. Maximizing welfare in such auctions is complicated by the fact that bids must be accepted or rejected at the moment they are submitted. It is known how the classic secretary problem introduced by Dynkin in 1963 can be used to design approximately welfare-maximizing auctions in a simple multi-unit auction setting. We show how the classic secretary problem can be generalized to a combinatorial
setting, and use this generalization to build mechanisms for a class of online combinatorial auctions.
||The polynomial automorphism group over finite fields|
|(Nijmegen)||A polynomial map in this talk is a map kn → kn (where k is afield) given by polynomials. If it has a polynomial map inverse, thenit is called a polynomial automorphism, and we can talk about thepolynomial automorphism group. For example, (X+Y2,Y) is a polynomial automorphism with inverse (X-Y2,Y).
Out of habit, polynomial automorphisms are mostly studied overfields of characteristic zero (also by me!), with only the occasional``free'' generalisation to characteristic p -Let alone polynomial maps over finite fields. There are two reasons to jump into this hiatus.
The first is, that certain problems over characteristic zero can be solved by ``reduction mod p'' techniques. For example,the fact that an injective polynomial map is automaticallysurjective, follows from the fact that a map from a finite set which isinjective, is automatically surjective. Another amazing result likethis was recently obtained by Belov and Kontsjevich.
The second is that any map from a finite field vector space can beinteresting for other, discrete-oriented research fields. I know onlyone or two of such implications, but one of the reasons for me to talkabout this subject is to get some input from the audience.
One of the questions that I will answer is which bijections (Fq)n → (Fq)n of the n-dimensional vector space over Fq can be obtained bypolynomial maps. I will apply this viewpoint to the problem offinding generators for the automorphism group, which is an open problemin dimension 3 and up.
Those in the audience who love characteristic 2 anomalies will be pleased.
||Lie algebras over fields of small characteristic|
|(Eindhoven)||Algorithms exist and have been implemented to compute Chevalley basesfor Lie algebras. Unfortunately, these algorithms break down over fieldsof characteristic 2 and 3. We give an overview of the difficulties thatarise, and propose several solutions.|
|12:00-12:25||Willem Jan Palenstijn||Enumerating ABC-triples|
|(Leiden)||An ABC-triple is a triple of coprime positive integers a, b, c with a +b = c for which the product of primes dividing abc is below c. TheABC-conjecture, considered one of the current holy grails of numbertheory, describes the behaviour of these triples. The distributedcomputing project at www.abcathome.com is enumerating all ABC-triples upto a certain bound. In this talk we will describe the algorithm used andlook at some questions raised by the available data.|
||Special values of L-functions: conjectures, variations, computations
|(Leiden)||I shall explain (assuming a non-expert audience), how a veryelegant conjecture of Deligne, Beilinson and Scholl unifies number theoreticalresults and conjectures such as the class number formula, the Birchand Swinnerton-Dyer conjecture, and Borel's theorem on values ofzeta functions at integral points. Some variations to this conjectureare more or less natural, and are supported by numerical computations. Iwill propose a characteristic p variant, and present some evidence for it.|
|14:45-15:10||Jos in 't panhuis
||The universal embedding of a finite irreduciblecotriangular space|
|(Eindhoven)||A cotriangular space is a partial linear space inwhich each line contains exactly 3 points and each point not on a line iscollinear with either 0 or 2 points of that line. If a cotriangular space isfinite and irreducible, then it is of three possible types: triangular,symplectic or orthogonal. Moreover, it can be embedded into a projective space.For each of the possible types we will give the corresponding universalembedding.|
||Combinatorics of simplicial complexes and Stanley Reisner algebras
from a topological point of view
||Given a finite simplicial complex there are several associated algebraic andtopological invariants, e.g. the Stanley-Reisner algebra andDavis-Januszkiewics spaces which are topological realizations of thesealgebras. The homotopy theory of these spaces is reflectedby combinatorial properties of the complexes. We will discuss twodifferent applications and will relate coloring question of the complexwith splitting properties of vector bundles over theDavis-Janucskiewicz space and depth of the Stanley-Reisner algebra withthe combinatorics of the complex.