# Abstracts

 Maya Stein (Universidad de Chile) The Loebl-Komlos-Sos conjecture: the regularity approach A typical question in extremal graph theory is to ask how certain substructures can be forced to appear in a graph by global assumptions, for example on the degrees of the vertices of the graph. One example is the Loebl-Komlos-Sos conjecture, which says that if at least half of the vertices of a graph G have degree at least k, then G contains all trees with at most k edges as subgraphs. During the last years, several forms of the conjecture have been proved (by several authors) using the regularity method. These version include the k=|G|/2 case and the approximate and the exact version of the original conjecture for large graphs. In this talk, we would like to expose the main idea behind these proofs, namely the application of Szemeredi'a regularity lemma to the host graph G and a certain treatment of the tree to be embedded in G. If time allows, we also discuss adaptions of the method for the sparse case of the conjecture. Samuel Mimram (ENS Lyon) Algebraic tools in game semantics Game semantics consists in interpreting logics and programming languages as games and strategies. One of the main difficulties, in order to have a really interesting and informative semantics, consists in characterizing definable strategies, that is strategies which are the interpretation of a proof or a program. We introduce here a new methodology in order to achieve this task, based on the notion of presentation of a category (by the means of generators and relations). It is illustrated on a simple semantics of first-order propositional logic, which is shown to be presented by a polarized variant of the algebraic theory of bicommutative bialgebras. The contents of this presentation is available in conference version : http://www.pps.jussieu.fr/~smimram/docs/mimram_lics09.pdf or in preliminary journal version : http://www.pps.jussieu.fr/~smimram/docs/mimram_first_order_causality_long.pdf Mark Broom (City University) Models of Evolution on Structured Populations We investigate two examples of models of populations with structure. These are different in character, with the common theme that the structure has an important influence on population outcomes. In the first part we consider a model of kleptoparasitism, the stealing of food from one animal by another. We investigate a model where individuals are allowed to fight in groups of more than two, as often occurs in real populations, but which has not featured in previous theoretical models. We find the equilibrium distribution of the population amongst various behavioural states, conditional upon the strategies played and environmental parameters, and then find evolutionarily stable strategies (ESSs) for the challenging behaviour of the participants. We show that ESSs can only come from a restricted subset of the possible strategies and that there is always at least one ESS. We show that there can be multiple ESSs, and indeed that the number of ESSs is unbounded. Finally we discuss the biological circumstances when particular ESSs occur in terms of key parameters such as the availability of food and the cost of fighting. The second part of the talk concerns the study of evolutionary dynamics on populations with some non-homogeneous structure, a topic in which there is a rapidly growing interest. We investigate the case of non-directed equally weighted graphs and find solutions for the fixation probability of a single mutant in two classes of simple graphs. This process is a Markov chain and we prove several mathematical results. For example we prove that for all but a restricted set of graphs, (almost) all states are accessible from the possible initial states. We then consider graphs within this restricted set or with considerable symmetry. To find the fixation probability of a line graph we relate this to a two-dimensional random walk which is not spatially homogeneous. We investigate our solutions numerically and find that for mutants with fitness greater than the resident, the existence of population structure helps the spread of the mutants. Thus it may be that models assuming well-mixed populations consistently underestimate the rate of evolutionary change. Luitgard Veraart (LSE) The relaxed investor with partial information We consider an investor in a financial market consisting of a riskless bond and several risky assets. The price processes of the risky assets are geometric Brownian motions where either the drifts are modelled as random variables assuming a constant volatility matrix or the volatility matrix is considered random and drifts are assumed to be constant. The investor is only able to observe the asset prices but not all the model parameters and hence information is only partial.  A Bayesian approach is used with known prior distributions for the random model parameters. We assume that the investor can only trade at discrete time points which are multiples of h>0 and investigate the loss in expected utility of terminal wealth which is due to the fact that the investor cannot trade and observe continuously. It turns out that in general a discretization gap appears, i.e for $h \to 0$ the expected utility of the h-investor does not converge to the expected utility of the continuous investor. This is in contrast to results under full information in(Rogers, L.C.G. 2001. The relaxed investor and parameter uncertainty. Finance and Stochastics, 5 (2), 131-154). We also present simple asymptotically optimal portfolio strategies for the discrete-time problem. Our results are illustrated by some numerical examples. This is joint work with Nicole Bäuerle and Sebastian Urban. Olof Sisask (Queen Mary, University of London) Arithmetic progressions in sums of low-density sets If A is a subset of the integers {1,...,N} of size alpha*N, how long an arithmetic progression must the sumset A+A = { a + b : a, b in A } contain? This question has been studied by several people, including Bourgain, Ruzsa and Green, who have given good lower and upper bounds for the answer when alpha is roughly at least 1/sqrt(log N). In this talk I shall discuss an approach to finding long arithmetic progressions in A+A when alpha can be as low as roughly 1/log N, with a relatively simple application of the probabilistic method being the main tool. The approach is quite different to previous ones, allowing also for a partial extension to non-commutative groups. Based on joint work with E. Croot. Abraham Neyman (Centre for the Study of Rationality, The Hebrew University of Jerusalem) Generalized Discounted Stochastic Games and Applications This work contributes to three seemingly unrelated topics: 1) Symmetric Nash Equilibrium, 2) Cardinal utilities over outcomes of multi-stage interactions, and 3) stochastic games. Each contribution is of independent interest, and in addition, we unveil hidden connection between these three topics. The continuous and stationary cardinal utilities defined on infinite sequences z_1, a_1, z_2, ... of states z_t in S and activities/consumptions a_t in A are characterized. Such infinite sequences arise explicitly as plays of a stochastic game with state space S and set of action profiles A or as the feasible economy evolutions where z_t is a state variable describing the available technology and/or information and/or preference at stage t and at describes the economic activity at stage t. Such infinite sequences arise also implicitly in the study of nonstationary cardinal utilities over streams of consumptions/actions a_1, a_2, ... where z_t represents the implicit preferec over the future given the past consumption/activity. It is proved that any stochastic game with finitely many states and actions and a continuous and stationary payoff function has a subgame perfect equilibrium consisting of stationary strategies. Mitch Keller (LSE) Interval Partitions and Stanley Depth This talk will explore a combinatorial partitioning problem for certain partially ordered sets. The problem has its origins in a 1982 commutative algebra conjecture of R.P. Stanley. The problem was attacked using purely algebraic techniques with limited success until recently, when Herzog, Vladoiu, and Zheng established a connection between algebraic decompositions of a monomial ideal and partitions of a poset associated to the ideal into intervals. (An interval [c,d] in a poset is {x : c <= x <=d}.) This connection has led not only to additional results on Stanley depth but also to interesting and elegant combinatorics. While the talk will begin with a brief look at the algebraic motivation for the problem, I will focus almost exclusively on the combinatorics involved in the research. For the principal result, I will give two different proofs that are both quite nice. One is recursive and the other is a direct construction. This talk contains joint work (in various combinations) with Csaba Biro, David M. Howard, Yi-Huang Shen, Noah Streib, William T. Trotter, and Stephen J. Young. Ryan Martin (Iowa State University) Recent results on the edit distance of graphs In this talk, we will discuss the edit distance function, a function of a hereditary property $\mathcal{H}$ and of $p$, which measures the maximum proportion of edges in a density-$p$ graph that need to be inserted/deleted in order to transform it into a member of $\mathcal{H}$. We will describe a method of computing this function and give some results that have been attained using this method. The edit distance problem has applications in property testing and evolutionary biology and is closely related to well-studied Tur\'an-type problems. This is joint work with Tracy McKay, Iowa State University. Ron Lavi (Technion-Israel Institute of Technology) Side-Communication Yields Efficiency of Ascending Auctions: TheTwo-Items Case We analyze the realistic, popular format of an ascending auction with anonymous item-prices, when there are two items that are substitutes. We describe an ex-post (subgame perfect) equilibrium of this auction, that uses limited side-communication. This equilibrium is ex-post efficient. Thus while plain intuition may suggest that side-communication (interpreted as collusion) reduces social efficiency, our result indicates that the opposite may be true. In contrast, without side-communication, we show that there is no ex-post equilibrium which is ex-post efficient in the ascending auction. In the equilibrium strategy we suggest, bidders start by reporting their true demands at the first stages of the auction, and then perform a single demand reduction at a certain concrete point, determined using a single message exchanged be- tween the players. This limited collusion opportunity resolves the strategic problems of myopic bidding, and, quite surprisingly, improves the social welfare instead of harming it. (Joint work with Sigal Oren, Cornell University) Harry Miller (International University of Sarajevo) Old and new problems in Analysis Karoly Bezdek(Calgary, Canada) Plank problems - the discrete geometric side In the 1930's, Tarski introduced his plank problem at a time when the field Discrete Geometry was about to born. It is quite remarkable that Tarski's question and its variants continue to generate interest in the geometric and analytic aspects of coverings by planks in the present time as well. The lecture is of a survey type with some new results and with a list of open research problems on the discrete geometric side of the plank problem. Richard Steinberg (LSE) Pricing of Media Service Provision We consider the problem of how to price media service provision under competition. Specifically, a Media Service Provider (MSP) is an Internet Service Provider that offers basic Internet service plus additional media service. An example of such additional service would be unlimited music file downloads. Users have differing preferences for the additional media service. The question is: What fee should the MSP charge customers in a competitive environment? We present two game theoretic models. In the first model, there are two network providers, an Internet Service Provider offering basic Internet service and a Media Service Provider. In the second model, in addition to the two network providers, the ISP and the MSP, there is also an independent content provider that offers the same media service as the MSP but relies on the ISP to provide delivery of the media service to customers. (Joint work with Peter Key, Microsoft Research Cambridge.) Doreen Thomas (University of Melbourne) Optimisation of Underground Mine Networks Reducing the cost of mining operations is an important issue for mine developers and operators faced with an extremely competitive market place for mineral commodities. When developing a new mine, or an extension to an existing mine, the overarching aim is to maximise the value of the mine. The planning of such underground mines can be viewed as a process that involves a number of fundamental decisions and design tasks, including the design of the access. In underground mines, ore is typically accessed via a network of interconnected underground tunnels, called declines, and then transported to the surface. The declines used for trucking ore to the surface have to satisfy a gradient and turning circle constraint so that the large haulage trucks can navigate them. The access optimisation problem involves designing this network of declines so as to minimise the cost of development and haulage subject to these constraints. In this talk I describe mathematically modelling this access problem as a network optimisation problem and I will talk about a decline optimisation software tool, DOT, that we have developed to design an access network.  I also discuss a recent case study where we used DOT to provide a number of designs for the new gold and copper mine at Prominent Hill owned by OZ Minerals. This research is part of a large industry research project, PRIMO (Planned and Rapid Integrated Mine Optimisation), organised by AMIRA and sponsored by Newmont Asia Pacific, Rio Tinto, OZ Minerals, BHP Billiton, Barrick Gold, Vale Inco, Xstrata  as well as three mining software suppliers, Datamine, GijimaAST and Maptek.   This work is done in collaboration with Dr Marcus Brazil and Dr Peter Grossman, Department of Electrical and Electronic Engineering; Professor Hyam Rubinstein, Department of Mathematics; and Professor Nick Wormald, the University of Waterloo. Leszek Gasieniec (University of Liverpool) Location aware asynchronous rendezvous in discrete 2D-spaces We discuss efficient rendezvous of two anonymous robots located in a discrete Euclidean 2D-space represented by an infinite 2D-grid with integer coordinates. We assume that each robot knows its own initial location. The robots, however, are not aware of positions of one another. This model is equivalent to a standard geometric model in which the robots possess: coherent compasses, the same unit of length, and a limited visibility allowing them to encounter one another at a fixed range. We present an efficient explicit construction of "space-covering sequences" embedded into a discrete 2D-space, a novel concept that allows two robots located at a distance of d to meet after adopting a trajectory of a length of O(d^{2+e}), for any constant e > 0. Further, we provide an improvement that leads to an almost optimal asynchronous rendezvous of a length of O(d^2\log^7 d). Finally, we show how to adopt our rendezvous methods to efficient gathering of a larger number of robots and we provide a list of related open problems. Joint work with: Evangelos Bampas, Andrew Collins, Jurek Czyzowicz, David Ilcinkas, and Arnaud Labourel. Tristan Tomala (HEC Paris) Mechanism Design and Communication Networks Mechanism design theory studies which decisions can be implemented by an equilibrium of a communication game between players who are informed of their characteristics and a designer who chooses an outcome. The well-known revelation principle states that for every such game, its equilibria can be implemented by direct and private communication between the players and the designer. On another hand, computer science often models communication possibilities by means of communication networks where agents are linked when they have the ability to communicate privately. The aim of our work is to characterize the (directed) communication networks which are as good as direct and private communication. Namely, those networks for which any equilibrium outcome of a direct communication game can be replicated by an equilibrium of the game of communication within the network. Our main result shows that in environments (utilities and beliefs) with a worst outcome, a necessary and sufficient condition is that the network be strongly 1-connected (each player has a directed path to the designer in the network) and weakly 2-connected (each player has two disjoint undirected paths to the designer in the underlying undirected graph). The proof relies on the construction of communication protocols in directed graphs with the following properties: -the designer correctly learns all types, -no player gets extra information about other players' types, -any deviation is detected with arbitrarily high probability by the designer. Eran Shmaya (Kellog School of Management) Expressible tests need not be manipulable A decision maker needs predictions about the realizations of a repeated experiment in each period. An expert provides a theory that, conditional on each finite history of realizations, supplies a probabilistic prediction. However, there may be false experts without any knowledge of the data-generating process who may deliver theories strategically. Hence, empirical tests for these theories are necessary. A test is manipulable if a false expert can pass the test with a high probability. For the theories to be deliverable and for tests to be implementable, they have to be computable. Consider only computable theories and tests, we show that there is a test that is not manipulable and that accepts true experts with high probabilities. In particular, the constructed test is both future independent (Olszewski and Sandroni (2008)) and sequential. Our conclusion overturns earlier results that future independent tests are manipulable, and shows that computability considerations have significant effects in these problems. Ken Binmore (UCL) Sexual Drift What is sex good for? This paper argues that one of its uses may be to get a species from one equilibrium to another when the environment changes so that the first equilibrium becomes inferior. Karl Schlag (Universitat Pompeu Fabra) Finite Sample Nonparametric Tests for Linear Regressions We introduce several exact nonparametric tests for finite sample multivariate linear regressions, and compare their powers. This fills an important gap in the literature where the only known nonparametric tests are either asymptotic, or assume one covariate only. John Bell(University of Western Ontario, Canada) Continuity and Infinitesimals My talk will outline the development of the concept of the continuum - and the related concept of the infinitesimal - over the past 2 1/2 millenia. I shall be leaving for London on May 2. Could you provide me with a contact number? Colin McDiarmid(Statistics, University of Oxford) Random graphs with few disjoint cycles Fix a positive integer k, and consider the class of all graphs which do not contain k+1 vertex-disjoint cycles. A classical result of Erdos and Posa says that each such graph G contains a blocker of size at most f(k), where a blocker means a set B of vertices such that G-B has no cycles. From a minor extension of this result, we deduce that almost all such labelled graphs on vertex set 1,..,n have a blocker of size just k. This yields an asymptotic counting formula for such graphs; and allows us to deduce further properties of a graph R_n taken uniformly at random from the class: we see for example that the probability that R_n is connected tends to a specified limit as n tends to infinity. We consider also variants of the problem involving for example disjoint long cycles or other excluded minors for suitable classes of graphs. This is joint work with Valentas Kurauskas. Yannick Viossat  (Paris-Dauphine) Time-Average Replicator and Best-Reply Dynamics Evolutionary game dynamics model the evolution of behavior in populations of boundedly rational agents interacting repeteadly. The two most studied dynamics are the replicator dynamics and the best reply dynamics. The motivations and mathematical expressions of these dynamics are quite different. The former is the prototype of nonrational dynamics, the later of rational (though myopic) dynamics. Nevertheless, it has been noted heuristically that, in many games, the time average of the replicator dynamics behaves in the long run as the best reply dynamics. We largely explain this heuristics by showing that the time average of the replicator dynamics is a perturbed solution of the best reply dynamics. Dan Archdeacon (University of Vermont, USA) Monohedral Tilings Given infinitely many copies of a single tile, when does it tile the plane? The answer is not as simple as you think. In this talk I'll survey results in this area, including some recent work with Carsten Thomassen (Technical University of Denmark). Imre Leader (Cambridge) Higher Order Tournaments Jozef Siran (Open University) Residual finiteness and highly symmetric maps A group is residually finite if for any non-identity element the group contains a subgroup of finite index avoiding the chosen element. Among the important classes of residually finite groups are automorphism groups of tessellations of the infinite plane. Since any map on some surface, and in particular any `highly symmetric' map, is a quotient of such a tessellation, residual finiteness may help proving theorems for highly symmetric maps. We outline the corresponding theory and give illustrative examples. Thomas Erlebach(University of Leicester) Domination Problems in Geometric Intersection Graphs Dominating set problems in geometric intersection graphs are motivated, for example, by the construction of routing backbones in wireless ad-hoc networks. While the approximability of the dominating set problem is well understood for general graphs, the situation is less clear for graph classes such as unit disk graphs, arbitrary disk graphs, or intersection graphs of other geometric objects. In this talk we give an overview of progress that has been made on these problems in recent years, both for weighted and unweighted problem variants. Among other results, we discuss a general technique yielding constant-factor approximation algorithms for intersection graphs of scaled, translated copies of an r-regular polygon, and a (4+epsilon)-approximation approximation algorithm for weighted dominating sets in unit disk graphs. The talk is based on joint work with Erik Jan van Leeuwen and Matus Mihalak. Bill Jackson(Queen Mary, University of London) A zero-free interval for chromatic polynomials of 3-connected planar graphs It is known that (-\infty,0), (0,1) and (1,32/27] are the only zero-free intervals for chromatic polynomials of graphs. It seems likely however that the interval (1,32/27] can be extended to the right for the family of 3-connected graphs. I will describe a joint result with Fengming Dong which shows that this is true for planar graphs. Dan Hefetz (ETH Zürich) On two generalizations of the Alon-Tarsi polynomial method Abstract: In a seminal paper, Alon and Tarsi have introduced an algebraic technique for proving upper bounds on the choice number of graphs (and thus, in particular, upper bounds on their chromatic number). The upper bound on the choice number of G obtained via their method, was later coined the Alon-Tarsi number of G and was denoted by AT(G). They have provided a combinatorial interpretation of this parameter in terms of the eulerian sub-digraphs of an appropriate orientation of G. Shortly afterwards, for the special case of line graphs of d-regular d-edge-colorable graphs, Alon gave another interpretation of AT(G), this time in terms of the signed d-colourings of the line graph. In the talk I will generalize both results. I will then use these results to prove some choosability results. In the first part of the talk I will introduce chromatic, choice, and Alon-Tarsi numbers of graphs. In the second part I will state the two generalizations as well as some applications. Miklós Reiter (University of Cambridge) A Game-Theoretic Model for Pricing Internet Service We model the interaction between Internet Service Providers on a two-segment network as a game where the players set prices in order to maximize profit. First, we extend the Bertrand-Edgeworth price competition game with capacity constraints to the case where part of the players' capacity is sold under long-term contracts, proving the existence and uniqueness of pure and mixed (random) strategy equilibria in different demand regions. Next, we add a player controlling the upstream network link, and prove price equilibrium conditions in the two-segment network. In the region of intermediate demand, a pure strategy equilibrium fails to exist. Here, we prove the existence of a unique equilibrium point where every downstream player chooses an optimal mixed strategy and the upstream player chooses a locally optimal pure strategy. The full model is a two-stage game where the competing downstream players choose to sell bandwidth using long-term forward contracts in the first stage, and all players set prices in the second stage. Although players have an incentive to enter into long-term contracts, as it makes their profit more predictable, we show that contracting can put downstream players at a strategic disadvantage in the second stage. However, if one downstream player chooses a low contracting level in the first stage, this raises prices for all downstream players in the second stage. We show that a pure strategy contracting equilibrium is necessarily asymmetric, with a unique lowest contracting level. Joint work with Richard Steinberg. A pdf of this talk can be found here. Boris Bukh (University of Cambridge) Sum-product theorems for polynomials Suppose A is a set of numbers and f(x,y) is a polynomial, how small can f(A,A) be? If f(x,y)=x+y or f(x,y)=xy, then f(A,A) can be very small indeed if A is a progression. However, Erdős and Szemerédi proved that A+A and AA cannot be simultaneously small when A is a set of real numbers. Their results has been generalised to other rings, and have found numerous applications in number theory, combinatorics, theoretical computer science, and other fields. In this talk, I will survey the classical sum-product estimates, and will discuss several new results for other polynomial functions f. Joint work with Jacob Tsimerman. Amarpreet Rattan (University of Bristol) Lattice paths below a cyclically shifting boundary We count the number of lattice paths lying under a cyclically shifting piecewise linear boundary of varying slope. Our main result extends well known enumerative formulae concerning lattice paths, and its derivation involves a classical reflection argument. A refinement allows for the counting of paths with a specified number of corners. We also give various applications to recent results in the area of lattice path enumeration. Reto Spöhel (ETH Zürich, Switzerland) Upper bounds for asymmetric Ramsey properties of random graphs Consider the following problem: Is there a colouring of the edges of the random graph $G_{n,p}$ with two colours such that there is no monochromatic copy of some fixed graph $F$? A celebrated result by Rödl and Rucinski (1995) states a general threshold function $p_0(F,n)$ for the existence of such a coluoring. Kohayakawa and Kreuter (1997) conjectured a general threshold function for the asymmetric case (where different graphs $F_1$ and $F_2$ are forbidden in the two colours), and verified this conjecture for the case where both graphs are cycles. Implicit in their work is the following more general statement: The conjectured threshold function is an upper bound on the actual threshold provided that i) the two graphs satisfy some balancedness condition, and ii) the so-called K{\L}R-Conjecture is true for the sparser of the two graphs. We present a new upper bound proof that does not depend on the K{\L}R-Conjecture. Together with earlier lower bound results [Marciniszyn, Skokan, S., Steger (2006)], this yields in particular a full proof of the Kohayakawa-Kreuter conjecture for the case where both graphs are cliques. Joint work with Yoshiharu Kohayakawa and Mathias Schacht. Jan Hladky (University of Warwick) On tree packing conjectures A family of graphs H_1,...,H_k packs into a graph G if there exist pairwise edge-disjoint copies of H_1,...,H_k in G. Gyarfas and Lehel conjectured in 1976 that any family T_1, ..., T_n of trees of respective orders 1, ..., n packs into K_n. A similar conjecture of Ringel from 1963 asserts that 2n copies of any trees T on n+1 vertices pack into K_{2n+1}. We prove a theorem about packing trees. The theorem implies asymptotic versions of the above conjectures for families of trees of bounded maximum degree. Tree-indexed random walks controlled by the nibbling method are used in the proof. This is a joint work with Julia Boettcher, Diana Piguet, and Anusch Taraz.
Share:|||