KAIST Discrete Math Seminar

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.

Computational geometry deals with basic geometric objects such as points, line segments, polygons, and polyhedra, and aims to develop efficient algorithms and data structures for solving problems by figuring out the geometric, combinatorial, and topological properties of the objects. It has provided numerous methods and algorithms to solve geometric problems in application areas efficiently, such as computer graphics, robotics, geographic information systems, computer vision, and computational biology.
The traditional geometric algorithms, however, are not adequate for real-world data because they are not designed to handle imprecise and uncertain data and therefore they may return a wrong answer due to the imprecision or uncertainty of data.
This talk will provide an introduction to recent results of computational geometry on real-world data and open questions.

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).

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.

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.