You are currently browsing the tag archive for the ‘graphs’ tag.

### Recent Posts

- kleinian, a tool for visualizing Kleinian groups
- Kähler manifolds and groups, part 2
- Kähler manifolds and groups, part 1
- Liouville illiouminated
- Scharlemann on Schoenflies
- You can solve the cube – with commutators!
- Chiral subsurface projection, asymmetric metrics and quasimorphisms
- Random groups contain surface subgroups
- wireframe, a tool for drawing surfaces
- Cube complexes, Reidemeister 3, zonohedra and the missing 8th region
- Orthocentricity
- Kenyon’s squarespirals
- Thurston talks on geometrization at Harvard
- Random turtles in the hyperbolic plane
- Surface subgroups of Sapir’s group
- Upper curvature bounds and CAT(K)
- Bill Thurston 1946-2012
- Circle packing – theory and practice
- Agol’s Virtual Haken Theorem (part 3): return of the hierarchies
- Agol’s Virtual Haken Theorem (part 2): Agol-Groves-Manning strike back
- Agol’s Virtual Haken Theorem (part 1)
- Characteristic classes of foliations
- Filling geodesics and hyperbolic complements
- Quasigeodesic flows on hyperbolic 3-manifolds
- Laying train tracks

### Blogroll

- Area 777
- Combinatorics and more
- Deep street soul
- Evaluating E-Discovery
- floerhomology
- Gaddeswarup
- Geometric Group Theory
- Godel's lost letter and P=NP
- Images des mathematiques
- Jim Woodring
- Language Log
- Letters of note
- Low dimensional topology
- Math Overflow
- Mathematics under the microscope
- n-Category Cafe
- Noncommutative geometry
- Paul Krugman
- Persiflage
- Preposterous Universe
- Questionable content
- Quomodocumque
- Scott McCloud
- Secret blogging seminar
- Sketches of topology
- Terry Tao
- Tim Gowers
- Tony Phillips

### Software

### Recent Comments

Ian Agol on Cube complexes, Reidemeister 3… | |

Danny Calegari on kleinian, a tool for visualizi… | |

Quod est Absurdum |… on kleinian, a tool for visualizi… | |

dipankar on kleinian, a tool for visualizi… | |

Ludwig Bach on Liouville illiouminated |

### Archives

- March 2014 (1)
- November 2013 (2)
- October 2013 (2)
- August 2013 (1)
- June 2013 (1)
- April 2013 (1)
- February 2013 (1)
- January 2013 (3)
- December 2012 (2)
- November 2012 (1)
- October 2012 (1)
- August 2012 (2)
- March 2012 (3)
- February 2012 (2)
- December 2011 (2)
- November 2011 (1)
- October 2011 (2)
- August 2011 (1)
- May 2010 (1)
- April 2010 (4)
- December 2009 (3)
- November 2009 (4)
- October 2009 (4)
- September 2009 (4)
- August 2009 (5)
- July 2009 (5)
- June 2009 (8)
- May 2009 (4)

### Categories

- 3-manifolds (14)
- 4-manifolds (2)
- Algebraic Geometry (2)
- Biology (2)
- Commentary (4)
- Complex analysis (7)
- Convex geometry (2)
- Diophantine approximation (1)
- Dynamics (9)
- Ergodic Theory (8)
- Euclidean Geometry (8)
- Foliations (1)
- Geometric structures (5)
- Groups (28)
- Hyperbolic geometry (18)
- Knot theory (1)
- Lie groups (8)
- Overview (2)
- Polyhedra (2)
- Probability (1)
- Projective geometry (1)
- Psychology (2)
- Rigidity (2)
- Special functions (1)
- Surfaces (18)
- Symplectic geometry (2)
- TQFT (1)
- Uncategorized (4)
- Visualization (9)

## The (strengthened) Hanna Neumann Conjecture

May 29, 2009 in Commentary, Groups | Tags: free groups, graphs, Hanna Neumann Conjecture | by Danny Calegari | 1 comment

A few days ago, Joel Friedman posted a paper on the arXiv purporting to give a proof of the (strengthened) Hanna Neumann conjecture, a well-known problem in geometric group theory.

Simply stated, the problem is as follows.

Conjecture(Hanna Neumann): Let be a free group, and let and be finitely generated subgroups. For a subgroup of , let . Then there is an inequality .This conjecture was further strengthened by Walter Neumann (her son):

Conjecture(strengthened Hanna Neumann): With notation above, there is an inequality where the sum is taken over , i.e. the double coset representatives.Notice by the way that since any free group embeds into , the free group of rank , one can assume that has rank above. This fact is implicit in the discussion below.

