Tuesday 11.12.2018 at 10:00 ÚI, room 318: Joel Larsson (University of Warwick): The Mézard-Parisi conjecture
Abstract: Consider the complete bipartite graph on n+n vertices equipped with i.i.d. edge weights. The random assignment or minimum matching problem is to find a perfect matching that minimizes the total weight $M_n$ of included edges. |
Friday 23.11.2018 at 10:00 ÚI, room 318: Robert Hancock (MI, Czech Academy of Sciences): The Maker-Breaker Rado game on a random set of integers
Abstract: Given an integer-valued matrix A of dimension lxk and an integer-valued vector b of dimension l, the Maker-Breaker (A,b)-game on a set of integers X is the game where Maker and Breaker take turns claiming previously unclaimed integers from X, and Maker's aim is to obtain a solution to the system Ax=b, whereas Breaker's aim is to prevent this. When X is a random subset of {1,...,n} where each number is included with probability p independently of all others, we determine the threshold probability p_0 for when the game is Maker or Breaker's win, for a large class of matrices and vectors. This class includes but is not limited to all pairs (A,b) for which Ax=b corresponds to a single linear equation. The Maker's win statement also extends to a much wider class of matrices which include those which satisfy Rado's partition theorem. |
Friday 16.11.2018 at 10:00 ÚI, room 318: Jan Volec (Emory and Universität Hamburg): Transversal and colorful versions of Mantel's theorem
Abstract:
A classical result of Mantel states that every graph of density larger than 1/2
contains a triangle, and this result is best possible. In this talk, we study
two Mantel-inspired problems: The first one asks what is the minimum d such
that any triple of graphs G1,G2,G3 on the same vertex-set all of density
larger than d contains a transversal triangle, i.e., there exist three edges
uv,vw,wu in G1,G2,G3, respectively. We show that d = (52 - 4*Sqrt[7]) / 81,
which is asymptotically best possible witnessed by a construction discovered by
Aharoni and DeVos. Moreover, their construction is asymptotically the only
extremal configuration. The second problem, which is due to DeVos, McDonald and
Montejano, states that every k-edge-colored graph where each color class has
density more than 1/(2k-1) contains a non-monochromatic triangle. |
Friday 9.11.2018 at 10:00 ÚI, room 318: Stefan Glock (University of Birmingham): Resolution of the Oberwolfach problem
Abstract: The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of the complete graph of odd order n into edge-disjoint copies of a given cycle factor. We show that this can be achieved for all large n. We actually prove a more general result, which allows for decompositions into more general types of factors. In particular, this also resolves the Hamilton--Waterloo problem for large n. This is joint work with Felix Joos, Jaehoon Kim, Daniela Kühn and Deryk Osthus. |
Friday 26.10.2018 at 10:00 ÚI, room 318: Matas Šileikis (ICS, Czech Academy of Sciences): Small subgraph counts in the binomial random graph: a survey
Abstract: Given a (fixed) graph H, let X be the number of copies of H in the random binomial graph G(n,p). In this talk we recall the results on the asymptotic behaviour of X, as the number n of vertices grows and p is allowed to depend on n. In particular we will focus on the problem of estimating probability that X is significantly larger than its expectation, which earned the name of 'the infamous upper tail'. (Includes joint work with L. Warnke.) |
Monday 24.9.2018 at 10:00 MI, room "modrá posluchárna": Maryam Sharifzadeh (Warwick University): Number of maximal sum-free subsets of integers and abelian groups
Abstract: A set S is sum-free if it does not contain a triple x,y,z such that x+y=z (note x,y may not necessarily be distinct). We say that S⊆ [n] is a maximal sum-free subset of [n] if it is sum-free and it is not properly contained in another sum-free subset of [n]. Cameron and Erdős asked whether the number of maximal sum-free subsets of [n] is much smaller than the number of sum-free sets. They also gave a lower bound of 2⌊ n/4 ⌋ for the number of maximal sum-free sets. Together with József Balogh, Hong Liu, and Andrew Treglown, we give an exact solution to the problem: For each 1≤ i ≤ 4, there is a constant C_i such that, given any n≡ i mod 4, [n] contains (C_i+o(1)) 2n/4. maximal sum-free sets. In this talk, I will outline the ideas and techniques used in the proof. I will also discuss some new results on the number of maximal sum-free sets in abelian groups, which are joint work with Hong Liu. |
Wednesday 8.8.2018 at 10:00 ÚI, room 318: Casey Tompkins (Hungarian Academy of Sciences): Generalizations of the Erdős-Gallai theorem
Abstract: In this talk we will consider a variety of extensions of the classical theorems of Erdős and Gallai about graphs without long paths or cycles. I will discuss recent hypergraph analogues for so-called Berge paths and cycles, generalized Turán problems where we try to maximize various subgraph counts in P_k-free graphs, and if time permits a colored analogue. The results presented will be joint work with different groups from the following: Beka Ergemlidze, Ervin Győri, Abhishek Methuku, Nika Salia, Oscar Zamora. |
Friday 22.6.2018 at 14:00 ÚI, room 318: Diana Piguet (ICS, Czech Academy of Sciences): Packing degenerate graphs
Abstract: We say that a family (H_1,H_2,..H_k) of graphs packs into a graph G, when there are pairwise edges disjoint copies of H_i in G.
Motivated by the famous tree-packing conjecture and Ringel conjecture,
we consider packing spanning D-degenerate graphs with unbounded (but still sublinear) maximal degree into the complete graph. Our proof proceeds by analysing a natural random greedy packing algorithm. |
FRIDAY 1.6.2018 at 10:00 ÚI, room 318: Israel Rocha (ICS, Czech Academy of Sciences): 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. |
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. |
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. |