A polynomial Ramsey statement for bounded VC-dimension

11^th March 2025, 13:00 ELEC204, 2th Floor Lecture Theatre EEE
Tomáš Hons
Charles University, Prague

Abstract

Zoom link: https://liverpool-ac-uk.zoom.us/j/98935123903?pwd=SaYbdu6qHaNPqbJbdVb3hVDBRnIgPy.1
Meeting ID: 989 3512 3903
Passcode: CSLiver#1

A theorem by Ding, Oporowski, Oxley, and Vertigan states that every sufficiently large bipartite graph without twins contains a matching, co-matching, or half-graph of arbitrary size as an induced subgraph. We prove that this Ramsey statement has polynomial dependency assuming bounded VC-dimension of the initial graph, using the recent verification of the Erd\H{o}s-Hajnal property for graphs of bounded VC-dimension. Since the theorem of Ding et al. plays a role in (finite) model theory, which deals with even more restricted structures, we also comment on its further refinements in this context.

Biography

Guoli Ding, Bogdan Oporowski, James Oxley, and Dirk Vertigan. “Unavoidable Minors of
Large 3-Connected Binary Matroids”. In: Journal of Combinatorial Theory, Series B 66.2
(Mar. 1996), pp. 334–360. issn: 0095-8956. doi: 10.1006/jctb.1996.0026.

Tung Nguyen, Alex Scott, and Paul Seymour. “Induced subgraph density. VI. Bounded
VC-dimension”. In: (2023). doi: 10.48550/ARXIV.2312.15572.

Additional Materials

• https://arxiv.org/abs/2502.20461