# Cayley graphs and the geometry of groups

10 July, 2010 in expository, math.CO, math.GR | Tags: Cayley graphs, fibre bundles, normal subgroups, semi-direct products

What’s new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

10 July, 2010 in expository, math.CO, math.GR | Tags: Cayley graphs, fibre bundles, normal subgroups, semi-direct products

- Gene Weingarten – Pearls before breakfast
- Isaac Asimov – The relativity of wrong
- Jonah Lehrer – Don't! – the secret of self-control
- Julianne Dalcanton – The cult of genius
- Nassim Taleb – The fourth quadrant: a map of the limits of statistics
- Paul Graham – What You'll Wish You'd Known
- Po Bronson – How not to talk to your kids
- Scott Aaronson – Ten signs a claimed mathematical proof is wrong
- Timothy Gowers – Elsevier — my part in its downfall
- Timothy Gowers – The two cultures of mathematics
- William Thurston – On proof and progress in mathematics

- Abstruse Goose
- Assembler
- BoxCar2D
- Factcheck.org
- FiveThirtyEight
- Gapminder
- Literally Unbelievable
- Planarity
- PolitiFact
- Quite Interesting
- snopes
- Strange maps
- Television tropes and idioms
- The Daily Show with Jon Stewart
- The Economist
- The Onion
- The Straight Dope
- This American Life on the financial crisis I
- This American Life on the financial crisis II
- What if? (xkcd)
- White whine
- xkcd

- 0xDE
- A Mind for Madness
- A Portion of the Book
- Absolutely useless
- Alex Sisto
- AMS blogs
- AMS Graduate Student Blog
- Analysis & PDE
- Analysis & PDE Conferences
- Annoying Precision
- Area 777
- Ars Mathematica
- ATLAS of Finite Group Representations
- Automorphic forum
- Avzel's journal
- Blog on Math Blogs
- Blog On Mathematical Journals
- blogderbeweise
- Bubbles Bad; Ripples Good
- Cédric Villani
- Climbing Mount Bourbaki
- Coloquio Oleis
- Combinatorics and more
- Compressed sensing resources
- Computational Complexity
- Concrete nonsense
- David Mumford's blog
- Delta epsilons
- DispersiveWiki
- Disquisitiones Mathematicae
- Embûches tissues
- Emmanuel Kowalski’s blog
- Encyclopedia of Mathematics
- Equatorial Mathematics
- fff
- Floer Homology
- Frank Morgan’s blog
- Gérard Besson's Blog
- Gödel’s Lost Letter and P=NP
- Geometric Group Theory
- Geometry and the imagination
- Geometry Bulletin Board
- Girl's Angle
- God Plays Dice
- Good Math, Bad Math
- Graduated Understanding
- Hydrobates
- I Woke Up In A Strange Place
- Igor Pak's blog
- Images des mathématiques
- In theory
- James Colliander's Blog
- Jérôme Buzzi’s Mathematical Ramblings
- Joel David Hamkins
- Journal of the American Mathematical Society
- Kill Math
- Le Petit Chercheur Illustré
- Lemma Meringue
- Lewko's blog
- Libres pensées d’un mathématicien ordinaire
- LMFDB – L-functions and modular forms database
- LMS blogs page
- London number theory
- Low Dimensional Topology
- M-Phi
- MAA MinuteMath
- Math Overflow
- Mathbabe
- Mathblogging
- Mathematical musings
- Mathematics Illuminated
- Mathematics in Australia
- Mathematics Jobs Wiki
- Mathematics Stack Exchange
- Mathematics under the Microscope
- Mathlog
- MathOnline
- Mathtube
- Matt Baker's Math Blog
- Mixedmath
- Motivic stuff
- Much ado about nothing
- Multiple Choice Quiz Wiki
- neverendingbooks
- nLab
- Noncommutative geometry blog
- Nonlocal equations wiki
- Not "Not Even Wrong"
- Nuit-blanche
- Number theory web
- outofprintmath
- PDE blog
- Pengfei Zhang's blog
- Peter Cameron's Blog
- Phillipe LeFloch's blog
- ProofWiki
- Quomodocumque
- Random Math
- Reasonable Deviations
- Regularize
- Rigorous Trivialities
- Roots of unity
- Secret Blogging Seminar
- Selected Papers Network
- Sergei Denisov's blog
- Shtetl-Optimized
- Shuanglin's Blog
- Since it is not…
- Sketches of topology
- Soft questions
- Stacks Project Blog
- SymOmega
- tcs math
- TeX, LaTeX, and friends
- The accidental mathematician
- The capacity to be alone
- The Cost of Knowledge
- The Everything Seminar
- The Geomblog
- The Mathematics Literature Project
- The n-Category Café
- The n-geometry cafe
- The On-Line Blog of Integer Sequences
- The polylogblog
- The polymath blog
- The polymath wiki
- The Tricki
- The twofold gaze
- The Unapologetic Mathematician
- The value of the variable
- The World Digital Mathematical Library
- Theoretical Computer Science – StackExchange
- Tim Gowers’ blog
- Tim Gowers’ mathematical discussions
- Todd and Vishal’s blog
- Van Vu's blog
- Vaughn Climenhaga
- Vieux Girondin
- Visual Insight
- Vivatsgasse 7
- Williams College Math/Stat Blog
- Windows on Theory
- Wiskundemeisjes
- XOR’s hammer
- Zhenghe's Blog

