The Yandex workshop on extremal graph theory is part of the 9th International Computer Science Symposium and aims at brining together specialists who work in extremal combinatorics, probabilistic methods in discrete mathematics, random graphs, hypergraphs and related fields.

Speakers in this workshop, which is organised by Andrey Raigorodsky, include David Gamarnik (MIT), Joel Spencer (Courant Institute, New York University), Endre Szemerédi (Rutgers University) and others.

This workshop will take place in Yandex’s Moscow office on **June 6, 2014**.

The talks will start at **10:00 am** with on-site registration open from **9:30 am**.

To be eligible for on-site registration, participants fist need to register online.

The language of this workshop is English.

### Talks

09:30 | Registration |

10:00 | Finding Needles in Exponential Haystacks | Joel Spencer New York University's Courant Institute of Mathematical Sciences | Watch |

## Workshop on Extremal Graph Theory## Finding Needles in Exponential Haystacks6 June, 10:00Lva Tolstogo 16, Moscow 119021 We discuss two recent methods in which an object with a certain property is sought. In both, using of a straightforward random object would succeed with only exponentially small probability. The new randomized algorithms run efficiently and also give new proofs of the existence of the desired object. In both cases there is a potentially broad use of the methodology. (i) Consider an instance of (ii) No Outliers. Given |

11:00 | Zero-one k-laws for G(n,n^{−α}) | Maksim Zhukovskii Yandex | Watch |

## Workshop on Extremal Graph Theory## Zero-one k-laws for G(n,n |

11:30 | Improved algorithms for colorings of simple hypergraphs and applications | Dmitry Shabanov Lomonosov Moscow State University | Watch |

## Workshop on Extremal Graph Theory## Improved algorithms for colorings of simple hypergraphs and applications6 June, 11:30Lva Tolstogo 16, Moscow 119021 The famous Lovász Local Lemma was derived in the paper of P. Erdős and Lovász to prove that any
A long series of papers is devoted to the improvement of this classical result for different classesof uniform hypergraphs. In our work we deal with colorings of simple hypergraphs, i.e. hypergraphs in which everytwo distinct edges do not share more than one vertex. By using a multipass random recoloringwe show that any simple
where The work of the second author was supported by Russian Foundation of Fundamental Research (grant № 12-01-00683-a), by the program “Leading Scientific Schools” (grant no. NSh-2964.2014.1) and by the grant of the President of Russian Federation MK-692.2014.1 |

12:00 | Coffee Break |

12:30 | Proof of the Pósa−Seymour Conjecture | Endre Szemerédi Rutgers University | Watch |

## Workshop on Extremal Graph Theory## Proof of the Pósa−Seymour Conjecture6 June, 12:30Lva Tolstogo 16, Moscow 119021 In 1974 Paul Seymour conjectured that any graph Joint work with Asif Jamshed. |

13:30 | Zero-one k-laws and extended zero-one k-laws for random distance graphs | Svetlana Popova Lomonosov Moscow State University | Watch |

