Welcome to Combinatorics and Optimization

Title: Symmetric and Skew-Symmetric Signing for Graphs

Abstract:

We consider symmetric and skew-symmetric signings for graphs. A signing for a graph G = (V, E) is a mapping σ : (x, y) | x, y in V \} to {0, ± 1} with the following properties:

• σ(x, y) ≠ 0 if and only if {x, y} in E,
• σ(x, y) = σ(y, x) for any distinct x, y in V with {x, y} in E.

For a signing σ of a graph, we define the signed adjacency matrix A_σ of the graph, where the (x, y)-entry of A_σ is equal to σ(x, y). We study the problem of finding lower bounds for the spectral radius of A_σ and aim to determine a signing for a given graph such that its spectral radius is the smallest among all possible signings of that graph. A signing of a small spectral radius plays an important role in constructing Ramanujan graphs.  Additionally, we consider a variation of signing, which we call skew-symmetric signing for graphs.

This talk is based on joint work with Jack Koolen and Hadi Kharaghani.

Title:New results on the complexity of edge-modification problems

Abstract:

For a k-uniform hypergraph H, the H-freeness edge modification problem is the algorithmic problem of finding, for a given k-uniform input G, the distance of G from H-freeness, i.e., the minimum number of edges that need to be deleted from G in order to obtain an H-free hypergraph. I will present new results on the computational complexity of this general problem. In particular, I will show that if H is not k-partite, then it is NP-hard to compute the distance to H-freeness, and even to approximate this distance up to an additive error of n^{k-delta} for any fixed delta > 0. This resolves a special case of a problem raised by Ailon and Alon.

This is a joint work with Yevgeny Levanzov and Asaf Shapira.

Title: Schubert calculus by counting puzzles

 Abstract: There are three rings-with-bases whose multiplicative structure constants are computed by the same rule: the cohomology ring of the Grassmannian Gr(k,n), the representation ring of GL_k (made by stabilizing the previous in n), and one made by summing all representation rings of the symmetric groups (made by stabiliizing the previous in k). The most famous rules, typically involving counting Young tableaux, are for the most stable version, but the unstable version admits the most generalizations, to K-theory, equivariant cohomology, quantum cohomology, and to other homogeneous varieties. I'll explain how to compute the multiplication in many of these cases by counting "puzzles".

This work is joint with Terry Tao and Paul Zinn-Justin.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,