- A cheap version of nonstandard analysis
- A review of probability theory
- American Academy of Arts and Sciences speech
- Amplification, arbitrage, and the tensor power trick
- An airport-inspired puzzle
- Benford's law, Zipf's law, and the Pareto distribution
- Compressed sensing and single-pixel cameras
- Einstein’s derivation of E=mc^2
- On multiple choice questions in mathematics
- Quantum mechanics and Tomb Raider
- Real analysis problem solving strategies
- Sailing into the wind, or faster than the wind
- Simons lectures on structure and randomness
- Small samples, and the margin of error
- Soft analysis, hard analysis, and the finite convergence principle
- The blue-eyed islanders puzzle
- The cosmic distance ladder
- The federal budget, rescaled
- Ultrafilters, non-standard analysis, and epsilon management
- What is a gauge?
- What is good mathematics?
- Why global regularity for Navier-Stokes is hard

- Career advice
- There’s more to mathematics than rigour and proofs
- Does one have to be a genius to do maths?
- The Euler-Maclaurin formula, Bernoulli numbers, the zeta function, and real-variable analytic continuation
- Failure of the L^1 pointwise and maximal ergodic theorems for the free group
- On writing
- A remark on the lonely runner conjecture
- Books
- The blue-eyed islanders puzzle
- About

- May 2015 (3)
- April 2015 (4)
- March 2015 (3)
- February 2015 (4)
- January 2015 (4)
- December 2014 (6)
- November 2014 (5)
- October 2014 (4)
- September 2014 (3)
- August 2014 (4)
- July 2014 (5)
- June 2014 (5)
- May 2014 (5)
- April 2014 (2)
- March 2014 (4)
- February 2014 (5)
- January 2014 (4)
- December 2013 (4)
- November 2013 (5)
- October 2013 (4)
- September 2013 (5)
- August 2013 (1)
- July 2013 (7)
- June 2013 (12)
- May 2013 (4)
- April 2013 (2)
- March 2013 (2)
- February 2013 (6)
- January 2013 (1)
- December 2012 (4)
- November 2012 (7)
- October 2012 (6)
- September 2012 (4)
- August 2012 (3)
- July 2012 (4)
- June 2012 (3)
- May 2012 (3)
- April 2012 (4)
- March 2012 (5)
- February 2012 (5)
- January 2012 (4)
- December 2011 (8)
- November 2011 (8)
- October 2011 (7)
- September 2011 (6)
- August 2011 (8)
- July 2011 (9)
- June 2011 (8)
- May 2011 (11)
- April 2011 (3)
- March 2011 (10)
- February 2011 (3)
- January 2011 (5)
- December 2010 (5)
- November 2010 (6)
- October 2010 (9)
- September 2010 (9)
- August 2010 (3)
- July 2010 (4)
- June 2010 (8)
- May 2010 (8)
- April 2010 (8)
- March 2010 (8)
- February 2010 (10)
- January 2010 (12)
- December 2009 (11)
- November 2009 (8)
- October 2009 (15)
- September 2009 (6)
- August 2009 (13)
- July 2009 (10)
- June 2009 (11)
- May 2009 (9)
- April 2009 (11)
- March 2009 (14)
- February 2009 (13)
- January 2009 (18)
- December 2008 (8)
- November 2008 (9)
- October 2008 (10)
- September 2008 (5)
- August 2008 (6)
- July 2008 (7)
- June 2008 (8)
- May 2008 (11)
- April 2008 (12)
- March 2008 (12)
- February 2008 (13)
- January 2008 (17)
- December 2007 (10)
- November 2007 (9)
- October 2007 (9)
- September 2007 (7)
- August 2007 (9)
- July 2007 (9)
- June 2007 (6)
- May 2007 (10)
- April 2007 (11)
- March 2007 (9)
- February 2007 (4)

