Events

Title: Ramsey Cayley graphs, random graph models, and information theory

Abstract: A graph is Ramsey if its largest clique or independent set is of size logarithmic in the number of vertices. While almost all graphs are Ramsey, there is still no known explicit construction of Ramsey graphs. Alon conjectured that every finite group has a Ramsey Cayley graph.

Title: Combinatorial and complexity theoretic aspects of Stabilities and Controllabilities of linear switched systems(discrete and continuous time)

Abstract: I will talk about my "pre-hyperbolic" research, some of it done jointly with Alex Samorodnitsky and Alex Olshevsky.

Title: Rigidity of Simplicial Complexes

Abstract: A simplicial k-cycle is an abstract simplicial k-complex in which every (k-1)-face belongs to an even number of k-faces. A simplicial k-circuit is a minimal simplicial k-cycle (in the sense that none of its proper subcomplexes are simplicial k-cycles).

Title: Proof of the Clustered Hadwiger Conjecture

Abstract: Hadwiger's Conjecture asserts that every Kh-minor-free graph is properly (h-1)-colourable. We prove the following improper analogue of Hadwiger's Conjecture: for fixed h, every Kh-minor-free graph is (h-1)-colourable with monochromatic components of bounded size.

Title: An Approximate Generalization of the Okamura-Seymour Theorem

Abstract: We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands.

Title: A Simple Sparsification Algorithm for Maximum Matching with Applications to Graph Streams 

Abstract: In this talk, we present a simple algorithm that reduces approximating the maximum weight matching problem in arbitrary graphs to few adaptively chosen instances of the same problem on sparse graphs.

Title: The Chambolle-Pock algorithm revisited: splitting operator and its range with applications

Abstract: Primal-dual hybrid gradient (PDHG) is a first-order method for saddle-point problems and convex programming introduced by Chambolle and Pock. Recently, Applegate et al. analyzed the behavior of PDHG when applied to an infeasible or unbounded instance of linear programming, and in particular, showed that PDHG is able to diagnose these conditions.

Title: Algorithmic Tools for Congressional Districting: Fairness via Analytics

Abstract: The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. To date, computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness and other related metrics.

Title: Hypergraph Matchings Avoiding Forbidden Submatchings

Abstract: We overview a general theory for finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of forbidden submatchings (which we view as a hypergraph H where V(H)=E(G)).

Title: Diagonal coefficients, graph invariants with the symmetries of Feynman integrals, and the proof of the c_2 completion conjecture

Abstract: In a scalar field theory the contribution of a Feynman diagram to the beta function of the theory, the Feynman period, can be written as an integral in terms of the (dual) Kirchhoff polynomial of the graph.