ETH Zurich

A subset S of initially infected vertices of a graph G is called forcing if we can infect the entire graph by iteratively applying the following process. At each step, any infected vertex which has a unique uninfected neighbour, infects this neighbour. The forcing number of G is the minimum cardinality of a forcing set in G. It was introduced independently as a bound for the minimum rank of a graph, and as a tool in quantum information theory.

The focus of this talk is on the forcing number of the random graph. Furthermore, we will state our bounds on the forcing number of pseudorandom graphs and related problems. The results are joint work with Thomas Kalinowski and Benny Sudakov.

We study some features of the energy of a deterministic chordal Loewner chain, which is defined as the Dirichlet energy of its driving function in a very directional way. Using an interpretation of this energy as a large deviation rate function for SLE_k as k goes to 0, we show that the energy of a deterministic curve from one boundary point A of a simply connected domain D to another boundary point B, is equal to the energy of its time-reversal i.e. of the same curve but viewed as going from B to A in D. In particular it measures how far does the chord differ from the hyperbolic geodesic. I will also discuss the relation between the energy of the curve with its regularity, some questions are still open. If time allows, I will present the Loewner energy for loops on the Riemann sphere, and open questions related to it as well.


 

One of the central results in rough path theory is the local Lipschitz continuity of the solution map of a controlled differential equation called Ito-Lyons map. This continuity statement was obtained by T. Lyons in a q-variation resp. 1/q-Hölder type (rough path) metrics for any regularity 1/q>0. We extend this to a new class of Besov-Nikolskii type metrics with arbitrary regularity 1/q and integrability p, which particularly covers the aforementioned results as special cases. This talk is based on a joint work with Peter K. Friz.

 

In this talk, I will present two different aspects of the ice flow modelling, including a theoretical part and an applied part. In the theoretical part, I will derive some "mechanical error estimators'', i.e. estimators that can measure the mechanical error between the most accurate ice flow model (Glen-Stokes) and some approximations based on shallowness assumption. To do so, I will follow residual techniques used to obtain a posteriori estimators of the numerical error in finite element methods for non-linear elliptic problems. In the applied part, I will present some simulations of the ice flow generated by the Rhone Glacier, Switzerland, during the last glacial maximum (~ 22 000 years ago), analyse the trajectories taken by erratic boulders of different origins, and compare these results to geomorphological observations. In particular, I will show that erratic boulders, whose origin is known, constitute valuable data to infer information about paleo-climate, which is the most uncertain input of any paleo ice sheet model. 

The size Ramsey number r'(H) of a graph H is the smallest number of edges in a graph G which is Ramsey with respect to H, that is, such that any 2-colouring of the edges of G contains a monochromatic copy of H. A famous result of Beck states that the size Ramsey number of the path with n vertices is at most bn for some fixed constant b > 0. An extension of this result to graphs of maximum degree ∆ was recently given by Kohayakawa, Rödl, Schacht and Szemerédi, who showed that there is a constant b > 0 depending only on ∆ such that if H is a graph with n vertices and maximum degree ∆ then r'(H) < bn^{2 - 1/∆} (log n)^{1/∆}. On the other hand, the only known lower-bound on the size Ramsey numbers of bounded-degree graphs is of order n (log n)^c for some constant c > 0, due to Rödl and Szemerédi.

Together with David Conlon, we make a small step towards improving the upper bound. In particular, we show that if H is a ∆-bounded-degree triangle-free graph then r'(H) < s(∆) n^{2 - 1/(∆ - 1/2)} polylog n. In this talk we discuss why 1/∆ is the natural "barrier" in the exponent and how we go around it, why we need the triangle-free condition and what are the limits of our approach.

We discuss a new setting of algorithmic problems in random graphs, studying the minimum number of queries one needs to ask about the adjacency between pairs of vertices of $G(n,p)$ in order to typically find a subgraph possessing a certain structure. More specifically, given a monotone property of graphs $P$, we consider $G(n,p)$ where $p$ is above the threshold probability for $P$ and look for adaptive algorithms which query significantly less than all pairs of vertices in order to reveal that the property $P$ holds with high probability. In this talk we focus particularly on the properties of containing a Hamilton cycle and containing paths of linear size. The talk is based on joint work with Asaf Ferber, Michael Krivelevich and Benny Sudakov.

A graph is quasirandom if its edge distribution is similar (in a well defined quantitative way) to that of a random graph with the same edge density. Classical results of Thomason and Chung-Graham-Wilson show that a variety of graph properties are equivalent to quasirandomness. On the other hand, in some known proofs the error terms which measure quasirandomness can change quite dramatically when going from one property to another which might be problematic in some applications.

Simonovits and Sós proved that the property that all induced subgraphs have about the expected number of copies of a fixed graph $H$ is quasirandom. However, their proof relies on the regularity lemma and gives a very weak estimate. They asked to find a new proof for this result with a better estimate. The purpose of this talk is to accomplish this.

Joint work with D. Conlon and J. Fox

An edge (vertex) coloured graph is rainbow-connected if there is a rainbow path between any two vertices, i.e. a path all of whose edges (internal vertices) carry distinct colours. Rainbow edge (vertex) connectivity of a graph G is the smallest number of colours needed for a rainbow edge (vertex) colouring of G. We propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several new and known results, focusing on random regular graphs. This is joint work with Michael Krivelevich and Benny Sudakov.

We describe the cohomology of moduli spaces of points on schemes over Abelian varieties and give explicit calculations for schemes in dimensions less that three. The construction of Gulbrandsen allows one to consider virtual motives in dimension three. In particular we see a new proof of his conjectures on the Euler numbers of generalized Kummer schemes recently proven by Shen. Joint work in progress with Junliang Shen.