- Series
- Combinatorics Seminar
- Time
- Friday, February 9, 2024 - 3:15pm for 1 hour (actually 50 minutes)
- Location
- Skiles 308
- Speaker
- James Anderson, Sean Kafer, Tantan Dai – Georgia Tech
- Organizer
- Evelyne Smith-Roberge
James Anderson: Odd coloring (resp, PCF coloring) is a stricter form of proper coloring in which every nonisolated vertex is required to have a color in its neighborhood with odd multiplicity (resp, with multiplicity 1). Using the discharging method, and a new tool which we call the Forb-Flex method, we improve the bounds on the odd and PCF chromatic number of planar graphs of girth 10 and 11, respectively.
Sean Kafer: Many classical combinatorial optimization problems (e.g. max weight matching, max weight matroid independent set, etc.) have formulations as linear programs (LPs) over 0/1 polytopes on which LP solvers could be applied. However, there often exist bespoke algorithms for these problems which, by merit of being tailored to a specific domain, are both more efficient and conceptually nicer than running a generic LP solver on the associated LP. We will discuss recent results which show that a number of such algorithms (e.g. the shortest augmenting path algorithm, the greedy algorithm, etc.) can be "executed" by the Simplex method for solving LPs, in the sense that the Simplex method can be made to generate the same sequence of solutions when applied to the appropriate corresponding LP.
Tantan Dai: There has been extensive research on Latin Squares. It is simple to construct a Latin Square with n rows and n columns. But how do we define a Latin Triangle? What are the rows? When does a Latin Triangle exist? How can we construct them? In this talk, I will discuss two types of Latin Triangles and the construction of a countable family of Latin Triangles.
ReplyReply allForward
SE