Events

Title: Recent Progresses on Correlation Clustering

Abstract: Correlation Clustering is one of the most well-studied graph clustering problems. The input is a complete graph where each edge is labeled either "+" or "-", and the goal is to partition the vertex set into (an arbitrary number of) clusters to minimize (the number of + edges between different clusters) + (the number of - edges within the same cluster). Until recently, the best polynomial-time approximation ratio was 2.06, nearly matching the integrality gap of 2 for the standard LP relaxation. Since 2022, we have bypassed this barrier and progressively improved the approximation ratio, with the current ratio being 1.44. Based on a new relaxation inspired by the Sherali-Adams hierarchy, the algorithm introduces and combines several tools considered in different contexts, including "local to global correlation rounding" and "combinatorial preclusering". In this talk, I will describe the current algorithm as well as how it has been inspired by various viewpoints. Joint work with Nairen Cao, Vincent Cohen-Addad, Shi Li, Alantha Newman, and Lukas Vogl.

Title: A general theorem in spectral extremal graph theory

Abstract: The extremal graphs $\mathrm{EX}(n,\mathcal F)$ and spectral extremal graphs $\mathrm{SPEX}(n,\mathcal F)$ are the sets of graphs on $n$ vertices with maximum number of edges and maximum spectral radius, respectively, with no subgraph in $\mathcal F$. We prove a general theorem which allows us to characterize the spectral extremal graphs for a wide range of forbidden families $\mathcal F$ and implies several new and existing results. In particular, whenever $\mathrm{EX}(n,\mathcal F)$ contains the complete bipartite graph $K_{k,n-k}$ (or certain similar graphs) then $\mathrm{SPEX}(n,\mathcal F)$ contains the same graph when $n$ is sufficiently large. We prove a similar theorem which relates $\mathrm{SPEX}(n,\mathcal F)$ and $\mathrm{SPEX}_\alpha(n,\mathcal F)$, the set of $\mathcal F$-free graphs which maximize the spectral radius of the matrix $A_\alpha=\alpha D+(1-\alpha)A$, where $A$ is the adjacency matrix and $D$ is the diagonal degree matrix.

Title: Rate-distortion theory for quantum data compression

Abstract: Quantum data compression is a fundamental quantum information processing task, where the sender compresses many copies of a given quantum state into the smallest possible storage space before transmitting it to the receiver. Among various quantum data compression setups and analyses, the trade-off between the efficiency (rate) and the error of the compression has been investigated using the framework of quantum rate-distortion theory, in which a small error is tolerated to improve the rate. In this talk, adopting the quantum rate-distortion theory, we reveal the optimal rate-error trade-off of quantum data compression with and without the assistance of quantum entanglement. Moreover, we generalize these results to figure out the full rate region where both the communication and entanglement rates vary. Thus, we successfully obtain a complete form of the rate-distortion theory of quantum data compression with entanglement.

Title: Self-dual axioms for infinite matroids on lattices

Abstract: In an informal sequel to my recent Tutte colloquium on the topic, I will talk about axiomatizing infinite matroids with a modular lattice in place of the usual ground set. I will present three sets of axioms that characterize these objects; two of the axiom sets are self-dual.

Title: Chord diagrams, triangulations, and $\phi^p$ amplitudes.

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

Abstract: I will discuss some combinatorics of non-crossing chord diagrams that arose in the context of proving a conjecture from my coauthor's thesis which said that the global Schwinger formula of Cachazo and Early could be decomposed into a sum over cones indexed by non-crossing chord diagrams and that the amplitudes can be read off the chord diagrams by a triangulation construction.

For this talk I will focus on the combinatorics, but will hand wave over the physics at some point between the seminar and the pre-seminar.

Joint work with Bruno Giménez Umbert.

Title: Stochastic Minimum Norm Combinatorial Optimization

Abstract: We develop a framework for designing approximation algorithms for a wide class of (1-stage) stochastic-optimization problems with norm-based objective functions. We introduce the model of stochastic minimum-norm combinatorial optimization, wherein the costs involved are random variables with given distributions, and we are given a monotone, symmetric norm f. Each feasible solution induces a random multidimensional cost vector whose entries are independent random variables, and the goal is to find a solution that minimizes the expected f-norm of the induced cost vector. This is a very rich class of objectives, containing all l_p norms, as also Top-l norms (sum of l largest coordinates in absolute value), which enjoys various closure properties.

Title: Webs and quantum representations

Abstract: A web is a directed, labeled plane graph satisfying certain conditions coming from representation theory. Each web corresponds to a specific invariant vector in a tensor product of fundamental representations of a quantum group. In this talk, we introduce a process called stranding, which encodes as the monomial terms in a web’s associated vector as a collection of paths in the web graph.  We also describe how the strandings connect seemingly-unrelated ideas in combinatorics (e.g. noncrossing matchings) and geometry (e.g. certain algebraic varieties called Springer fibers).

Title: Ramsey with purple edges

Abstract: Motivated by a question of David Angell, we study a variant of Ramsey numbers where some edges are coloured with both red and blue colours, (i.e. are called ‘purple’ edges). Specifically, we are interested in the largest number g = g(s, t, n), for some s and t and n < R(s, t), such that there exists a red-blue-purple colouring of Kn with g purple edges, without a red-purple Ks and without a blue-purple Kt. We determine g asymptotically for a large family of parameters. The talk will be introductory in nature. Since the concept of double-coloured edges is new in this context, there is a plethora of open questions. Joint work with Anita Liebenau and Nye Taylor.

Title: Graph theory and Feynman integrals

Abstract: Feynman integrals are one of the most versatile tools in theoretical physics. They are used to compute perturbative solutions for various interacting systems. Examples include scattering amplitudes in quantum field theory, gravitational waves at black hole mergers, and the scaling behavior in statistical physics at critical points. Every Feynman integral is defined in terms of a corresponding Feynman graph, and besides the concrete physical application, it is interesting to study the number theory of Feynman integrals and how they are related to combinatorial properties of the underlying graph. What can we know about the value of the integral from examining the graph alone? In particular: Under which conditions will the Feynman integrals of two non-isomorphic graphs evaluate to the same number?

Title: Shellability of complexes over lattices

Abstract: In this work, we introduce the notion of power lattices, which are a more general class of ranked lattices with additional properties. Then we generalize the concept of shellable simplicial complexes in the lattice of subsets to P-shellable P-complexes in a power lattice P. We show that when the P-complex is P-shellable, its order complex is a shellable simplicial complex. We demonstrate that these P-complexes can be constructed by generalizing the concept of matroids to matroids in a power lattice P. This provides various constructions of posets with desirable topological and algebraic properties. In the particular class of lattices of multiset subsets, we show how to construct shellable 'multicomplexes' from weighted graphs. Finally, we illustrate how shellable multicomplexes give rise to rings that are sequentially Cohen-Macaulay.