Georgia Institute of Technology College of Sciences

 The classical Borsuk--Ulam theorem states that for any continuous map  from the sphere to Euclidean space, $f\colon S^d\to R^d$, there is a pair of antipodal points that are identified, so $f(x)=f(-x)$. We prove a colorful generalization of the Borsuk–Ulam theorem. The classical result has many applications and consequences for combinatorics and discrete geometry and we in turn prove colorful generalizations of these consequences such as the colorful ham sandwich theorem, which allows us to prove a recent result of B\'{a}r\'{a}ny, Hubard, and Jer\'{o}nimo on well-separated measures as a special case, and Brouwer's fixed point theorem, which allows us to prove an alternative between KKM-covering results and Radon partition results.  This is joint work with Florian Frick.

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.

ReplyReply allForward

SE

The notion of $S$-labeling, where $S$ is a subset of the symmetric group, is a common generalization of signed $k$-coloring, signed $\mathbb{Z}_k$-coloring, DP (or Correspondence) coloring, group coloring, and coloring of gained graphs that was introduced in 2019 by Jin, Wong, and Zhu.  In this talk we use a well-known theorem of  Alon and F\"{u}redi to present an algebraic technique for bounding the number of colorings of an $S$-labeled graph from below.  While applicable in the broad context of counting colorings of $S$-labeled graphs, we will focus on the case where $S$ is a symmetric group, which corresponds to DP-coloring (or, correspondence coloring) of graphs, and the case where $S$ is a set of linear permutations which is applicable to the coloring of signed graphs, etc.

This technique allows us to prove exponential lower bounds on the number of colorings of any $S$-labeling of graphs that satisfy certain sparsity conditions. We apply these to give exponential lower bounds on the number of DP-colorings (and consequently, number of  list colorings, or usual colorings) of families of planar graphs, and on the number of colorings of families of signed (planar) graphs. These lower bounds either improve previously known results, or are first known such results.

This joint work with Samantha Dahlberg and Jeffrey Mudrock.

I will give an overview of recent work, joint with Jacques Verstraete, where we gave an improved lower bound for the off-diagonal Ramsey number $r(4,t)$, solving a long-standing conjecture of Erd\H{o}s. Our proof has a strong non-probabilistic component, in contrast to previous work. This approach was generalized in further work with David Conlon, Dhruv Mubayi and Jacques Verstraete to off-diagonal Ramsey numbers $r(H,t)$ for any fixed graph $H$. We will go over of the main ideas of these proofs and indicate some open problems.