Extremal graph theory group


FRIDAY 1.6.2018 at 10:00 ÚI, room 318: Israel Rocha : Using eigenvectors to recover the layout of random circulant graphs

Abstract:A circulant graph H is a graph on n vertices that can be numbered from 0 to n-1 in such a way that, if two vertices x and ( x+d ) mod n are adjacent, then every two vertices z and ( z+d ) mod n are adjacent. The labelling in the definition is what we call the layout. Now a random circulant graph results from deleting edges of H with probability 1-p.
The general question we intend to address is how to recover the layout of a random circulant graph. In this talk I will explain how it can be done by means of eigenvectors and present a polynomial time algorithm that approximates the solution with high probability. This is a joint work with Sebastian Richter.

FRIDAY 15.6.2018 at 10:00 ÚI, room 318: Diana Piguet : Packing degenerate graphs

Past seminars

FRIDAY 25.5.2018 at 10:00 ÚI, room 318: Tomas Juškevičius (Vilnius University): Littlewood-Offord type inequalities in groups

Abstract: Given n positive numbers a_1, ..., a_n in R consider all 2^n possible sums of them with signs + and -. How many of them can be equal? This is a variant of the so-called Littlewood-Offord problem, which was solved by Erdős in 1945 using Sperner's inequality. Since then the problem was considered in a more general setting when the numbers a_i are replaced by non-zero vectors in a R^k, the research culminating in a theorem by Kleitman (1970) for vectors a_i in arbitrary normed spaces. We consider a natural extension of the problem to the setting when a_i's are elements of a group: how many elements of the form g_1 * ... * g_n, where g_i is either a_i or a_i^{-1}, can coincide? Strengthening and generalizing some very recent results by Tiep and Vu, we establish several optimal inequalities, which, among other things, imply that the Erdős' bound for real numbers is still best possible for any torsion-free group. (Joint work with G. Šemetulskis)

FRIDAY 18.5.2018 at 10:00 ÚI, room 318: Vaclav Rozhon (Czech Academy of Sciences & Charles University): Embedding trees in dense graphs

Abstract: A famous conjecture of Erdős and Sós from 1963 states that every graph with average degree greater than k-1 contains any tree on k+1 vertices. A proof of the conjecture for large values of k by Ajtai, Komlós, Simonovits, and Szemerédi was announced in the early 1990's. A similar conjecture is the Loebl-Komlós-Sós conjecture stating that every graph such that at least half of its vertices have degree at least k contains any tree on k+1 vertices. Hladký, Komlós, Piguet, Simonovits, Stein, and Szemerédi proved the conjecture is asymptotically correct for large values of k.
We investigate some variations of these problems. Specifically, we partially answer a question of Simonovits by proving that a certain strengthening of the Loebl-Komlós-Sós conjecture is asymptotically correct for dense graphs. This is joint work with T. Klimošová and D. Piguet. Another result implies that the Erdős-Sós conjecture is asymptotically correct for dense graphs and trees with sublinear maximum degree. Both results are based on the celebrated Szemerédi's regularity lemma.

FRIDAY 27.4.2018 at 10:00 ÚI, room 318: Frederik Garbe (Czech Academy of Sciences, MI): Contagious sets in degree-proportional bootstrap percolation

Abstract: We study the following bootstrap percolation process: given a connected graph G, we infect an initial set A of vertices, and in each step a vertex v becomes infected if at least a ρ-proportion of its neighbours are infected. Once infected, a vertex remains infected forever. A set A which infects the whole graph is called a contagious set. It is natural to ask for the minimal size of a contagious set.
Our main result states that for every ρ between 0 and 1, every connected graph G on n vertices has a contagious set of size less than 2ρn or a contagious set of size 1 (note that allowing the latter possibility is necessary since every contagious set has size at least one). This result is best-possible and improves previous results of Chang, Chang and Lyuu, and Gentner and Rautenbach. We also provide a stronger bound in the case of graphs of girth at least five. Both proofs exploit the structure of a minimal counterexample in a randomised fashion.
This is joint work with Andrew McDowell and Richard Mycroft.

FRIDAY 16.3.2018 at 10:00 ÚI, room 318: Jakub Sosnovec (Charles University) Finitely forcible graphons with an almost arbitrary structure

Abstract: The theory of combinatorial limits offers analytic tools to study large combinatorial objects. In this theory, an analytic object representing large dense graphs is called a graphon. A graphon is finitely forcible if its structure is determined by finitely many subgraph densities, i.e., the asymptotic structure of graphs represented by such a graphon depends only on finitely many density constraints. Finitely forcible graphons appear in various scenarios, particularly in extremal combinatorics.
Lovász and Szegedy conjectured that all finitely forcible graphons possess a simple structure. This was disproved in a strong sense by Cooper, Král' and Martins, who showed that any graphon is a subgraphon of a finitely forcible graphon. We strenghten this result by showing for every ε > 0 that any graphon spans a 1 - ε proportion of a finitely forcible graphon.
Joint work with Daniel Král', László M. Lovász and Jonathan A. Noel.

MONDAY 22.1.2018 at 10:00 ÚI, room 318: Viresh Patel (University of Amsterdam) Decomposing tournaments into paths

Abstract: In this talk we consider a generalisation of Kelly's conjecture which is due Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by K{\"u}hn and Osthus for all sufficiently large tournaments. The conjecture of Alspach, Mason, and Pullman concerns general tournaments and asks for the minimum number of paths needed in an edge decomposition of each tournament into paths. There is a natural lower bound for this number in terms of the degree sequence of the tournament and they conjecture this bound is correct for tournaments of even order.
Almost all cases of the conjecture are open and we prove many of them.
This is joint work with Allan Lo, Jozef Skokan, and John Talbot.

FRIDAY 5.1.2018 at 10:00 ÚI, room 318: Jan Volec (McGill) On degree thresholds of cycles in oriented graphs

Abstract: Motivated by Caccetta-Haggkvist conjecture, Kelly, Kuhn and Osthus initiated the study of minimum out-degree and semi-degree conditions that force an oriented graph to contain an oriented cycle of a given length. In particular, they proved for every l>=4 that if G is a sufficiently large n-vertex oriented graph with semi-degree > n/3, then G contains an oriented cycle of length l. It is easy to show that the bound is sharp for every l not divisible by 3. However, they conjectured that for l>=4 which is a multiple of 3, one can always do better. The smallest open case, which has drawn quite some attention and was a few times mentioned in open problem sessions by Kuhn and Osthus, is the one when l=6, i.e., the case of 6-cycles.
In this talk, we will mainly focus on the 6-cycle threshold and prove that if G is a sufficiently large n-vertex oriented graph with semi-degrees > n/4+1, then it contains an oriented 6-cycle. Since the natural lower-bound n/4 coming from a blow-up of oriented 4-cycle could be improved by one when n=4k+3, our lower-bound is best possible. We also determine the semi-degree thresholds for closed walks of length l for every l>=9 which is a multiple of 3, which provides an asymptotic solution to the conjecture of Kelly, Kuhn and Osthus.
This is a joint work with Roman Glebov and Andrzej Grzesik

seminars in 2017

seminars in 2016