Spectral Theory of Graph Limits

Marie Skłodowska-Curie Actions
Individual Fellowship grant no. 661025

Viktor Harangi
Rényi Institute of Mathematics
Budapest, Hungary




with Á. Backhausz, B. Gerencsér, M. Vizer:
Correlation bound for distant parts of factor of IID processes
Combinatorics, Probability and Computing, to appear. pdf

with B. Gerencsér:
Mutual information decay for factors of IID
Ergodic Theory and Dynamical Systems, to appear. pdf

with Á. Backhausz, B. Gerencsér:
Entropy inequalities for factors of IID
submitted. pdf

Factors of IID on hypergraphs and entropy inequalities
in preparation.

Seminar talks

Invariant processes on infinite trees slides
Louvain-la-Neuve, Belgium
Abstract: In this talk we will demonstrate how studying certain invariant processes on infinite trees can help to answer questions about (large) finite graphs/networks (such as questions about the maximal size of an independent set or about the eigenvectors of the adjacency matrix). Our main focus will be the class of factor of IID processes (which are essentially factors of Bernoulli shifts from an ergodic theoretic point of view). We will also mention some entropy inequalities that played a central role in a couple of remarkable results recently.

Entropy inequalities for factors of IID
University of Toronto, Canada
Abstract: This talk is concerned with certain invariant processes over infinite trees. Tha main focus will be on the class of factor of IID processes which have received a growing attention recently due to their connection to certain randomized local algorithms and random regular graphs. Entropy inequalities for these processes played a central role in a couple of remarkable results in the past few years. I will talk about how one can find and prove new entropy inequalities.

Correlation bounds and one-ended tail triviality for factors of IID on trees slides
Stochastics Seminar, Budapest University of Technology and Economics
Abstract: We study factor of IID processes on the d-regular tree. We show that if such a process is restricted to two distant connected subgraphs of the tree, then the two parts are basically uncorrelated. More precisely, we give an explicit bound for the correlation of any measurable functions of the two parts, the bound only depending on d and the distance of the subgraphs. This result can be considered as a quantitative version of the fact that factor of IID processes have trivial 1-ended tails.

On the eigenvectors of random regular graphs
Graph Limits Seminar, Rényi Institute
Abstract: There is much known about the spectrum of a random regular graph. When it comes to its eigenvectors, however, even (not too strong) delocalization results are hard to come by. In this talk we will survey what has been proved in the literature, and also mention some ambitious conjectures and potential approaches.

The resolvent operator and the Stieltjes transform
Graph Limits Seminar, Rényi Institute
Abstract: Given a compactly supported measure on the real line (such as the spectral measure of a bounded degree graph), its Stieltjes transform is an analytic function on the complex upper half-plane. This function can also be obtained directly from the adjacency operator of the graph via the so-called resolvent operator. Stieltjes transforms proved to be a useful tool to study the spectral properties of (random) matrices/operators. In this talk we give a brief introduction to the subject.

Talks at student seminars

Randomizált lokális algoritmusok nagy gráfokon slides  (partial)
Eötvös University Bolyai Kollégium
Abstract (in Hungarian): Olyan párhuzamosítható algoritmusokat tekintünk gráfokon, melyeknél minden csúcs csupán egy fix sugarú környezetét "látja" és kizárólag ez alapján dönti el, hogyan "jár el". Olyan gráfoknál, ahol ezek a környezetek nagyrészt ugyanúgy néznek ki, "megtörhetjük a szimmetriát" azáltal, hogy első lépésként a csúcsokhoz színeket/címkéket rendelünk véletlenszerűen, és a randomizált lokális algoritmus már ezeket a címkéket is használhatja. Sok esetben hasznosnak bizonyul, ha az algoritmust a "limesz gráfon" vizsgáljuk.

Pac-Man-ek esete a hópehely görbével slides  (Hungarian)
Eötvös University Bolyai Kollégium
Abstract (in Hungarian): A Koch-féle hópehely görbe az egyik legismertebb önhasonló halmaz. Az előadáson azt a meglepő tényt látjuk be, hogy ez a fraktál lefedhető tetszőlegesen kis össz-szélességű sávokkal. A bizonyításhoz Pac-Man-eket fogunk segítségül hívni.

English version: the following similar talk was given a few months earlier.
Tube-null sets slides   video
Central European University
Abstract: A set in the plane is called 'tube-null' if it can be covered by strips of arbitrarily small total width. (A strip is the region between two parallel lines.) Any such set can appear as the set of divergence for the localization problem. It turns out that there are not many methods for proving that a given set is not tube-null, and even for very concrete sets, like the snowflake curve, it can be hard to decide whether they are tube-null or not.

Workshop organization

Mini workshop on entropy inequalities for factors of IID, August 22-26, 2016, Siófok

Description. Entropy inequalities proved to be a key tool in a couple of remarkable results recently: the Rahman-Virág result about the maximal size of a factor of IID independent set on the regular tree and the Backhausz-Szegedy result on eigenvectors of random regular graphs. The main focus of this mini workshop will be to investigate these inequalities, look for further applications, and try to obtain new inequalities as well.

Another goal of the workshop is to study a series of papers by Lewis Bowen in which he introduced the f-invariant for free group actions and the sofic-entropy for actions of sofic groups. Bowen also showed that the f-invariant is essentially a special case of the the sofic-entropy which has the consequence that the f-invariant is non-negative for factors of the Bernoulli shift. This fact is particularly relevant for us since it is equivalent to (a somewhat more general version of) the edge-vertex entropy inequality for factors over the free group.

Conference participation

  • Groups, Graphs and Stochastic Processes, June 21-26, 2015, BIRS, Banff, Canada. link
  • Spectrum of Random Graphs, January 4-8, 2016, CIRM, Luminy, France. link

Upcoming events:

  • 2017 Colloquia in Combinatorics, Queen Mary and London School of Economics. link
  • "Graph limits, groups and stochastic processes" Summer School, Rényi Institute. link

Public engagement

  • Talk at a public event organized and hosted by the Hungarian Academy of Sciences. I was invited to talk about the research I had done during the period of this fellowship and about my experience with applying for and participating in a Marie Skłodowska-Curie grant. The purpose of the event was multifold. On the one hand, it showcased the various research carried out in Hungary under MSCA and ERC grants. Its main purpose was to popularize these grants among Hungarian researchers and to provide advice and guidance on how to prepare a successful proposal. link video (in Hungarian)
  • Interview with Erinto (an online mathematics portal published by the János Bolyai Mathematical Society)

Other activities

  • Editorial work at one of the top combinatorial journals:
    Managing Editor of Combinatorica (2015 August - present).