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: Counting matroid extensions

Abstract: In this talk, we will discuss methods of counting the number of extensions of certain matroids. We will see that, in some cases, the number of extensions is surprisingly large. I will start by introducing matroids, so previous experience with matroids is not assumed.

Title: Budget Feasible Mechanisms

Abstract: In the setting of budget feasible mechanism design, a buyer wants to purchase items from a set of agents. Each agent can supply at item at an incurred cost of c_i to themself, and the buyer wants to optimize over their own valuation for the set of items bought. The cost c_i is private information that the buyer doesn't have access to. The goal is to design a mechanism that is truthful, in the sense that the sellers do not have incentive to deviate from reporting their true costs, and budget feasible, in the sense that the total payments made to the sellers is within some budget B.

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: URA Presentations

Abstract: A series of presentations by a group of Spring 2023 Undergraduate Research Assistants. The topics of each presentation are detailed below.

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: URA Presentations

Abstract: A series of presentations by a group of Spring 2023 Undergraduate Research Assistants. The topics of each presentation are detailed below.

Quantum Max-Cut on Bipartite Graphs - Benjamin Wong

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: Kissing Polytopes

Abstract: We investigate the following question: how close can two disjoint lattice polytopes contained in a fixed hypercube be? This question stems from various contexts where the minimal distance between such polytopes appears in complexity bounds of optimization algorithms.