On the Erdős-Szekeres convex polygon problem

May 25th, 2016
On the Erdős-Szekeres convex polygon problem
Andreas Holmsen
Department of Mathematical Sciences, KAIST
2016/05/27 4PM (Room 2411 of Bldg E6-1)
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.

Neil Immerman, Towards Capturing Order-Independent P

May 4th, 2016

FYI: Joint Seminar on Theoretical Computer Science

Towards Capturing Order-Independent P
Neil Immerman
College of Information and Computer Sciences, University of Massachusetts Amherst, Amherst, MA, USA
2016/5/11 Wed 4PM-5PM (E3-1, Room 3445)
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.

Suil O (오수일), Interlacing families and the Hermitian spectral norm of digraphs

April 20th, 2016
Interlacing families and the Hermitian spectral norm of digraphs
Suil O (오수일)
Department of Mathematics, Simon Fraser University, Burnaby, B.C., Canada
2016/6/1 Wed 4PM-5PM
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.

(Colloquium) András Sebő, Classical tools and recent advances in combinatorial optimization

April 4th, 2016

FYI: Colloquium of Dept. of Mathematical Sciences.

Classical tools and recent advances in combinatorial optimization
András Sebő
CNRS, Laboratoire G-SCOP, Université Grenoble-Alpes, France
2016/04/28 Thu 4:15PM-5:15PM (Room 1501, Bldg. E6-1)
Combinatorial optimization has recently discovered new usages of probability theory, information theory, algebra, semidefinit programming, etc. This allows addressing the problems arising in new application areas such as the management of very large networks, which require new tools. A new layer of results make use of several classical methods at the same time, in new ways, combined with newly developed arguments.
After a brief panorama of this evolution, I would like to show the new place of the best-known, classical combinatorial optimization tools in this jungle: matroids, matchings, elementary probabilities, polyhedra, linear programming.
More concretely, I try to demonstrate on the example of the Travelling Salesman Problem, how strong meta-methods may predict possibilities, and then be replaced by better suited elementary methods. The pillars of combinatorial optimization such as matroid intersection, matchings, T-joins, graph connectivity, used in parallel with elements of freshmen’s probabilities, and linear programming, appropriately merged with newly developed ideas tailored for the problems, may not only replace difficult generic methods, but essentially improve the results. I would like to show how this has happened with various versions of the TSP problem in the past years (see results of Gharan, Saberi, Singh, Mömke and Svensson, and several recent results of Anke van Zuylen, Jens Vygen and the speaker), essentially improving the approximation ratios of algorithms.

András Sebő, The Salesman’s Improved Paths

April 4th, 2016
The Salesman’s Improved Paths
András Sebő
CNRS, Laboratoire G-SCOP, Université Grenoble-Alpes, France
2016/05/04 Wed 4PM-5PM
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.