We prove that if T1,…, Tn is a sequence of bounded degree trees so that Ti has i vertices, then Kn has a decomposition into T1,…, Tn. This shows that the tree packing conjecture of Gyárfás and Lehel from 1976 holds for all bounded degree trees.
We deduce this result from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs.
In this talk, we discuss the ideas used in the proof.
This is joint work with Felix Joos, Daniela Kühn and Deryk Osthus.

We consider the dynamical system of Sinai billiards with a single cusp where two walls meet at the vertex of a cusp and have zero one-sided curvature, thus forming a flat point at the vertex. For Holder continuous observables, we show that properly normalized Birkhoff sums, with respect to the billiard map, converge in law to a totally skewed alpha-stable law.

It has long been known that Feedback Vertex Set can be solved in time 2^O(w log w) n^O(1) on graphs of treewidth w, but it was only recently that this running time was improved to 2^O(w) n^O(1), that is, to single-exponential parameterized by treewidth. We consider a natural generalization of this problem, which asks given a graph G on n vertices and positive integers k and d, whether there is a set S of at most k vertices of G such that each block of G-S has at most d vertices. The central question of this talk is: “Can we obtain an algorithm that runs in single-exponential time parameterized by treewidth, for every fixed d?” The answer is negative. But then, one may be curious which properties of Feedback Vertex Set that make it allow to have a single-exponential algorithm. To answer this question, we add an additional condition in the general problem, and provide a dichotomy result.
Formally, for a class

A homomorphism is an adjacency preserving map between the vertex sets of two graphs. A n-vertex, k-regular graph is strongly regular, with parameters (n,k,λ, μ), if there exist numbers λ and μ such that every pair of adjacent vertices share λ common neighbors and every pair of non-adjacent vertices share μ common neighbors. A strongly regular graph is primitive if neither it nor its complement is a disjoint union of complete graphs. We prove that if G and H are primitive strongly regular graphs with the same parameters and φ is a homomorphism from G to H, then φ is either an isomorphism or a coloring (homomorphism to a complete subgraph). Moreover, any such coloring is optimal for G and its image is a maximum clique of H. Therefore, the only endomorphisms of a primitive strongly regular graph are automorphisms or colorings. This confirms and strengthens a conjecture of Peter Cameron and Priscila Kazanidis that all strongly regular graphs are cores or have complete cores. The proof of the result is elementary, mainly relying on linear algebraic techniques.

In classical combinatorics, sequences of positive integers are usually studied through their generating series. These formal power series can be used to classify the sequences, to obtain closed formulas for the number of object of a given size, …
Seeing the generating series as analytic functions, we can use tools of complex analysis (such as the residue theorem) to obtain, typically, an asymptotic equivalent to the sequence under consideration.
In this talk I will give a quick overview of the main results obtained in this field, from the automatic construction of generating series to some theorems coming from the theory of functions of a complex variable.
The talk will not assume any specific knowledge in combinatorics or complex analysis.

The purpose of this talk is to study the finite field analog of the Erdős distance problem. First, the conjecture and known results on the problem are reviewed. Second, we introduce basic skills to deduce results on the problem. Finally, we address how to improve currently known results on the Erdős distance problem.

For a tournament T, the chromatic number of T is the minimum number of transitive sets with union V(T). We say a set H of tournaments is heroic if there exists c such that every tournament excluding all members of H has chromatic number at most c. Berger et al. explicitly characterized all heroic sets of size one. In this talk, we study heroic sets of size two. This is a joint work with Maria Chudnovsky, Ilhee Kim, and Paul Seymour.

A set F of graphs has the Erdős-Posa property if there exists a function f such that every graph either contains k disjoint subgraphs each isomorphic to a member in F or contains a set of at most f(k) vertices intersecting all such subgraphs. In this talk I will address the Erdős-Posa property with respect to three closely related graph containment relations: minor, topological minor, and immersion. We denote the set of graphs containing H as a minor, topological minor and immersion by M(H),T(H) and I(H), respectively. Robertson and Seymour in 1980’s proved that M(H) has the Erdős-Posa property if and only if H is planar. And they left the question for characterizing H in which T(H) has the Erdős-Posa property in the same paper. This characterization is expected to be complicated as T(H) has no Erdős-Posa property even for some tree H. In this talk, I will present joint work with Postle and Wollan for providing such a characterization. For immersions, it is more reasonable to consider an edge-variant of the Erdős-Posa property: packing edge-disjoint subgraphs and covering them by edges. I(H) has no this edge-variant of the Erdős-Posa property even for some tree H. However, I will prove that I(H) has the edge-variant of the Erdős-Posa property for every graph H if the host graphs are restricted to be 4-edge-connected. The 4-edge-connectivity cannot be replaced by the 3-edge-connectivity.

