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
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. |
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. |
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. |
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. |
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. |