# What is meant by Invariant Measure on a Graph

In an unpublished paper by Ackerman-Freer-Patel, it is stated that if a relational structure has trivial definable closure, it has an invariant measure. This finding is very new (1 year old) and hence is not published. Here, however, is what they have give so far: http://www.maths.leeds.ac.uk/events/lmsnorth2011/freerpatel.pdf

My question is: What exactly do THEY mean by an invariant measure? If i had to explain to my uneducated (in graph theory) friend what they meant by an invariant measure, what would I tell him? Its obviously not as trivial as same number of edges, or same planarity... or is it?

If I were to guess, I would say a distribution on edge relations that is unchanged under any permutation of the vertices, but even that accounts for trivial invariant measures. Can someone clear this up? What do those three people mean specifically???

-
The point is that they are not just interested in $S_{\infty}$ invariant Borel measures. They are interested in such measures that are concentrated in an isomorphism class of a particular relational structure. I wish you could make your question a bit more specific. – Gjergji Zaimi Aug 30 '11 at 2:30
I thought I made it clear, but if there is something you do not understand, simply tell me and I will explain what I meant :) – Raj Aug 30 '11 at 2:43
Well, for me the definitions in that presentation seem fine, so when you say you are having trouble understanding them, it sounds like it would be better if you were specific on which parts you are having trouble with. Is it understanding the weak topology on the set of graphs, the construction of Borel measures, what it means for a measure to be concentrated at a particular set, etc.? – Gjergji Zaimi Aug 30 '11 at 3:32

I agree with @Gjergji that the technical answer you require is on page 4 of the paper you reference.

A measure $m$ on $S_L$ is invariant when it is invariant under the action of $\mathfrak G_{\mathbb N}$ (the permutation group of $\mathbb N$), i.e., for every Borel set $X \subseteq S_L$ and every $g \in \mathfrak G_{\mathbb N}$, we have $m(X) = m(g.X)$.

So, they put a measure m on the space of your special graphs. For any set of graphs $X \subseteq S_L$, we measure the size of this set as $m(X)$. If we rename all the verticies of $X$ and call this set $g.X$, then these sets have equal measure $m(X)=m(g.X)$.

So, to your friend, you can say that "invariant measure" means that the measure assigns the same number to sets of isomorphic graphs.

-
"the measure assigns the same number to sets of isomorphic graphs" I think, it is misleading formulation: the point is that the isomorphism must be the same. The correct one could be "the measure assigns the same number to two sets of graphs, one of which is obtained from another by the same permutation of vertices" – Fedor Petrov Aug 30 '11 at 7:07
But couldnt the measure be as trivial as "number of edges" in which case $m$ would assign the same number to two sets of graphs with permuted vertices. And then OBVIOUSLY every graph with trivial dcl has an invariant measure, namely the trivial one! (same number of edges) – Raj Aug 30 '11 at 15:17
Thank you @Fedor. What you say is an improvement to my inaccurate description. @Raj, can you make edge-counting into a probability measure on graphs of countable size? – Daniel Mansfield Aug 30 '11 at 22:08
I suppose my next question would be how does a probability invariant measure differ from a simple invariant measure – Raj Aug 31 '11 at 3:31
What do you mean by "simple invariant measure"? – Daniel Mansfield Sep 3 '11 at 7:51