- expository (219)
- tricks (8)

- guest blog (9)
- Mathematics (613)
- math.AC (5)
- math.AG (37)
- math.AP (83)
- math.AT (15)
- math.CA (120)
- math.CO (142)
- math.CT (6)
- math.CV (13)
- math.DG (32)
- math.DS (65)
- math.FA (22)
- math.GM (9)
- math.GN (21)
- math.GR (77)
- math.GT (12)
- math.HO (9)
- math.IT (8)
- math.LO (46)
- math.MG (34)
- math.MP (25)
- math.NA (12)
- math.NT (114)
- math.OA (17)
- math.PR (78)
- math.QA (5)
- math.RA (24)
- math.RT (21)
- math.SG (4)
- math.SP (44)
- math.ST (4)

- non-technical (119)
- admin (41)
- advertising (16)
- diversions (4)
- media (11)
- journals (2)

- obituary (8)

- opinion (27)
- paper (156)
- question (96)
- polymath (68)

- talk (62)
- DLS (19)

- teaching (142)
- 245A – Real analysis (11)
- 245B – Real analysis (19)
- 245C – Real analysis (6)
- 254A – analytic prime number theory (16)
- 254A – ergodic theory (18)
- 254A – Hilbert's fifth problem (12)
- 254A – random matrices (14)
- 254B – expansion in groups (8)
- 254B – Higher order Fourier analysis (9)
- 285G – poincare conjecture (20)
- Logic reading seminar (8)

- travel (25)
- Uncategorized (1)

- An error has occurred; the feed is probably down. Try again later.

additive combinatorics
almost orthogonality
approximate groups
arithmetic progressions
Ben Green
Cauchy-Schwarz
Cayley graphs
characters
circular law
compactness
compressed sensing
concentration compactness
correspondence principle
eigenvalues
Elias Stein
Emmanuel Breuillard
entropy
equidistribution
ergodic theory
expander graphs
exponential sums
finite fields
Fourier transform
Four Moment Theorem
Freiman's theorem
Gowers uniformity norms
gradient shrinking solitons
graph theory
Gromov's theorem
GUE
Hilbert's fifth problem
hypergraphs
inverse conjecture
Kakeya conjecture
Lie algebras
Lie groups
Littlewood-Offord problem
Mobius function
multiple recurrence
Navier-Stokes equations
nilpotent groups
NLS
nonstandard analysis
parity problem
politics
polymath1
polymath8
polynomial method
polynomials
prime numbers
prime number theorem
project heatwave
random matrices
randomness
random walks
Ratner's theorem
regularity lemma
Ricci flow
Riemann zeta function
Schrodinger equation
Selberg sieve
sieve theory
spectral theorem
structure
Szemeredi's theorem
szemeredi regularity lemma
Tamar Ziegler
ultrafilters
ultraproducts
universality
Van Vu
wave maps
Weil conjectures
Wigner matrices
Yitang Zhang

