Three fifteen-minute talks by local speakers.
A graph is $H$-Ramsey if every two-coloring of its edges contains a monochromatic copy of $H$. Define the $F$-Ramsey number of $H$, denoted by $r_F(H)$, to be the minimum number of copies of $F$ in a graph which is $H$-Ramsey. This generalizes the Ramsey number and size Ramsey number of a graph. Addressing a question of Spiro, we prove that \[r_{K_3}(K_t)=\binom{r(K_t)}3\] for all sufficiently large $t$.
Our proof employs many recent results on the chromatic number of locally sparse graphs. In particular, I will highlight a new result on the chromatic number of degenerate graphs, which leads to several intriguing open problems.
Three fifteen-minute talks by local speakers.
A Latin square is an nxn grid filled with n symbols such that each symbol appears exactly once in each row and column. A transversal in a Latin square is a collection of n cells such that each row, column and symbol appears exactly once in the collection.
Latin squares were introduced by Euler in the 1700s and he was interested in the question of when a Latin square decomposes fully into transversals. Equivalently, when does a Latin square have an 'orthogonal mate'?
We'll discuss the history of this question, and some upcoming joint work with Richard Montgomery.
How many different ways can we arrange n convex sets in R^d? One answer is provided by counting the number of d-representable complexes on vertex set [n]. We show that there are exp(Theta(n^d log n))-many such complexes, and provide bounds on the constants involved. As a consequence, we show that d-representable complexes comprise a vanishingly small fraction of the class of d-collapsible complexes. In the case d = 1 our results are more precise, and improve the previous best estimate for the number of interval graphs.
A hereditary class $\mathcal C$ of graphs is said to have the Erdős–Hajnal property if every $n$-vertex graph in $\mathcal C$ has a clique or stable set of size at least $n^c$. We discuss a proof of a conjecture of Chernikov–Starchenko–Thomas and Fox–Pach–Suk that for every $d\ge1$, the class of graphs of VC-dimension at most $d$ has the Erdős–Hajnal property. Joint work with Alex Scott and Paul Seymour.
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.
An edge-coloured graph is said to be rainbow if it uses no colour more than once. Extremal problems involving rainbow objects have been a focus of much research as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstraëte from 2007 asks for the maximum possible average degree of a properly edge-coloured graph on n vertices without a rainbow cycle. Improving upon a series of earlier bounds, Tomon proved an upper bound of (log n)^(2+o(1)) for this question. Very recently, Janzer-Sudakov and Kim-Lee-Liu-Tran independently removed the o(1) term in Tomon's bound. We show that the answer to the question is equal to (log n)^(1+o(1)).
Joint work with: Noga Alon, Lisa Sauermann, Dmitrii Zakharov and Or Zamir.
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
Every graph is associated to a symmetric function constructed from proper colorings of the graph. The Stanley-Stembridge conjecture posits that the expansion of the chromatic symmetric function into the elementary symmetric functions has positive coefficients for a certain class of graphs. We explore a potential new approach to the Stanley-Stembridge Conjecture using combinatorial objects called "special rim hooks" and connect this to the "chromatic quasisymmetric functions" introduced by Shareshian and Wachs as a generalization of chromatic symmetric functions. This is joint work with Meagan Hodge.