## Workshop on Extremal Graph Theory## Zero-one k-laws and extended zero-one k-laws for random distance graphs6 June, 13:30Lva Tolstogo 16, Moscow 119021 Studying zero-one laws for random graphs was initiated by Glebskii Y. et al. in [1]. In this work the authors proved the zero-one law for Erdős-Rényi random graph Let {G
We say sequence We obtain conditions on the sequence {G -
zero-one *k*-law holds; -
zero-one *k*-law doesn't hold, but extended zero-one k-law holds; -
extended zero-one *k*-law doesn't hold.
[1] Y.V. Glebskii, D.I. Kogan, M.I. Liagonkii, V.A. Talanov, [2] S. Shelah, J.H. Spencer, [3] M.E. Zhukovskii, [4] S.N. Popova, |

14:00 | Subsets of Z/pZ with small Wiener norm and arithmetic progressions | Ilya Shkredov Lomonosov Moscow State University | Watch |

## Workshop on Extremal Graph Theory## Subsets of Z/pZ with small Wiener norm and arithmetic progressions6 June, 14:00Lva Tolstogo 16, Moscow 119021 It is proved that any subset of Z/pZ, p is a prime number, having small Wiener norm (l_1-norm of its Fourier transform) contains a subset which is close to be an arithmetic progression. We apply the obtained results to get some progress in so-called Littlewood conjecture in Z/pZ as well as in a quantitative version of Beurling-Helson theorem. |

14:30 | Lunch |

16:00 | Limits of Local Algorithms for Randomly Generated Constraint Satisfaction Problems | Watch | |

## Workshop on Extremal Graph Theory## Limits of Local Algorithms for Randomly Generated Constraint Satisfaction Problems6 June, 16:00Lva Tolstogo 16, Moscow 119021 A major challenge in the field of random graphs is constructing fast algorithms for solving a variety of combinatorial optimization problems, such as finding largest independent set of a graph or finding a satisfying assignment in random instances of K-SAT problem. Most of the algorithms that have been successfully analyzed in the past are so-called local algorithms which rely on making decisions based on local information. In this talk we will discuss fundamental barrier on the power of local algorithms to solve such problems, despite the conjectures put forward in the past. In particular, we refute a conjecture regarding the power of local algorithms to find nearly largest independent sets in random regular graphs. Similarly, we show that a broad class of local algorithms, including the so-called Belief Propagation and Survey Propagation algorithms, cannot find satisfying assignments in random NAE-K-SAT problem above a certain asymptotic threshold, below which even simple algorithms succeed with high probability. Our negative results exploit fascinating geometry of feasible solutions of random constraint satisfaction problems, which was first predicted by physicists heuristically and now confirmed by rigorous methods. According to this picture, the solution space exhibits a clustering property whereby the feasible solutions tend to cluster according to the underlying Hamming distance. We show that success of local algorithms would imply violation of such a clustering property thus leading to a contradiction. Joint work with Madhu Sudan (Microsoft Research). |

17:00 | Local clustering coefficient in preferential attachment graphs | Alexander Krot Moscow Institute of Physics and Technology Egor Samosvat Yandex | Watch |

## Workshop on Extremal Graph Theory## Local clustering coefficient in preferential attachment graphs6 June, 17:00Lva Tolstogo 16, Moscow 119021 Alexander Krot Moscow Institute of Physics and Technology Liudmila Ostroumova-Prokhorenkova Yandex Egor Samosvat Yandex In this talk we discuss some properties of generalized preferential attachment models. A general approach to preferential attachment was introduced in [1], where a wide class of models (PA-class) was defined in terms of constraints that are sufficient for the study of the degree distribution and the clustering coefficient. It was shown in [1] that the degree distribution in all models of the PA-class follows the power law. Also, the global clustering coefficient was analyzed and a lower bound for the average local clustering coefficient was obtained. It was also shown that in preferential attachment models global and average local clustering coefficients behave differently. In our study we expand the results of [1] by analyzing the local clustering coefficient for the PA-class of models. We analyze the behavior of C(d) which is the average local clustering for vertices of degree d. The value C(d) is defined in the following way. First, the local clustering of a given vertex is defined as the ratio of the number of edges between the neighbors of this vertex to the number of pairs of such neighbors. Then the obtained values are averaged over all vertices of degree d. [1] L. Ostroumova, A. Ryabchenko, E. Samosvat, Generalized Preferential Attachment: Tunable Power-Law Degree Distribution and Clustering Coefficient, Algorithms and Models for the Web Graph, Lecture Notes in Computer Science Volume 8305, 2013, pp 185-202. |

17:30 | Asymptotic behaviour of ranking algorithms in directed random networks | Nelly Litvak University of Twente | Watch |

## Workshop on Extremal Graph Theory## Asymptotic behaviour of ranking algorithms in directed random networks6 June, 17:30Lva Tolstogo 16, Moscow 119021 There is a vast empirical research on the behaviour of ranking algorithms, e.g. Google PageRank, in scale-free networks. In this talk, we address this problem by analytical probabilistic methods. In particular, it is well-known that the PageRank in scale-free networks follows a power law with the same exponent as in-degree. Recent probabilistic analysis has provided an explanation for this phenomenon by obtaining a natural approximation for PageRank based on stochastic fixed-point equations. For these equations, explicit solutions can be constructed on weighted branching trees, and their tail behavior can be described in great detail. In this talk we present a model for generating directed random graphs with prescribed degree distributions where we can prove that the PageRank of a randomly chosen node does indeed converge to the solution of the corresponding fixed-point equation as the number of nodes in the graph grows to infinity. The proof of this result is based on classical random graph coupling techniques combined with the now extensive literature on the behavior of branching recursions on trees. |

18:00 | Boundary properties of factorial classes of graphs | Victor Zamaraev National research university "Higher school of economics". | Watch |

## Workshop on Extremal Graph Theory## Boundary properties of factorial classes of graphs6 June, 18:00Lva Tolstogo 16, Moscow 119021 For a class of graphs X, let X_n be the number of graphs with vertex set {1,...,n} in the class X, also known as the speed of X. It is known that in the family of hereditary classes (i.e. those that are closed under taking induced subgraphs) the speeds constitute discrete layers and the first four lower layers are constant, polynomial, exponential, and factorial. For each of these four layers a complete list of minimal classes is available, and this information allows to provide a global structural characterization for the first three of them. The minimal layer for which no such characterization is known is the factorial one. A possible approach to obtaining such a characterization could be through identifying all minimal superfactorial classes. However, no such class is known and possibly no such class exists. To overcome this difficulty, we employ the notion of boundary classes that has been recently introduced to study algorithmic graph problems and reveal the first few boundary classes for the factorial layer. Joint work with Vadim Lozin. |