Combinatorics Seminars
Apr 11, 2024 02:00 PM
ZOOM
Speaker: Ellen Veomett (University of San Francisco)
Title: Mathematical Questions in Redistricting and Detecting Gerrymandering
Abstract: Please come learn how your skills and expertise as a mathematician can be used to improve our democracy! We'll discuss what redistricting is, and mathematical metrics that can help to determine whether or not a redistricting map is "fair." We'll also learn about the redistricting "metagraph," which is (as you probably guessed) a graph of graphs. (This is the kind of graph you've heard of in your discrete math or combinatorics class). The structure of this metagraph is unknown, and has impacts on whether a tool that is frequently cited in courts does a good job of sampling potential redistricting maps. Finally, we'll look at two-player-games in redistricting. In particular, we'll look at trees that arise from the "Connected Recursive Bisection" protocol, which is a two-player game to create a redistricting map.
DMS Combinatorics Seminar
Apr 09, 2024 02:00 PM
328 Parker Hall
Speaker: Zach Walsh (Georgia Tech/Auburn)
Title: New lift matroids for gain graphs
Abstract: Given a graph G with edges labeled by a group, a construction of Zaslavsky gives a rank-1 lift of the graphic matroid of G that respects the group labeling. For which finite groups can we construct a rank-t lift of the graphic matroid of G with t > 1 that respects the group labeling? We show that this is possible if and only if the group is the additive group of a non-prime finite field. We assume no knowledge of matroid theory.
This is joint work with Daniel Bernstein.
DMS Combinatorics Seminar
Apr 02, 2024 02:00 PM
328 Parker Hall
Speaker: Aseem Dalal (IIT Delhi)
Title: On Total Chromatic Number of Graphs Having Triangle-Free Core
DMS Combinatorics Seminar
Mar 26, 2024 11:00 AM
228 Parker Hall
Speaker: Ben Baker
Title: Searching for a Conway-99 Graph
DMS Combinatorics Seminar
Mar 21, 2024 02:00 PM
328 Parker Hall
Speaker: Evan Leonard (Auburn)
Title: Constructions based on a refinement of list coloring
DMS Combinatorics Seminar
Mar 14, 2024 02:00 PM
328 Parker Hall
Speaker: Colby Muir (Auburn University)
Title: Modified Feng-Rao Decoding for Two-Point Codes
Abstract: Matthews introduces a class of two-point algebraic-geometry codes with better parameters than the correlated one-point codes. However, there was no decoding scheme provided. We develop a decoding scheme (with codes as well) by reducing the two-point code into one-point form and use a modified Feng-Rao algorithm to produce the error positions and magnitudes.
DMS Combinatorics Seminar
Feb 29, 2024 02:00 PM
328 Parker Hall
Speaker: Jie Ma (University of Science and Technology of China)
Title: On extremal problems on k-critical graphs
Abstract: A graph is called k-critical if its chromatic number is k but any proper subgraph has chromatic number less than k. There has been extensive research on k-critical graphs over the past decades, yet several basic problems remain widely open. One of such problems is to determine the maximum number of edges in an n-vertex k-critical graph. In this talk, we will discuss some recent results on extremal aspects of k-critical graphs.
DMS Combinatorics Seminar
Feb 27, 2024 02:00 PM
328 Parker Hall
Speaker: Manuel Fernandez (Georgia Tech)
Title: On the \(\ell_0\)-Isoperimetry of Measurable Sets
Abstract: Gibbs-sampling, also known as coordinate hit-and-run (CHAR), is a random walk used to sample points uniformly from convex bodies. Its transition rule is simple: Given the current point p, pick a random coordinate i and resample the i'th coordinate of p according to the distribution induced by fixing all other coordinates. Despite its use in practice, strong theoretical guarantees regarding the mixing time of CHAR for sampling from convex bodies were only recently shown in works of Laddha and Vempala, Narayanan and Srivastava, and Narayanam, Rajaraman and Srivastava. In the work of Laddha and Vempala, as part of their proof strategy, the authors introduced the notion of the \(\ell_0\) isoperimetric coefficient of a measurable set and provided a lower bound for the quantity in the case of axis-aligned cubes. In this talk we will present some new results regarding the \(\ell_0\) isoperimetric coefficient of measurable sets. In particular we pin down the exact order of magnitude of the \(\ell_0\) isoperimetric coefficient of axis-aligned cubes and present a general upper bound of the \(\ell_0\) isoperimetric coefficient for any measurable set. As an application, we will mention how the results give a moderate improvement in the mixing time of CHAR.
DMS Combinatorics Seminar
Feb 22, 2024 02:00 PM
328 Parker Hall
Speaker: James Anderson (Georgia Tech)
Title: The forb-flex method for odd coloring and proper conflict-free coloring of planar graphs
Abstract: Odd coloring (resp, PCF coloring) is a stricter form of proper vertex coloring in which every nonisolated vertex is required to have a color in its neighborhood with odd multiplicity (resp, with multiplicity 1).
We introduce a new tool useful for these colorings, based on greedy coloring, which we call the forb-flex method. Combining this with the discharging method allows us to prove \(\chi_{\mathsf{PCF}}(G) \leq 4\) for planar graphs of girth at least 11, and \(\chi_{\mathsf{o}}(G) \leq 4\) for planar graphs of girth at least 10, improving upon the recent works of Cho, Choi, Kwon, and Park. (We will give a brief overview of the discharging method, so no prior knowledge of discharging is required).
DMS Combinatorics Seminar
Feb 01, 2024 02:00 PM
328 Parker Hall
Speaker: Corrine Yap (Georgia Tech)
Title: Reconstructing Random Pictures
Abstract: Reconstruction problems ask whether or not it is possible to uniquely build a discrete structure from the collection of its substructures of a fixed size. This question has been explored in a wide range of settings, most famously with graphs and the resulting Graph Reconstruction Conjecture due to Kelly and Ulam, but also including geometric sets, jigsaws, and abelian groups. In this talk, we'll consider the reconstruction of random pictures (n-by-n grids with binary entries) from the collection of its k-by-k subgrids and prove two-point concentration for the threshold value of k = k(n). Our main proof technique is an adaptation of the Peierls contour method from statistical physics. Joint work with Bhargav Narayanan.