Seminars and Colloquia by Series

Probabilistic Method in Combinatorics

Series
Undergraduate Seminar
Time
Monday, September 14, 2020 - 15:30 for 1 hour (actually 50 minutes)
Location
Bluejeans meeting https://bluejeans.com/759112674
Speaker
Dr. Lutz WarnkeGeorgia Tech
The Probabilistic Method is a powerful tool for tackling many problems in discrete mathematics and related areas. Roughly speaking, its basic idea can be described as follows. In order to prove existence of a combinatorial structure with certain properties, we construct an appropriate probability space, and show that a randomly chosen element of this space has the desired property with positive probability. In this talk we shall give a gentle introduction to the Probabilistic Method, with an emphasis on examples.

L-space surgeries on 2-component L-space links

Series
Geometry Topology Seminar
Time
Monday, September 14, 2020 - 14:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/803706608
Speaker
Beibei LiuGeorgia Tech

All 3-manifolds can be described as surgery on links in the three-sphere by the celebrated theorem of Lickorish and Wallace. Motivated by the L-space conjecture, it is interesting to understand what surgery manifolds are L-spaces, which have the simplest possible Floer homology such as lens spaces. In this talk, we concentrate on surgeries on a family of links, which are called L-space links, and show possible L-space surgeries on such links. We also give some link detection results in terms of the surgeries. 

The chromatic number of a random lift of K_d

Series
Combinatorics Seminar
Time
Friday, September 11, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Xavier Pérez GiménezUniversity of Nebraska-Lincoln

An n-lift of a graph G is a graph from which there is an n-to-1 covering map onto G. Amit, Linial, and Matousek (2002) raised the question of whether the chromatic number of a random n-lift of K_5 is concentrated on a single value. We consider a more general problem, and show that for fixed d ≥ 3 the chromatic number of a random lift of K_d is (asymptotically almost surely) either k or k+1, where k is the smallest integer satisfying d < 2k log k. Moreover, we show that, for roughly half of the values of d, the chromatic number is concentrated on k. The argument for the upper-bound on the chromatic number uses the small subgraph conditioning method, and it can be extended to random n-lifts of G, for any fixed d-regular graph G. (This is joint work with JD Nir.)

Online Selection with Cardinality Constraints under Bias

Series
ACO Student Seminar
Time
Friday, September 11, 2020 - 13:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/264244877/0166
Speaker
Jad SalemMath, Georgia Tech

Optimization and machine learning algorithms often use real-world data that has been generated through complex socio-economic and behavioral processes. This data, however, is noisy, and naturally encodes difficult-to-quantify systemic biases. In this work, we model and address bias in the secretary problem, which has applications in hiring. We assume that utilities of candidates are scaled by unknown bias factors, perhaps depending on demographic information, and show that bias-agnostic algorithms are suboptimal in terms of utility and fairness. We propose bias-aware algorithms that achieve certain notions of fairness, while achieving order-optimal competitive ratios in several settings.

TBA by Tianyi Zhang

Series
Student Algebraic Geometry Seminar
Time
Friday, September 11, 2020 - 09:00 for 1 hour (actually 50 minutes)
Location
Microsoft Teams Meeting
Speaker
Tianyi ZhangGeorgia Tech

Please Note: Link to meeting: https://teams.microsoft.com/l/meetup-join/19%3a3a9d7f9d1fca4f5b991b4029b09c69a1%40thread.tacv2/1599679148202?context=%7b%22Tid%22%3a%22482198bb-ae7b-4b25-8b7a-6d7f32faa083%22%2c%22Oid%22%3a%223eebc7e2-37e7-4146-9038-a57e56c92d31%22%7d

Couplings of Markov chain Monte Carlo and their uses

Series
Stochastics Seminar
Time
Thursday, September 10, 2020 - 15:30 for 1 hour (actually 50 minutes)
Location
https://us02web.zoom.us/j/83378796301
Speaker
Pierre JacobHarvard University

