Workshop on Random Graphs, Combinatorial Limits, Stochastic Processes
The purpose of this workshop was to bring together experts and young scientists who form WORKING GROUPS to SOLVE DIFFERENT PROBLEMS about RANDOM GRAPHS and RELATED MATHEMATICAL TOPICS IN A VERY BROAD SENSE.
The random graph is a fundamental object related to different fields.For example, graph limit theory is about understanding the large-scale structure of a graph, or in other words, understanding how a graph is different from a random graph. Statistical physics uses random graphs to model different physical matters and phase transitions on them. Group theory uses the fact that the Cayley-graph of a free group is locally equivalent to a random regular graph. There are other random structures such as random permutations which have analogous theory. In this broad area, it particularly often happens that a question is motivated by one field, but the best tools for solving it come from another field.
The 26 participants arrived from 7 countries and many different fields of expertise. On day one, 13 open problems were suggested by them, and the background of these problems were explained in short presentations. Then we selected three of the open problems, and formed research groups to work on the questions separately.
The event was very successful, largely due to the format of the workshop. The third problem was essentially solved, and strong partial results were achieved in the second one. At the end of the first week, all three groups gathered to present a short report on their progress. Here, ideas were exchanged, which resulted in a new perspective on the third problem, leading to a breakthrough in the proof.
On the free day, we took a refreshing trip to lake Balaton.
Endre Csóka (Rényi Institute): Hoppen-Wormald type algorithms on graph limits
Łukasz Grabowski (University of Leipzig): Hypershallow digraphs
Jan Grebik (Univ.of Warwick): Local problems from the perspective of random processes and distributed algorithms
Eng Keat Hng (The Czech Academy of Sciences): Graph flip processes
Brice Huang (MIT): Max-cut in sparse graphs
Mark Kaufmann (ETH Zurich): Geometric constructions to large networks
Gábor Kun (Rényi Institute): Perfect matchings in graphings
Noela Müller (Eindhoven University of Technology): Partition function of random k-SAT problems
Zoltán Lóránt Nagy (Eötvös Loránd University): Bisection width, internal partitions, and r-degenerate graphs
Gábor Pete (Rényi Institute): Disconnected components of critical Erdős-Rényi random graphs