- Two polymath (of a sort) proposed projects 20 January, 2014
- Polymath9: P=NP? (The Discretized Borel Determinacy Approach) 4 November, 2013
- Polymath8 – A Success ! 20 September, 2013
- Polymath7 research thread 5: the hot spots conjecture 9 August, 2013
- Polymath proposal: bounded gaps between primes 4 June, 2013
- Polymath proposal (Tim Gowers): Randomized Parallel Sorting Algorithm 2 March, 2013
- Next Polymath Project(s): What, When, Where? 14 February, 2013
- Polymath7 research threads 4: the Hot Spots Conjecture 10 September, 2012
- Minipolymath4 project, second research thread 13 July, 2012
- Minipolymath4 project: IMO 2012 Q3 12 July, 2012

- Save pure mathematics at the VU University of Amsterdam 30 April, 2011
- ERA results for mathematical sciences in Australia 15 February, 2011
- Junior positions at ANU 8 November, 2010
- AustMS now on twitter 10 October, 2010
- Research not bad, but not stellar 9 May, 2010
- L’Oréal Australia For Women In Science Fellowships 11 April, 2010
- Postdoctoral position (Level A) in mathematics at Australian National University 18 January, 2010
- Cheryl Praeger named as 2009 Western Australian Scientist of the Year 2 December, 2009
- Positions at Australian National University 4 November, 2009
- Mathematics skills out for the count 26 October, 2009

To enter in LaTeX in comments, use $latex *<Your LaTeX code>*$ (without the < and > signs, of course; in fact, these signs should be avoided as they can cause formatting errors). See the about page for details and for other commenting policy.

%d bloggers like this:

## 38 comments

Comments feed for this article

10 July, 2010 at 4:27 pm

Andrew L.First off, I LOVE these “by the way” lecture posts of yours,Professor Tao. They’re a great resource for the entire mathematical community. It’s very comforting to know there’s a top notch researcher who seems just as passionate about teaching as you are. Keep up the great work.

The serious study of the geometric properties of groups and thier associated graph embeddings in Euclidean spaces-which was initiated by Klein and developed by so many great mathematicians,most notably Wilhelm Magnus and his students-is a fantasticaly rich topic that isn’t incorporated into traditional courses in algebra and geometry anywhere near as fully as it should be. The classic introduction is of course, GRAPHS AND THIER GROUPS by Grossman and Magnus. A much more advanced text that covers the graph theoretic aspects-including the deeper topological properties of the Cayley graph and it’s fundamental group structure touched on in your post-can be found in GRAPHS OF GROUPS ON SURFACES by Arthur T.White,currently in it’s 3rd edition.

Again,thanks for the great introduction to such an important topic.

10 July, 2010 at 5:26 pm

TheoIt’s a well-known fact that a connected topological group is generated by any open neighborhood of its identity element. (So it is tempting to think of a Lie group as _generated_ by its Lie algebra, after identifying the Lie algebra with an infinitesimal neighborhood of the identity. This is reasonable in models of mathematics where infinite numbers really exist. Moreover, the Baker-Campbell-Hausdorff series identifies the Lie algebra with the formal group, and over the BCH series converges for finite-dimensional Lie algebras in a non-trivial neighborhood of the origin, and so you really can identity a neighborhood of the Lie algebra with a neighborhood of the Lie group.) So it is tempting to take some sort of “formal neighborhood” of the identity element as my generating set . Can I then think of the topology on $G$ as coming from some sort of “formal Cayley graph”? Maybe I will ask this over on MathOverflow.

10 July, 2010 at 9:04 pm

Terence TaoYes, one can view topological groups and Lie groups as being continuous analogues of generated groups, and indeed a significant portion of geometric group theory is devoted to viewing the former as asymptotic limits of the latter (e.g. Gromov’s original proof of Gromov’s theorem on groups of polynomial growth definitely falls into this category). The literature on Hilbert’s fifth problem (which, roughly speaking, asks whether all locally compact topological groups come from Lie groups) don’t explicitly use Cayley graphs, but it seems to be lurking beneath the surface (particularly with those solutions to that problem that use nonstandard analysis).

10 July, 2010 at 7:52 pm

JairFascinating stuff. I didn’t realize that groups were so closely connected with certain graphs. Thanks for posting this.

10 July, 2010 at 9:36 pm

