KAIST Discrete Math Seminar

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.

In Descriptive Complexity we characterize the complexity of decision problems by how rich a logical language is needed to describe the problem. Important complexity classes have natural logical characterizations, for example NP is the set of problems expressible in second order existential logic (NP = SOE) and P is the set of problems expressible in first order logic, plus a fixed point operator (P = FO(FP)).
The latter characterization is over ordered graphs, i.e. the vertex set is a linearly ordered set. This is appropriate for computational problems because all inputs to a computer are ordered sequences of bits. Any ordering will do; we are interested in the order-independent properties of graphs. The search for order-independent P is closely tied to the complexity of graph isomorphism. I will explain these concepts and the current effort to capture order-independent P.

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.)
This is joint work with Anke van Zuylen.