Welcome to Combinatorics and Optimization

Title: Positivity of P-Recursive Sequences Satisfying Linear Recurrences

 Abstract: Whether it is decidable to determine when sequences satisfying linear recurrences with constant coefficients have all positive terms is a notorious problem in enumerative combinatorics that has essentially been open for around 90 years. Nevertheless, a "meta-principle" states that all such sequences arising from combinatorial counting problems belong to a special class where positivity (and more general asymptotic

behaviour) is decidable. Here we discuss new software for determining positivity for sequences satisfying linear recurrences with *polynomial* coefficients. Originally motivated by a novel approach to proving genus one solution uniqueness for the Canham model for biomembrane shapes, our algorithm combines rigorous numeric analytic continuation of functions satisfying linear ODEs with singularity analysis techniques from analytic combinatorics. The main talk will be presented using a live Sage Jupyter notebook, and audience members who have access to Sage with a recent version of the ore_algebra package installed (available at

https://github.com/mkauers/ore_algebra) will be able to follow along and play with the package during the talk.

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

Title:A bound on the quantum value of all compiled nonlocal games

Abstract: Nonlocal games provide valuable insights into quantum entanglement and even enable a classical verifier to confirm and control the behavior of entangled quantum provers. However, an issue with this approach has always been the necessity of two non-communicating quantum provers. To address this issue, a group of researchers recently introduced a "compilation procedure" that reduces the need for multiple provers and enforces non-communication through cryptographic methods. In this talk, we will show that even in this single prover "compiled setting," the prover remains fundamentally constrained. Specifically, we show that any polynomial-time quantum prover cannot win the "compiled game" with a higher probability than any quantum commuting provers could win the original nonlocal game. Our result is derived through a novel combination of techniques from cryptography and operator algebras and allows us to recover several important self-testing results in the "compiled setting".

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.