# Drafting Workshop in Discrete Mathematics and Probability

### Description

Several postdoc positions are available in Budapest in various research groups in discrete mathematics and probability theory. The research groups are listed below.

To make the application process more efficient and joyful, we are organizing a drafting workshop for young researchers interested in these positions, with the dates Jan 31 – Feb 3, 2022, at the Renyi Institute.

The participants of the workshop can present their work in a research talk, learn more about the research environment in Budapest, meet the heads and members of the research groups in person and in case of a perfect matching, get an offer on the spot.

The application due date is December 15th. The workshop is invitation based. We can cover the accommodation of successful applicants and there is limited funding for travel expenses. If you need travel funding, let us know in your application.

A CV containing a publication list should be sent as a part of the application. Recommendation letters are not required, but can be submitted as well. We may contact your PhD advisor asking for more information, so please add their email contacts to the application.

Applications should be sent to the e-mail address large.networks@renyi.hu. Please include 'Drafting workshop application' in the subject of the email. In case the applicant is still a PhD student, the e-mail should contain the expected termination date of their PhD studies.

**Groups and Graph Convergence Research Group**

Head: Miklós Abért, Alfréd Rényi Institute of Mathematics

E-mail address: abert.miklos@renyi.hu

The research group studies measured and asymptotic group theory, in particular spectral theory of graphs and groups, Benjamini-Schramm convergence, stochastic processes on groups, rank gradient, invariant random subgroups, homology growth, sofic entropy and asymptotic invariants of random graphs and locally symmetric spaces.

**MTA-ELTE Momentum Matroid Optimization Research Group**

Head: Kristóf Bérczi, Eötvös Loránd University

E-mail address: kristof.berczi@ttk.elte.hu

We aim to explore the global structure of bases in matroids, or more generally, of common bases in the intersection of matroids. Our goal is to devise structural and algorithmic results that will open up new domains for packing common bases algorithmically beyond the currently known special cases. Meanwhile, supported by the results obtained, we aim to resolve a wide list of fundamental open questions that all stem from the global relations of matroid bases.

**MTA-Rényi Momentum Counting in Sparse Graphs Research Group**

Head: Péter Csikvári, Alfréd Rényi Institute of Mathematics

E-mail address: peter.csikvari@gmail.com

We aim to study approximate counting problems of combinatorial objects of a given graph besides restricted information. This general framework includes counting matchings, independent sets, colorings given the degree sequence or local statistics or may be the whole graph as an input. There is an emphasis on developing random and deterministic algorithms.

**Local Algorithms on Sparse Random Graphs Research Group**

Head: Endre Csóka, Alfréd Rényi Institute of Mathematics

E-mail address: csoka.endre@renyi.hu

We examine the structures and phase transitions in large random graphs. For example, the structure of a largest independent set in a random \(d\)-regular graph on \(n → ∞\) vertices is in a "solid state" for \(d ≥ 20\) but probably in a "spin glass state" for \(d ≤ 19\) . We are using the tools of graph limit theory, local algorithms (IID-factor processes), and probability theory, and we are trying to translate and extend some intuitive arguments in statistical physics into this mathematical language.

**Analysis and Applications of Markov Chains Research Group**

Head: Balázs Gerencsér, Alfréd Rényi Institute of Mathematics

E-mail address: gerencser.balazs@renyi.hu

Our group is analyzing and exploring favorable perturbations of Markov chain transition probabilities towards nding the optimally mixing instance, also investigating minor changes in the transition topology (mostly discrete time chains). Similar research is carried out on a parallel track with an applied mind, in particular for consensus on networked systems, taking into account possibly asynchronous communication and similar challenges.

**Dynamics and Structure of Networks Research Group**

Head: László Lovász, Alfréd Rényi Institute of Mathematics

E-mail address: lovasz.laszlo@renyi.hu

A lot is known about the structure of large networks (graphs), but most real-life networks are interesting because they support interesting dynamics. Our research group is working on extending the structure theory of large networks to the case of graphs with medium density and to graphs supporting dynamics. Motivation comes from graph limit theory, epidemic propagation, and networks embedded in physical space.

**GeoScape: Combinatorial Geometry Research Group**

Head: János Pach, Alfréd Rényi Institute of Mathematics

E-mail address: pach@renyi.hu

A classic theme of combinatorics is to search for interesting patterns in various graphs and hypergraphs. Much of the research in Ramsey-theory, Turán-type extremal graph theory, Szemerédi regularity theory found important applications in combinatorial and computational geometry. However, if we blindly apply these theories in geometric scenarios, the obtained results are rarely optimal. We try to explain this curious phenomenon by proving stronger results on structures often arising in geometric applications: graphs and hypergraphs of bounded complexity, containing no "forbidden" subpattern of a fixed type, or embedded in a surface.

**MTA-BME Momentum Arithmetic Combinatorics Research Group**

Head: Péter Pál Pach, Budapest University of Technology and Economics

E-mail address: ppp@cs.bme.hu

Our aim is to introduce novel methods to solve problems of various types from Arithmetic Combinatorics. We particularly concentrate on developing techniques built on (linear) algebraic grounds like the slice rank method. A central question to be investigated is the following: What is the largest possible size of a k-AP-free subset of \(\mathbb{Z}_{p}^{n}\) ?

**Noise-Sensitivity Everywhere Research Group**

Head: Gábor Pete, Alfréd Rényi Institute of Mathematics and Budapest University of Technology and Economics

E-mail address: robagetep@gmail.com

Noise-sensitivity of a Boolean function with random input bits means that resampling a tiny proportion of the input makes the output decorrelate faster than the relaxation time of the entire system. For iid random input, discrete Fourier analysis yields a useful theory to understand what functions are noise-sensitive, with great applications, e.g., in percolation theory. What happens for non-iid input, such as the Ising model, Gaussian random fields, spanning forests, or factor of iid processes? A related goal is to study the (near-)critical behavior of statistical physics models on Cayley graphs of groups and on random graphs.

**Limits of Discrete Structures Research Group**

Head: Balázs Szegedy, Alfréd Rényi Institute of Mathematics

E-mail address: szegedyb@gmail.com

We study large networks using methods from analysis, probability theory and algebra. More generally we develop limit concepts for various discrete structures.

Other closely related research areas include higher order Fourier analysis, dynamical systems and even machine learning.