Cyril Nicaud, Introduction to analytic combinatorics

October 4th, 2016
Introduction to analytic combinatorics
Cyril Nicaud
Laboratoire d’Informatique Gaspard Monge (LIGM), Université Paris-Est, France
2016/10/19 Wed 4PM-5PM
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.

[Colloquium] Chris Godsil, Quantum walks on graphs

September 13th, 2016

FYI: Colloquium of Dept. of Mathematical Sciences.

Quantum walks on graphs.
Chris Godsil
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada
2016/11/17 Thu 4:15PM-5:15PM
A quantum walk is a (rather imperfect analog) of a random walk on a graph. They can be viewed as gadgets that might play a role in quantum computers, and have been used to produce algorithms that outperform corresponding classical procedures. Physical questions about these walks lead to problems in spectral graph theory, and they also provide interesting new graph invariants. In my talk I will present some of the background, and some of the many open problems that they have given rise to.

David Roberson, Homomorphisms of Strongly Regular Graphs

October 17th, 2016
Homomorphisms of Strongly Regular Graphs
David Roberson
Department of Computer Science, University College London, London, UK
2016/11/16 Wed 4PM-5PM
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.

[SoC Colloquium] Gyesik Lee (이계식), Program Extraction from Proofs

October 13th, 2016

FYI: Colloquium, School of Computing

Program Extraction from Proofs
Gyesik Lee (이계식)
Dept. of Computer Science and Engineering, Hankyong National University, Anseong, South Korea
2016-10-17 Mon 4PM-6PM
The Curry–Howard correspondence says that there is an isomorphic relation between intuitionistic logic and a constructive type theory. The basic idea is that intuitionistic proofs of mathematical formulas contain constructive information to prove them and that the information can be represented as concrete terms in a constructive type theory. One can then use these information and terms to extract computer programs from proofs. The resulting programs are error-free and correct in the sense that they satisfy the prescribed specifications. That means it is certified that the programs work as expected. This talk will explain the basic idea of Curry-Howard correspondence and its use in extracting certified programs.

O-joung Kwon (권오정), Generalized feedback vertex set problems on bounded-treewidth graphs

October 12th, 2016
Generalized feedback vertex set problems on bounded-treewidth graphs
O-joung Kwon (권오정)
Technische Universitat Berlin, Berin, Germany
2016/11/25 Fri 4PM-5PM
It has long been known that Feedback Vertex Set can be solved in time 2O(w log w)nO(1) on graphs of treewidth w, but it was only recently that this running time was improved to 2O(w)nO(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 𝒫 of graphs, the Bounded 𝒫-Block Vertex Deletion problem 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 and is in 𝒫. Assuming that 𝒫 is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d:
  • if 𝒫 consists only of chordal graphs, then the problem can be solved in time 2O(wd^2)nO(1),
  • if 𝒫 contains a graph with an induced cycle of length ℓ≥4, then the problem is not solvable in time 2o(w log w) nO(1) even for fixed d=ℓ, unless the ETH fails.

We further show that it is W[1]-hard parameterized by only treewidth, when 𝒫 consists of all graphs. This is joint work with Édouard Bonnet, Nick Brettell, and Daniel Marx.

[Lecture series]Xavier Goaoc, Topological methods for discrete geometry

October 4th, 2016

MFRS Lecture Series

Topological methods for discrete geometry
Xavier Goaoc
Université Paris-Est Marne-la-Vallée, France
2016/11/04 Fri 4PM-6PM (Lecture 1)
2016/11/07 Mon 4PM-6PM (Lecture 2)
Helly’s theorem, a classical result in discrete geometry, asserts that if n>d convex subsets of R^d have empty intersection, some d+1 of them must already have empty intersection. I will discuss some topological generalizations of Helly’s theorem, where convexity is replaced by connectivity assumptions on the nonempty intersections, that lead to non-embeddability results of Borsuk-Ulam type and to variations on Leray’s acyclic cover theorem (or the Nerve theorem).

Xavier Goaoc, Embedding complete graphs in surfaces: what about higher dimensions?

October 4th, 2016
Embedding complete graphs in surfaces: what about higher dimensions?
Xavier Goaoc
Université Paris-Est Marne-la-Vallée, France
2016/11/02 Wed 4PM-5PM
The fact that the complete graph K5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that Kn embeds in a closed surface M if and only if (n − 3)(n − 4) ≤ 6b1(M), where b1(M) is the first Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of Kn+1 embeds in R2k if and only if n ≤ 2k + 1.
I will discuss a conjecture of Kuhnel that generalizes both the Heawood inequality and the van Kampen-Flores theorem, and present some partial results toward this conjecture.