Seminar

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: 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: 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: 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: Central Limit Theorems via Analytic Combinatorics in Several Variables

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

Abstract: Analytic combinatorics in several variables is a field of study focused on the derivation of limit behaviours of multivariate sequences. In this talk, I will describe a local central limit theorem and its applications to a variety of examples. Included in these examples will be a family of permutations with restricted cycles, integer compositions with tracked summands and n-colour compositions with tracked summands. The proof of this new, automated, local central limit theorem will also be briefly discussed, using techniques from the theory of analytic combinatorics in several variables. I will also provide background for proving central limit theorems probabilistically.

Title: Which graphs are determined by their total numbers of walks?

Abstract: Walks and closed-walks are ubiquitous in graph theory, which capture lots of important structural information of graphs. In this talk, we shall consider the question in the title. The same question for closed walks is precisely the problem of spectral characterizations of graphs. We show that for most graphs, the number of walks determines the generalized spectrum of graphs and vice versa. Then the above question is equivalent to the problem of generalized spectral characterizations of graphs, a topic which has been studied extensively in recent years. Some simple criterions are provided for graphs G to be determined by their total number of walks, based on some recent results on the generalized spectral characterizations of graphs. Numerical results are also provided to illustrate the effectiveness of the proposed method. This is a joint work with Weifang Lv, Finjin Liu and Wei Wang.

Title: Multicommodity Flows and Cuts

Abstract: Flow and cut problems occupy a central place in discrete optimzation and algorithms. The well known max-flow min-cut theorem states that there exists a s-t flow of value d in a network if and only if the minimum capacity of edges whose removal separates s and t is at least d. In this talk, we will discuss a generalization of this problem to the multicommodity setting and study natural necessary and sufficient conditions for the existence of a feasible flow. We will discuss connections to approximation algorithms, metric embeddings and partitions, and survey some of the classical results, open problems and recent progress.

Title: Sometimes you can't compute on encrypted data 

Abstract: A long dream in cryptography was "fully homomorphic encryption": the ability to perform computations on encrypted data. This way, a cloud provider can do your computations without compromising your privacy. The first general method was proposed by Gentry in 2009, but this method and follow up works are all too slow for many purposes. Naturally, we want to do better. This talk will explain some work in progress from a pessimistic perspective: when can we prove that faster methods are impossible.

Title: The spectra of lift and factored lifts of graphs or digraphs

Abstract: In this talk, we first explain the path we took from defining polynomial matrices to a generalization of voltage graphs that we call combined voltage graphs. Moreover, we give a general definition of a matrix associated with a combined voltage graph, which allows us to provide a new method for computing the eigenvalues and eigenspaces of such graphs. 

Title: Introducing the interval poset associahedron

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

Abstract: Given a permutation, we define its interval poset to be the set of all intervals ordered by inclusion. In this framework, a 'tube' is a convex connected subset, while a 'tubing' denotes a collection of tubes, that are pairwise either nested or disjoint. The interval poset associahedron is a polytope, whose faces correspond to proper tubes and whose vertices correspond to maximal tubings of the interval poset of a given permutation.

If we start with a simple permutation, the resulting interval poset associahedron will be isomorphic to the permutahedron. And if we consider inverse permutations, it turns out, that they yield identical associahedra.

If there is time, I will discuss another order on permutations, the Bruhat order, and compare it to the permutahedron.