Welcome to MathOverflow

Question

0

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???

flag	asked Aug 30 2011 at 1:32 Raj 23●5

	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 2011 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 2011 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 2011 at 3:32

Daniel Mansfield · Answer 1 · 2011-08-30 04:45:51Z UTC

2

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.

edited Aug 30 2011 at 4:45

answered Aug 30 2011 at 3:32

Daniel Mansfield
438●1●8

	"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 2011 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 2011 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 2011 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 2011 at 3:31
	What do you mean by "simple invariant measure"? – Daniel Mansfield Sep 3 2011 at 7:51

What is meant by Invariant Measure on a Graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.