Atlantic Graph Theory Seminar
January 22, 2025 @ 3:30 pm - 4:30 pm
Ramsey numbers of signed graphs
Ben Seamone, Dawson College and Université de Montréal
Abstract:
Nathan Acheampong (Université de Montréal) Francis Clavette (Université de Montréal)
Geˇna Hahn (Université de Montréal) Margaux Marseloo (Université Paris-Saclay) Viktor
Paardekooper (Université de Montréal), and Ben Seamone* (Dawson College & Université de Montréal)
A signed graph is a pair (G, σ) where G = (V,E) is a graph and σ : E(G) → {+, −} is
a signature which assigns a sign to each edge of G. One well-studied operation on signed
graphs is that of switching at a vertex v ∈ V (G), by which we mean that every edge incident
to v has its sign changed. Two signed graphs are called equivalent if one can be obtained
from the other by a sequence of vertex switches.
We call a complete signed graph positive (negative) if every edge is positive (negative). We
study the following Ramsey problem on signed graphs – for positive integers s and t, what
is the smallest n such that every signed complete graph on n vertices has an equivalent
signed complete graph containing either a negative Ks or positive Kt? This “signed Ramsey
number” is denoted r±(s, t). We show how a variety of approaches lead to upper and lower
bounds on r±(s, t), settle an open problem by establishing the exact value of r±(4, t) for
every t, and determine the asymptotics of r±(5, t) and r±(6, t).
Zoom link:
Meeting ID: 868 6149 9971
Passcode: 325258