alexI like the commonsense explanation of normal groups that comes out of this presentation. By contrast, the usual definition ( g n g^{-1} \in G) is unintuitive despite its simplicity.

11 July, 2010 at 5:04 am

John ArmstrongSo a Cayley graph is not associated with a group, but with a presented group. It’d be nice to have something that only depended on the group itself, and not the presentation. (And yes, I do know where this goes…)

12 July, 2010 at 7:48 am

Terence TaoTo be utterly pedantic, a presented group is a slightly richer object than a generated group (which, in turn, is richer than a raw group); a presented group is a group with a distinguished set of generating elements and a distinguished set of generating relations, whereas a generated group only has the former and not the latter. (So there are forgetful functors from the category of presented groups to the category of generated groups to the category of groups.) Cayley graphs are more naturally associated with generated groups than with presented groups.

In the case of infinite finitely generated groups, changing the choice of generators only affects the word metric by a bilipschitz distortion. As such, the asymptotic (coarse) geometry of the finitely generated group does not depend on the choice of generators (e.g. the concept of a finitely generated group of polynomial growth does not depend on the choice of generators). Much of geometric group theory focuses on this asymptotic geometry and so indeed one can focus primarily on groups themselves rather than on generated groups. However, if one wants to work more quantitatively and non-asymptotically (and specifically, if one wants to talk about results that are non-trivial even for finite groups) then the choice of generators becomes more important. For instance, as discussed above, a cyclic group can look one-dimensional, two-dimensional, or many-dimensional at various scales, depending on how many generators one selects and how commensurate they are to each other.

11 July, 2010 at 10:00 am

Anonymoustypo in the second paragraph: $y = s_1^{\epsilon_1} \ldots s_m^{\epsilon_m} y$ should be $y = s_1^{\epsilon_1} \ldots s_m^{\epsilon_m} x$. Thanks for the post.

[Corrected, thanks – T.]12 July, 2010 at 1:35 pm

AnonymousCould you elaborate on the third property (Homogeneity) of the Cayley Graph?

Is this saying that there aren’t two paths between x and y of the same color and direction along each step?

Thanks.

15 July, 2010 at 9:08 am

Terence TaoNo, this is already a consequence of the regularity hypothesis.

One way to view homogeneity is that it asserts that any graph theoretic statement that is true if one uses x as a starting vertex, is also true if one uses y as a starting vertex, so that all vertices “look the same” from a graph theoretic perspective. For instance, in the Z/9Z graph, no matter where one starts from, the operation of following three blue arrows is always equal to following one red arrow. If three blues equaled a red for one starting vertex x but not for another y, then the graph would not be homogeneous.

The formal definition of homogeneity requires the notion of a graph isomorphism,

http://en.wikipedia.org/wiki/Graph_isomorphism

12 July, 2010 at 10:47 pm

Artem«Latex path not specified» in place of several formulas. About eight hours ago everything was OK.

Thanks for interesting post!

15 July, 2010 at 9:30 am

AnonymousI am pleased by this post, and I would like to understand better why the group properties discussed here are geometric?

Is it because they are (geo)metric? But it’s a word metric, why isn’t it algebraic?

The notion of ‘ball’ is not geometric either. Is ‘(polynomial) growth’ a geometric concept? you just count how many words there are of length 1,2,3,.. in your generated group.

That a group is abelian is visible from a multiplication table (anyway visualisation of Cayley graphs is restricted to ‘small’ groups).

“Nevertheless the geometric intuition that subgroups are analogous to foliations is still quite a good one.”

It would be interesting to know how it could help. Why is it really geometric? The notion of ‘metric’ is not engaged here. Is it geometric because it is visualised and explained by means of symbolism embedded in Euclidean plain? Yes, this method is used in geometry, but not only in geometry, in analysis, for example, too.

The fact that “one can view topological groups and Lie groups as being continuous analogues of generated groups” gives another view on group but does not add geometric properties, it seems to me. please, tell me if I am wrong.

15 July, 2010 at 10:04 am

Terence TaoGroups are both algebraic objects and geometric objects; it is not a dichotomy.

