# DIMACS Discrete Mathematics Seminar

## Title:

The rank of the intersection of free groups and a conjecture in graph theory

## Speaker:

- Gabor Tardos
- Mathematical Institute of Hungary

## Place:

- CoRE Building, Room 431
- Busch Campus, Rutgers University

## Time:

- 4:30 PM
- Tuesday, September 19, 1995

## Abstract:

The talk is on partial results about a graph-theoretic conjecture that is
equivalent to the 40 year old Hanna Neumann Conjecture on the intersection
of free groups.
By the Nielsen-Schreier theorem any subgroup of a free group is free. Let
us take two subgroups of a free group now. Clearly both of them and also
the intersection is free and therefore characterised up to isomorphism by
their rank (number of free generators). Suppose the two subgroups have
finite ranks k+1 and l+1 what can be the rank of the intersection. Hanna
Neumann conjectured that kl+1 is an upper bound but was only able to prove
that the rank is at most 2kl+1. This upper bound has been hardly improved
since.

While connection to graph theory was noted earlier, W. Dicks has recently
proved that the following Amalgamated Graph Conjecture is equivalent to
a strengthened form the Hanna Neumann Conjecture.

By graph we mean two-colored simple bipartite graphs, that is the
two-coloring is also given with the graph and oppositely colored graphs are
not considered isomorphic (unless they are symmetric).

The Amalgamated Graph Conjecture states:

Let us take three graphs G_1, G_2 and G_3, such that
G_1 \cap G_2 = G_2 \cap G_3
= G_3 \cap G_1 = G and suppose that the connected components of the three
graphs G_1 \cup G_2 and G_2 \cup G_3 and G_3 \cup G_1 are isomorphic in
pairs. The conjecture states that in this case G has at most half as many
edges "as it could have" i.e. the number of edges is at most
half the product of the number of vertices on one side times the number
of vertices on the other side.

In the talk I will focus on the special cases of the conjecture solved and
time permits, I will sketch the equivalence to the group theoretic question
as well.

dimacs-www@dimacs.rutgers.edu
Document last modified on September 15, 1995