Friedman’s paper seems to be very carefully written, and contains some new ideas (which I do not yet really understand), namely an approach using sheaf theory. But in this post I want to restrict myself to some simple (and probably well-known) geometric observations.

The first step is to reduce the problem to a completely graph-theoretic one, following Stallings; in fact, Benson Farb tells me that he thinks this reduction was known to Stallings, or at least to Dicks/Formanek (and in any case is very close to some ideas Stallings and Gersten introduced to study the problem; more on that in a later post). Friedman makes the following definition:

Definition: Let be a finite group and be two elements (that do not necessarily generate ). The directed Cayley graph is the graph with vertex set and with a directed edge from to labeled for each and .In other words, is a graph whose edges are oriented and labeled with either or in such a way that each vertex has at most one outgoing and one incoming edge with each label, and such that there is a transitive (on the vertices) free action of a group on . (Note: for some reason, Friedman wants his group to act on the right, and therefore has directed edges from to , but this is just a matter of convention).

For any finite graph , not necessarily connected, let ; i.e. where the sum is taken over the connected components of . Friedman shows (but this reduction is well-known) that the SHNC is equivalent to the following graph-theoretic inequality:

Theorem: The SHNC is equivalent to the following statement. For any graph as above, and any two subgraphs we have .The purpose of this blog entry is to show that there is a very simple proof of this inequality when is replaced with . This is not such a strange thing to do, since and are equal for graphs without acyclic components (i.e. without components that are trees), and for “random” graphs one does not expect the difference between and to be very big. The argument proceeds as follows. Suppose has vertices and edges of kind respectively, and define similarly for . Then

On the other hand, since Euler characteristic is

local, we just need to count how many vertices and edges of each kind turn up in each . But this is easy: every vertex of is equal to exactly one translate of every vertex of , and similarly for edges of each kind. HenceSo the inequality one wants to show is which simplifies to

On the other hand, each graph has at most two edges at any vertex with either label, and therefore we have inequalities . Subject to these constraints, the inequality above is straightforward to prove. To see this, first fix some non-negative values of and let be the four-dimensional cube of possible values of . Since both sides of the inequality are

linearas a function of each or , if the inequality is violated at any point in one may draw a straight line in corresponding to varying one of the co-ordinates (e.g. ) while keeping the others fixed, and deduce that the inequality must be violated on one of the faces of . Inductively, if the inequality is violated at all, it is violated at a vertex of , which may be ruled out by inspection; qed.This argument shows that the whole game is to understand the

acycliccomponents of ; i.e. those which are topologically trees, and therefore contribute to , but to .Incidentally, for all I know, this simple argument is explicitly contained in either Stallings’ or Gersten’s paper (it is surely not original in any case). If a reader can verify this, please let me know!

Update: Walter Neumann informs me that this observation (that the inequality is true with in place of ) is in his paper in which he introduces the SHNC! He further shows in that paper that for “most” , the SHNC is true for all .Update (6/29):Warren Dicks informs me that he was not aware of the reduction of SHNC to the graph-theoretic formulation described above. Friedman’s webpage acknowledges the existence of an error in the paper, and says that he is working to correct it. One problem that I know of (discovered mostly by my student Steven Frankel) concerns the commutativity of the diagram on page 10.Update (10/22):It has been a few months since I last edited this page, and Joel Friedman has not updated either the arXiv paper, or the statement on his webpage that he is “trying to fix the error”. Since wikipedia mentions Friedman’s announcement, I thought it would be worth going on record at this point to say that Friedman’s arXiv paper (version 1 — the only version at the point I write this) is definitely in error, and that I believe the error is fundamental, and cannot be repaired (this is not to say that the paper does not contain some things of interest (it does), or that Friedman does not acknowledge the error (he does), just that it is worth clearing up any possible ambiguity about the situation for readers who are wondering about the status of the SHNC). The problem is the “not entirely standard” (quote from Friedman’s paper) diagrams, like the one on page 10. In particular, the claimed proof of Theorem 5.6, that the projections constructed in Lemma 5.5 (by a very general dimension counting argument) fit into a diagram with the desired properties is false. Any construction of projections satisfying the desired properties must be quite special. Nevertheless, one can certainly still define Friedman’s sheaf , and ask whether it has (in Friedman’s sense); this would, as far as I can tell, prove SHNC; however, I do not know of any reason why it should hold (or whether there are any counterexamples, which might exist even if SHNC is true).