Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269: Seminar in Combinatorics

Prof. Yi Zhao

Georgia State University (yzhao6@gsu.edu)

Extremal results in multipartite graphs

Abstract:

Classical extremal results in graph theory (such as Turán's theorem) concern the maximal size of of a graph of given order and without certain subgraphs. Bollobás, Erdős, and Szemerédi in 1975 studied extremal problems in multipartite graphs. One of their problems (in its complementary form) was determining the maximal degree of a multipartite graph without an independent transversal. This problem has received considerable attention and was settle in 2006 (Szabó--Tardos and Haxell--Szabó). Other questions asked by Bollobás, Erdős, and Szemerédi remain open, such as determining:

(1) the maximum degree in a multipartite graph without a partial independent transversal, and;
(2) the minimum degree that forces an octahedral graph in balanced tripartite graphs.

In this talk I will survey recent progress on these and other related problems.

Lutz Warnke

November 26, 2024

2:00 PM

APM 7321

****************************