Events

Title: Graph Continued Fractions

Abstract:

This talk is about a connection between matching polynomials and continued fractions. For the matching polynomials: we prove a refinement of a theorem by Ku and Wong, which extends the classical Gallai-Edmonds decomposition;

Title: Structured (In)Feasibility: Nonmonotone Operator Splitting in Nonlinear Spaces

Abstract:

Several challenging optimization problems in power networks involve operational decisions, non-linear models of the underlying physics described by the network as well as uncertainty in the system parameters. However, these networks exhibit a nice structure. This talk provides an overview of approaches that combine recent advances in robust optimization and conic relaxations of polynomial optimization problems along with exploiting the structure of the underlying problem. These approaches are demonstrated on applications arising in power networks.

Title: Forcing Quasirandomness in Permutations

Abstract:

A striking result in graph theory is that the property of a graph being quasirandom (i.e. resembling a random graph) is characterized by the number of edges and the number of 4-cycles being close to the expected number in a random graph. Král’ and Pikhurko (2013) proved an analogous result for permutations; i.e. that quasirandom permutations are characterized by the densities of all permutations of length 4.

Title: Quantum information science for combinatorial optimization

Abstract:

Due to input-output bottlenecks, quantum computers are expected to be most applicable to problems for which the quantity of data specifying the instance is small but the computational cost of finding a solution is large. Aside from cryptanalysis and quantum simulation, combinatorial optimization provides some of the best candidates for problems of real-world impact fitting these criteria. Many of these problems are NP-hard and thus unlikely to be solvable on quantum computers with polynomial worst-case time complexity.

Title: Four families of polynomials in spectral graph theory

Abstract:

 In this talk we describe four families of polynomials related to the spectrum of a graph. First, some known main results involving such polynomials, such as the spectral excess theorem characterizing distance-regularity, are discussed. Second, some new results giving bounds for the $k$-independence number $\alpha_k$ of a graph are presented. In this context, we comment on some relationships between the inertia (Cvetkovi\`c) and ratio (Hoffman) bounds of $\alpha_k$.

Title: Newell-Littlewood numbers

Abstract:

The Newell-Littlewood numbers are defined in terms of the Littlewood-Richardson coefficients. Both arise as tensor product multiplicities for a classical Lie group. A. Klyachko connected eigenvalues of sums of Hermitian matrices to the saturated LR-cone and established defining linear inequalities.

Title: Induced subgraphs and treewidth

Abstract:

Treewidth, introduced by Robertson and Seymour in the graph minors series, is a fundamental measure of the complexity of a graph. While their results give an answer to the question, “what minors occur in graphs of large treewidth?,” the same question for induced subgraphs is still open. I will talk about some conjectures and recent results in this area.

Joint work with Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Sepehr Hajebi, Pawel Rzazewski, Kristina Vuskovic.

Title: Dyadic Linear Programming

Abstract:

Most linear programming solvers use fixed-precision floating points to approximate the rational numbers. Though successful on most real-world instances, solvers sometimes run into serious issues when carrying out sequential floating-point arithmetic, due to compounded error terms. This practical limitation leads to the following theoretical problem:

Title: State transfer on graphs with twin vertices

Abstract:

In this talk, we discuss algebraic and spectral properties of graphs with twin vertices that are important in quantum state transfer. We give a characterization of strong cospectrality between twin vertices, and characterize some types of state transfer that occur between them.

Title: The results of a search for small association schemes with noncyclotomic eigenvalues

Abstract: