-
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.)
Last modified: Sun Jun 30 22:55:22 CEST 2013