Recently, Marcus, Spielman, and Srivastava proved the existence of infinite families of bipartite Ramanujan graphs of every degree at least 3 by using the method of interlacing families of polynomials. In this talk, we apply their method to prove that for any connected graph G, there exists an orientation of G such that the spectral radius of the corresponding Hermitian adjacency matrix is at most that of the universal cover of G.

Very recently, Andrew Suk made a major breakthrough on the Erdos-Szekeres convex polygon problem, in which he solves asymptotically this 80 year old problem of determining the minimum number of points in the plane in general position that always guarantees n points in convex position. I will review his proof in full detail.

A new algorithm will be presented for the path tsp, with an improved analysis and ratio. After the starting idea of deleting some edges of Christofides’ trees, we do parity correction and eventual reconnection, taking the salesman to travel through a linear program determining the conditional probabilities for some of his choices; through matroid partition of a set of different matroids for a better choice of his initial spanning trees; and through some other adventures and misadventures.
The proofs proceed by global and intuitively justified steps, where the trees do not hide the forests.

One more pleasant piece of news is that we get closer to the conjectured approximation ratio of 3/2, and a hopefully last misadventure before finishing up this problem is that we still have to add 1/34 to this ratio, and also for the integrality gap. (The previous result was 8/5 with slight improvements.)

Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to and evolved from algorithms for this problem. Unfortunately, this collection of powerful algorithmic techniques had not yet been applicable to the more general capacitated facility location problem. In fact, all of the known algorithms with good performance guarantees were based on a single technique, local search, and no linear programming relaxation was known to efficiently approximate the problem.

In this paper, we present a linear programming relaxation with constant integrality gap for capacitated facility location. We demonstrate that the fundamental theories of multi-commodity flows and matchings provide key insights that lead to the strong relaxation. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding.

A graph is (d1, …, dr)-colorable if its vertex set can be partitioned into r sets V1, …, Vr where the maximum degree of the graph induced by Vi is at most di for each i in {1, …, r}.

Given r and d1, …, dr, determining if a (sparse) graph is (d1, …, dr)-colorable has attracted much interest.
For example, the Four Color Theorem states that all planar graphs are 4-colorable, and therefore (0, 0, 0, 0)-colorable.
The question is also well studied for partitioning planar graphs into three parts.
For two parts, it is known that for given d1 and d2, there exists a planar graph that is not (d1, d2)-colorable.
Therefore, it is natural to study the question for planar graphs with girth conditions.
Namely, given g and d1, determine the minimum d2=d2(g, d1) such that planar graphs with girth g are (d1, d2)-colorable. We continue the study and ask the same question for graphs that are embeddable on a fixed surface.
Given integers k, γ, g we completely characterize the smallest k-tuple (d1, …, dk) in lexicographical order such that each graph of girth at least g that is embeddable on a surface of Euler genus γ is (d1, …, dk)-colorable.
All of our results are tight, up to a constant multiplicative factor for the degrees di depending on g.
In particular, we show that a graph embeddable on a surface of Euler genus γ is (0, 0, 0, K1(γ))-colorable and (2, 2, K2(γ))-colorable, where K1(γ) and K2(γ) are linear functions in γ.This talk is based on results and discussions with H. Choi, F. Dross, L. Esperet, J. Jeong, M. Montassier, P. Ochem, A. Raspaud, and G. Suh.

In this talk, I attempt to provide a comprehensive introduction to the matroid properties that hold for almost all matroids.

Welsh conjectured that almost all matroids are paving, open for nearly 50 years. If true, the properties of paving matroids translate to almost all matroids, such as non-representability, concentrated ranks, high connectivity and so on. We shall see the related properties that are shown to hold for almost all matroids with some of the proofs. An overview of recent progress and possible further directions will also be presented.

Information Center for Basic Sciences KAIST
291 Daehak-ro, Yuseong-gu, Daejeon 305-701, Republic of Korea
TEL +82-42-869-8196, FAX +82-42-869-5722, e-mail : mathnet@mathnet.or.kr
Copyright (c) 2017 by The MathNet Koea. All Rights Reserved