While metric geometry is certainly an important component of modern geometry, metrics are certainly not the only geometric objects of study. Riemannian geometry, for instance, is definitely very much concerned with volumes of balls, among other things. Differential geometry and its relatives (e.g. contact geometry) is similarly quite concerned with foliations, bundles, and connections. Kleinian geometry focuses on the notion of symmetry, which is very much a group-theoretic concept also. (The classical Euclidean geometry of points, lines, and planes can be viewed as a special case of all of the above modern types of geometry.)

Traditionally, geometry has focused mostly on continuous structures, but nowadays discrete geometries are also an important area of study, and Cayley graphs form a basic example of such.

16 July, 2010 at 6:23 am

AnonymousIs it not a dichotomy in the sense that groups have algebraic and geometric properties or in the sense, the same properties of groups can be seen as algebraic and as geometric properties? or are there properties of groups which are certainly geometric but not algebraic? Because what is ‘geometric’ at the first glance, seems to be perfectly algebraic: e.g. metric, hyperbolicity can be formulated algebraically, Cayley graphs -aren’t they algebraic objects?

16 July, 2010 at 1:58 pm

Terence TaoAlmost every fundamental concept or object in mathematics can be interpreted in a number of different ways (algebraic, geometric, dynamical, analytical, etc.), and it is important to internalise as many of these as one can in order to truly understand these concepts. I recommend the discussion in Thurston’s article “On proof and progress in mathematics” for further reading. (Section 2 is the most relevant here, but the entire article is worthwhile.)

15 July, 2010 at 11:16 am

AnonymousNaive question: How do you yourself distinguish algebraic objects from geometric objects? I didn’t find the relevant wikipedia article especially helpful in this regard.

15 July, 2010 at 7:09 pm

xiaodong xuDear Terry, you wrote

•(Connectedness) The graph is connected.

This may not be true for some Cayley graphs. For instance, Z/8Z and S={2}.

Yes?

16 July, 2010 at 8:09 am

Terence Tao{2} does not generate Z/8Z.

16 July, 2010 at 3:49 am

westy31Dear Terrence,

I thought it would be interesting to mention the relationship between Cayley graphs and tilings. I have some pictures on thi on my web page:

http://www.xs4all.nl/~westy31/Geometry/Geometry.html#Cayley

Basically, you can take any Cayley graph with 2 generators, and turn it into a tiling of a Riemann surface. Each tile corresponds to a vertex of the Cayley graph. Since any finite simple group can be generated by 2 generators, all finite simple groups are a tiling of a Riemann surface. Also, you can interpret the tiling itself as a Cayly graph, by labeling rotations around the vertices as generators.

One question that comes to mind if the genus of the surface has some group theoretic meaning.

Gerard

18 July, 2010 at 7:22 am

Jason RuteInteresting article. In the second paragraph after the picture of S_3 you mention it can be split into “two red components” and “three blue components”. I believe you mean “two blue components” and “three red components”.

[Corrected, thanks – T.]19 July, 2010 at 1:21 am

studentYou wrote:

“In some cases, each colour {s \in S\backslash S’} will connect a {S’}-component to exactly one other {S’}-component; this is the case for instance when one splits {S_3} into three red components. In other cases, a colour {s} can connect a {S’}-component to multiple {S’}-components; this is the case for instance when one splits {S_3} into two blue components. ”

which should probably (???) read:

In some cases, each colour {s \in S\backslash S’} will connect a {S’}-component to exactly one other {S’}-component; this is the case for instance when one splits {S_3} into two blue components. In other cases, a colour {s} can connect a {S’}-component to multiple {S’}-components; this is the case for instance when one splits {S_3} into three red components.

[Oops! I implemented a previous fix incorrectly. Thanks, it should be correct now – T.]25 July, 2010 at 5:40 am

Politopos. « US Patent Appl. 12213303: Comentarios.[…] 3….y un post muy informativo sobre grafos de Cayley como “representación geometrica” de grupos: https://terrytao.wordpress.com/2010/07/10/cayley-graphs-and-the-geometry-of-groups/ […]

27 August, 2010 at 1:46 am

marryHi,

