Combinatorics Seminars
Sep 25, 2024 02:00 PM
328 Parker Hall
Speaker: Shira Zerbib (Iowa State University)
Title: Bounds on piercing numbers and line-piercing numbers in families of convex sets in the plane
Abstract: A family \(F\) of sets has the \((p,q)\) property if amongst any \(p\) members of it some \(q\) intersect. \(F\) has the \(T(k)\) property if every \(k\) sets in \(F\) are intersected by a line. We prove that if \(F\) is a family of convex sets in the plane with the \((p+1,2)\) property then there are \( \lfloor p/2\rfloor +1\) lines whose union intersects all the sets in \(F\), and this bound is tight. We use this result to prove new bounds on the piercing numbers in families of convex sets in the plane with the \((p,2)\) property, in terms of the matching numbers of their pairwise intersection families. We further prove a conjecture of Eckhoff from 1993, asserting that if a family of convex sets in the plane has the \(T(3)\) property then there are 3 lines whose union intersects all the sets in it. Rainbow versions of these results are also proved. The proofs use the topological KKM theorem and its colorful generalization.
Partly joined with Daniel McGinnis.
DMS Combinatorics Seminar
Sep 18, 2024 02:00 PM
328 Parker Hall
Speaker: Owen Henderschedt (Auburn University)
Title:On orientations of graphs with forbidden out-degrees
Abstract: When does a graph admit an orientation with some desired properties? This question has been extensively studied for many years and across many different properties. Specifically, I will talk about properties having to do with degree restrictions, and progress towards a conjecture of Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati dealing with a list-type of degree restriction. This is all joint work with Jessica McDonald.
DMS Combinatorics Seminar
Sep 11, 2024 12:55 PM
328 Parker Hall
Speaker: Arthur Tanyel (Auburn University)
Title: Degree sequence condition for Hamiltonicity in tough graphs
Abstract: Generalizing both Dirac's condition and Ore's condition for Hamilton cycles, Chvátal in 1972 established a degree sequence condition for the existence of a Hamilton cycle in a graph. Hoàng in 1995 generalized Chvátal's degree sequence condition for 1-tough graphs and conjectured a \(t\)-tough analogue for any positive integer \(t\ge 1\). Hoàng in the same paper verified his conjecture for \(t\le 3\) and recently Hoàng and Robin verified the conjecture for \(t=4\). In this talk, we present a proof of the conjecture for all \(t\ge 4\). The proof depends on two newly established results on cycle structures in tough graphs, which hold independent interest.
DMS Combinatorics Seminar
Sep 04, 2024 02:00 PM
328 Parker Hall
Speaker: Joseph Briggs (Auburn University)
Title: Colored ball sorting
Abstract: I will describe an algorithmic problem arising from a recently popularized puzzle format, and a beautiful extremal question asked by a large group of theoretical computer scientists. Graph-theoretic tools resolve one nontrivial instance, but otherwise, the problem is wide open.
DMS Combinatorics Seminar
Aug 28, 2024 02:00 PM
328 Parker Hall
Speaker: Chris Kapulkin, University of Western Ontario
Title: Effective computations of discrete homologyAbstract: Discrete homology is a graph invariant, known for its discerning power in analysis of social and technological networks. This talk will report on joint work with Nathan Kershaw on creating software for effective computations of this invariant. I will explain what discrete homology is and how it can be used in a variety of applied contexts, e.g., as an alternative to persistence homology in topological data analysis or as a poset invariant in systems biology.
In addition to presenting our techniques for effective computations, I will discuss some open problems of a combinatorial nature that would lead to further improvements in the software.
No prior knowledge of homology will be assumed.
DMS Algebra Seminar
Aug 20, 2024 02:30 PM
ZOOM
DMS Combinatorics Seminar
Apr 25, 2024 02:00 PM
328 Parker Hall
Speaker: Kyungyong Lee (University of Alabama)
Title: The Kazhdan-Lusztig polynomial of a matroid
Abstract: In 2016, Elias, Proudfoot, and Wakefield introduced the Kazhdan-Lusztig polynomial for every matroid. We present a combinatorial formula using skew Young tableaux for the coefficients of Kazhdan-Lusztig polynomials for sparse paving matroids. These matroids are known to be logarithmically almost all matroids, but are conjectured to be almost all matroids. In special cases, such as uniform matroids, our formula has a nice combinatorial interpretation. No background is required.
This is joint work with George D. Nasr and Jamie Radcliffe.
DMS Combinatorics Seminar
Apr 23, 2024 02:00 PM
328 Parker Hall
Speaker: Isabel Harris (Auburn)
Title: Avoiding k-Rainbow Graphs in Edge Colorings of Kn and other Families of Graphs
Abstract: A simple graph, G, avoids a k-rainbow edge coloring if any color appears on at least k+1 edges of G. For any positive integer k, the k-Anti-Ramsey Number, ARk(G, H), is the maximum number of colors in an edge coloring of the graph H on such that no k-rainbow edge colored copy of G is a subgraph of H. This talk will focus specifically on the edge colorings of complete graphs with n vertices, ARk(G,Kn)=ARk(G,n). We will say G is ARk-bounded if ARk(G,n) is bounded by some positive integer c for all n sufficiently large. In this talk we will discuss which simple graphs are ARk-bounded on the complete graph for any k. Additionally, we will explore some results for ARk(G,H), where H is not the complete graph.
DMS Combinatorics Seminar
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.