This event has passed.
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, 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)
Abstract: 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:
https://us02web.zoom.us/j/86861499971?pwd=rTDAaju0TCu24asnaBGvkuNlT11KZ1.1
Meeting ID: 868 6149 9971
Passcode: 325258