Markov chain Monte Carlo (MCMC) methods are state-of-the-art techniques for numerical integration. MCMC methods yield estimators that converge to integrals of interest in the limit of the number of iterations, obtained from Markov chains that converge to stationarity. This iterative asymptotic justification is not ideal. Indeed the literature offers little practical guidance on how many iterations should be performed, despite decades of research on the topic. This talk will describe a computational approach to address some of these issues. The key idea, pioneered by Glynn and Rhee in 2014, is to generate couplings of Markov chains, whereby pairs of chains contract, coalesce or even "meet" after a random number of iterations; we will see that these meeting times, which can be simulated in many practical settings, contain useful information about the finite-time marginal distributions of the chains. This talk will provide an overview of this line of research, joint work with John O'Leary, Yves Atchadé and various collaborators.
The main reference is available here: https://rss.onlinelibrary.wiley.com/doi/abs/10.1111/rssb.12336

Singularity of sparse Bernoulli matrices with$ p$ is close to $\log(n)/n$.

Series
High Dimensional Seminar
Time
Wednesday, September 9, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Join Zoom Meeting https://us02web.zoom.us/j/88203571169 Meeting ID: 882 0357 1169
Speaker
Han HuangGeorgia Tech

It has been conjectured that for a sufficiently large $n$, and $p = p_n \in [\log(n)/n, 1/2)$, the probability that a $n\times n$ Bernoulli($p$) matrix $A$ is singular equals to the probability that $A$ contains of a zero row or zero column up to a negligible error.

This conjecture has been recently proved by Litvak-Tikhomirov in the regime $ C\log(n)/ n < p < 1/C$ for some universal constant $C>1$ with their new tool. While for $p = (1+o(1)) \log(n) /n$, it also holds due to a result of Basak-Rudelson. In this talk, we will discuss how to extend their results to fill the gap between these two regions. ( $1\le pn/\log(n) <\infty$ )

Knot Concordance

Series
Geometry Topology Student Seminar
Time
Wednesday, September 9, 2020 - 14:00 for 1 hour (actually 50 minutes)
Location
Speaker
Hugo ZhouGeorgia Tech

Two knots are concordant to each other if they cobound an annulus in the product of S^3. We will discuss a few basic facts about knot concordance and look at J. Levine’s classical result on the knot concordance group.

Unavoidable dense induced subgraphs

Series
Graph Theory Seminar
Time
Tuesday, September 8, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/681348075/???? (replace ???? with password). For password, please email Anton Bernshteyn (bahtoh~at~gatech.edu)
Speaker
Rose McCartyUniversity of Waterloo

Thomassen conjectures that every graph of sufficiently large average degree has a subgraph of average degree at least d and girth at least k, for any d and k. What if we want the subgraph to be induced? Large cliques and bicliques are the obvious obstructions; we conjecture there are no others. We survey results in this direction, and we prove that every bipartite graph of sufficiently large average degree has either K_{d,d} or an induced subgraph of average degree at least d and girth at least 6.

On the Helfgott-Lindenstrauss conjecture for linear groups

Series
Combinatorics Seminar
Time
Friday, September 4, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Brendan MurphyUniversity of Bristol

Freiman's theorem characterizes finite subsets of abelian groups that behave "approximately" like subgroups: any such set is (roughly) a sum of arithmetic progressions and a finite subgroup. Quantifying Freiman's theorem is an important area of additive combinatorics; in particular, proving a "polynomial" Freiman theorem would be extremely useful.

The "Helfgott-Lindenstrauss conjecture" describes the structure of finite subsets of non-abelian groups that behave approximately like subgroups: any such set is (roughly) a finite extension of a nilpotent group. Breuillard, Green, and Tao proved a qualitative version of this conjecture. In general, a "polynomial" version of the HL conjecture cannot hold, but we prove that a polynomial version of the HL conjecture is true for linear groups of bounded rank.

In this talk, we will see how the "sum-product phenomenon" and its generalizations play a crucial role in the proof of this result. The amount of group theory needed is minimal.

Pages