I am newly interested in cayley graph. I read note on cayley graphs. may be it is very clear but I could not understand how can I draw ,i.e. how can ı draw directed edge? you gave example for 6Z and S={1}. as you say, I use from x to sx. but only one element exists in S and then edge is from 1 to 1, 2 to 2… and so on. Can I misunderstand?

27 August, 2010 at 9:06 am

Terence TaoIn the case of an additive group such as rather than a multiplicative group , one would connect x to s+x, rather than x to sx.

29 August, 2010 at 1:08 am

marryDear Prof. Tao,

firstly, thanks for answering my previous question.

I wonder that all inverse element of S is also S. Is this necessary or not?

in your note about cayley graphs you did not wrote but some books add this condition.

and you said that word metric is the maximal metric .What reason is maximal?

best regards,

30 August, 2010 at 8:46 am

Terence TaoThere are two types of Cayley graphs: directed Cayley graphs (the ones discussed here) and undirected Cayley graphs. The latter require a symmetric set of generators, and the former does not.

The word metric is maximal with respect to the pointwise order on metrics (in which one writes for two metrics d,d’ if one has for all x,y) subject to the constraint that for all x in G and s in S. This is a succinct way to define the word metric, but perhaps not the most enlightening, which is why I also added a more explicit description of that metric.

18 May, 2012 at 9:54 pm

SonDear prof. Tao,

Would only? Only that would make sense to me because this is kind of defining a metric of orbit of . What we care here is to establish the connection between and its orbits. If the action of on results in , . Otherwise, it is .

If that’s the case, .

That’s how I can make sense of this. Please correct me if I’m wrong.

31 August, 2010 at 3:21 am

marryDear prof. Tao,

you said that a directed coloured graph is a Cayley graph (up to relabeling) if and only if it obeys the above three properties. I understand one way of the proof. conversely for showing that cayley graph satisfy property of Homogeneity ,you use right multiplication xg. Can we choose left multiplication instead of right?

best regards,

27 August, 2011 at 11:35 am

254A, Notes 0 – Hilbert’s fifth problem and related topics « What’s new[…] describes the geometry of the Cayley graph on formed by connecting to for each and . (See this previous post for more discussion of using Cayley graphs to study groups […]

11 May, 2012 at 10:51 am

Cayley graphs and the algebra of groups « What’s new[…] is a sequel to my previous blog post “Cayley graphs and the geometry of groups“. In that post, the concept of a Cayley graph of a group was used to place some geometry on […]

18 November, 2013 at 9:49 pm

geometric conceptions of groups (and walks of graphs from groups); Heisenburg group | Peter's ruminations[…] https://terrytao.wordpress.com/2010/07/10/cayley-graphs-and-the-geometry-of-groups/ […]

3 February, 2014 at 3:58 am

ImranI want to ask a question…that If we have a finite presentation of a group, but order of the generators are unknown, then can we draw a cayley graph of that group?? if yes, then by which mean

3 August, 2014 at 7:01 am

Tuấn BùiReblogged this on Tuấn Bùi and commented:

Archived!

14 October, 2014 at 7:15 pm

AnonymousDoes the undirected cayley graph representation of a group always have a hamiltonian cycle for any choice of generators?

15 October, 2014 at 7:02 am

Terence TaoThis turns out to be a well studied problem with many partial results, though still far from completely solved: http://www.sciencedirect.com/science/article/pii/0012365X95000725

20 February, 2015 at 3:20 am

Groups and Group Actions: Lecture 2 | Theorem of the week[…] in various places, for example Fields medallist Terry Tao has written about them on his blog, e.g. here (warning: this post assumes knowledge of more advanced maths than first-year undergraduates usually […]

21 February, 2015 at 2:58 am

AnonymousAnother interesting example is the study of the subgroup of algebraic functions (of one complex variable over the Riemann sphere) generated by compositions of (all branches) of finitely many algebraic functions.

4 May, 2015 at 7:25 am

ValentinoI have a (probably) easy question.

Given a generating set S for a group G, I ask if the following proposition is true or not: “G has exactly one longest element wrt S if and only if S is a minimal generating set” ???

I know that this question can also be interpreted in terms of “minimal” Cayley graphs, but I can’t realize if it’s true or not.