# Topology in Combinatorics

## Tibor Szabó

Institute of Mathematics
Freie Universität Berlin

• Extremal problems for transversals in graphs with bounded degree, (with G. Tardos), Combinatorica, 26 (2006) 333-351.
There are lots of applications of topology in combinatorics and I consider here one, which is not "really" topology, there is a purely combinatorial way to say the statements, but pictures are so much nicer. The basic idea is from a paper of Aharoni and Haxell, who prove a general combinatorial theorem by constructing certain triangulations of the simplex having special properties and using them together with Sperner's Lemma to derive the combinatorial statement. This idea has later seen numerous applications and extensions by its inventors, and R. Meshulam, M. Chudnovsky, A. Kotlov, among others. Another application can be found in this paper.
Let K1(G) be the simplicial complex defined on the vertices of a graph G which contains those subsets of the vertex set V(G) which form an independent set in G. The complex K1(G), called the independent set complex of G, was investigated early and widely by numerous researchers for various reasons. One statement popping up in several of these papers concerns the connectedness of the independent set complex in terms of the maximum degree d of G. Namely, if the number n of vertices of G is greater than 2md for some integer m then K1(G) is (m-1)-connected. This statement is best possible as witnessed by the disjoint union of m complete bipartite graphs Kd,d.
In this paper we investigate the induced matching complex K2(G) consisting of those subsets of V(G) which induce a subgraph of maximum degree 1 in G. The connectedness of the induced matching complex has implications for the existence of matching transversals, which concept recently turned out to be a very applicable tool in graph theory. We prove that if n > (3/2) md then K2(G) is (m-1)-connected. We also give an example with n=(5/4) md, where (m-1)-connectedness does not follow.
Question: What is the optimal constant in front of md guaranteeing (m-1)-connectedness of K2(G)? Is it 5/4? Or 3/2? Or something between?
The more general question: What about the connectedness of the larger complex Kr(G) containing those subsets which induce a graph whose largest component is of order r? We can prove that n > (1+1/r)md implies (m-1)-connectedness of Kr(G) provided d >r-1. Is (1+1/r) the best constant multiplier?

• Dense Graphs with Cycle Neighborhoods (with Á. Seress), Journal of Combinatorial Theory (Series B), 63 (1995) 281-293.
The graphs constructed in this paper using finite fields have some implications in topological graph theory. Hartsfield and Ringel defined the notion of clean triangulation of a surface by requiring that all faces are triangles and all triangles of the embedded graph is a face. They provided triangulations of genus g surfaces having (4+o(1))g faces. This is equivalent to saying that n=o(e) for the number n of vertices and e of edges of the embedded graph G, so their graphs are dense in the sense that the number of edges is nonlinear. Here we construct graphs whose minimum genus embedding is a clean triangulation and they have n2-o(1) edges, i.e., they are essentially as dense as possible. (Clean triangulations cannot have quadratically many edges because of the famous (6,3)-theorem of Ruzsa and Szemerédi.)