Asymptotics of orbits on graphs Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?Growth rate of number of loops in a graphAsymptotics for forbidden subwords“Antipodal” maps on regular graphs?Average squared distance in $k$-regular graphsA question about expander graphsFinite vertex-transitive graphs that look like infinite vertex-transitive graphsLovász conjecture and 2-connected graphsHamming representability of finite graphsGraphs formed of vertices of distance $2$Reference on graphs such that contracting 2 non-adjacent vertices increases the Hadwiger number
Asymptotics of orbits on graphs
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?Growth rate of number of loops in a graphAsymptotics for forbidden subwords“Antipodal” maps on regular graphs?Average squared distance in $k$-regular graphsA question about expander graphsFinite vertex-transitive graphs that look like infinite vertex-transitive graphsLovász conjecture and 2-connected graphsHamming representability of finite graphsGraphs formed of vertices of distance $2$Reference on graphs such that contracting 2 non-adjacent vertices increases the Hadwiger number
$begingroup$
Let $X$ be a connected, locally finite graph with vertex set $V(X)$ and $G$ a group acting freely on $X$ such that $X/G$ is a finite graph. Fix a vertex $x$ and for $kinmathbb N$ set
$$
N(k)=# gin G: d(gx,x)le k,
$$
where $d$ is the vertex distance in the graph $X$.
Further set
$$
A(k)=#yin V(X):d(x,y)le k.
$$
Is it true that, as $ktoinfty$, the number $N(k)/A(k)$ tends to $#V(X/G)^-1$? If so, what error term estimates are known?
graph-theory asymptotics
asked Apr 4 at 7:09
ZeroZero
2667
$endgroup$
add a comment |
$begingroup$
Let $X$ be a connected, locally finite graph with vertex set $V(X)$ and $G$ a group acting freely on $X$ such that $X/G$ is a finite graph. Fix a vertex $x$ and for $kinmathbb N$ set
$$
N(k)=# gin G: d(gx,x)le k,
$$
where $d$ is the vertex distance in the graph $X$.
Further set
$$
A(k)=#yin V(X):d(x,y)le k.
$$
Is it true that, as $ktoinfty$, the number $N(k)/A(k)$ tends to $#V(X/G)^-1$? If so, what error term estimates are known?
graph-theory asymptotics
asked Apr 4 at 7:09
ZeroZero
2667
$endgroup$
$begingroup$
Very interesting! Can you please add the reference or the source of inspiration for this problem?
$endgroup$
– SeF
Apr 4 at 8:50
$begingroup$
It's kind of a graph analogue of lattice point counting.
$endgroup$
– Zero
Apr 4 at 9:04
$begingroup$
"The theory of lattices in automorphism groups of trees. The theory of tree lattices was developed by Bass, Kulkarni and Lubotzky[25][26] by analogy with the theory of lattices in Lie groups (that is discrete subgroups of Lie groups of finite co-volume). For a discrete subgroup G of the automorphism group of a locally finite tree X one can define a natural notion of volume for the quotient graph of groups A as $vol(A) = sum_v in V frac1lvert A_v rvert$" - wiki on Bass-Serre theory
$endgroup$
– i9Fn
Apr 6 at 9:41
add a comment |
$begingroup$
Let $X$ be a connected, locally finite graph with vertex set $V(X)$ and $G$ a group acting freely on $X$ such that $X/G$ is a finite graph. Fix a vertex $x$ and for $kinmathbb N$ set
$$
N(k)=# gin G: d(gx,x)le k,
$$
where $d$ is the vertex distance in the graph $X$.
Further set
$$
A(k)=#yin V(X):d(x,y)le k.
$$
Is it true that, as $ktoinfty$, the number $N(k)/A(k)$ tends to $#V(X/G)^-1$? If so, what error term estimates are known?
graph-theory asymptotics
asked Apr 4 at 7:09
ZeroZero
2667
$endgroup$
Let $X$ be a connected, locally finite graph with vertex set $V(X)$ and $G$ a group acting freely on $X$ such that $X/G$ is a finite graph. Fix a vertex $x$ and for $kinmathbb N$ set
$$
N(k)=# gin G: d(gx,x)le k,
$$
where $d$ is the vertex distance in the graph $X$.
Further set
$$
A(k)=#yin V(X):d(x,y)le k.
$$
Is it true that, as $ktoinfty$, the number $N(k)/A(k)$ tends to $#V(X/G)^-1$? If so, what error term estimates are known?
graph-theory asymptotics
graph-theory asymptotics
asked Apr 4 at 7:09
ZeroZero
2667
asked Apr 4 at 7:09
ZeroZero
2667
edited Apr 4 at 9:01
Zero
asked Apr 4 at 7:09
ZeroZero
2667
asked Apr 4 at 7:09
ZeroZero
2667
asked Apr 4 at 7:09
ZeroZero
2667
2667
$begingroup$
Very interesting! Can you please add the reference or the source of inspiration for this problem?
$endgroup$
– SeF
Apr 4 at 8:50
$begingroup$
It's kind of a graph analogue of lattice point counting.
$endgroup$
– Zero
Apr 4 at 9:04
$begingroup$
"The theory of lattices in automorphism groups of trees. The theory of tree lattices was developed by Bass, Kulkarni and Lubotzky[25][26] by analogy with the theory of lattices in Lie groups (that is discrete subgroups of Lie groups of finite co-volume). For a discrete subgroup G of the automorphism group of a locally finite tree X one can define a natural notion of volume for the quotient graph of groups A as $vol(A) = sum_v in V frac1lvert A_v rvert$" - wiki on Bass-Serre theory
$endgroup$
– i9Fn
Apr 6 at 9:41
add a comment |
$begingroup$
Very interesting! Can you please add the reference or the source of inspiration for this problem?
$endgroup$
– SeF
Apr 4 at 8:50
$begingroup$
It's kind of a graph analogue of lattice point counting.
$endgroup$
– Zero
Apr 4 at 9:04
$begingroup$
"The theory of lattices in automorphism groups of trees. The theory of tree lattices was developed by Bass, Kulkarni and Lubotzky[25][26] by analogy with the theory of lattices in Lie groups (that is discrete subgroups of Lie groups of finite co-volume). For a discrete subgroup G of the automorphism group of a locally finite tree X one can define a natural notion of volume for the quotient graph of groups A as $vol(A) = sum_v in V frac1lvert A_v rvert$" - wiki on Bass-Serre theory
$endgroup$
– i9Fn
Apr 6 at 9:41
$begingroup$
Very interesting! Can you please add the reference or the source of inspiration for this problem?
$endgroup$
– SeF
Apr 4 at 8:50
$begingroup$
Very interesting! Can you please add the reference or the source of inspiration for this problem?
$endgroup$
– SeF
Apr 4 at 8:50
$begingroup$
It's kind of a graph analogue of lattice point counting.
$endgroup$
– Zero
Apr 4 at 9:04
$begingroup$
It's kind of a graph analogue of lattice point counting.
$endgroup$
– Zero
Apr 4 at 9:04
$begingroup$
"The theory of lattices in automorphism groups of trees. The theory of tree lattices was developed by Bass, Kulkarni and Lubotzky[25][26] by analogy with the theory of lattices in Lie groups (that is discrete subgroups of Lie groups of finite co-volume). For a discrete subgroup G of the automorphism group of a locally finite tree X one can define a natural notion of volume for the quotient graph of groups A as $vol(A) = sum_v in V frac1lvert A_v rvert$" - wiki on Bass-Serre theory
$endgroup$
– i9Fn
Apr 6 at 9:41
$begingroup$
"The theory of lattices in automorphism groups of trees. The theory of tree lattices was developed by Bass, Kulkarni and Lubotzky[25][26] by analogy with the theory of lattices in Lie groups (that is discrete subgroups of Lie groups of finite co-volume). For a discrete subgroup G of the automorphism group of a locally finite tree X one can define a natural notion of volume for the quotient graph of groups A as $vol(A) = sum_v in V frac1lvert A_v rvert$" - wiki on Bass-Serre theory
$endgroup$
– i9Fn
Apr 6 at 9:41
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
It is possible that the limit does not exist at all: Consider the free group on two generators acting on the $(4,2)$-biregular tree in the obvious way. This action is free and has 3 orbits (one containing all vertices of degree 4, and the other two containing "half" of the vertices of degree 2).
Let $x$ be a vertex of degree $4$. Then $N(k)$ is the number of vertices of degree 4 in $B_x(k)$, and $A(k)$ is the total number of vertices in $B_x(k)$. If we write $a_k$ and $b_k$ for the number of vertices at distance exactly $k$ from $x$ which have degree 4 or 2 respectively, we get $a_0 = 1$, and $b_2l+1 = a_2l+2 = 4cdot3^l$ and $b_2l = a_2l+1 = 0$ for $l geq 0$. Note that
$$fracN(k)A(k) = fracsum_i leq k a_isum_i leq k a_i + b_i$$
and if I'm not mistaken, plugging in the above values gives a limit of $frac 12$ for the subsequence of even $k$, and $frac 14$ for the subsequence of odd $k$.
answered Apr 4 at 11:19
Florian LehnerFlorian Lehner
54138
$endgroup$
1
$begingroup$
Can you explain how the free group acts on the $(4,2)$-biregular tree? It is not obvious to me what is the obvious way.
$endgroup$
– i9Fn
Apr 5 at 18:00
$begingroup$
The $4$-regular tree is a Cayley graph of the free group on two generators, which gives a natural action of this group on it. The $(4,2)$-regular tree inherits this action since it can be obtained from the $4$-regular tree by replacing every edge by a path of length $2$.
$endgroup$
– Florian Lehner
Apr 8 at 8:45
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "504"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f327119%2fasymptotics-of-orbits-on-graphs%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It is possible that the limit does not exist at all: Consider the free group on two generators acting on the $(4,2)$-biregular tree in the obvious way. This action is free and has 3 orbits (one containing all vertices of degree 4, and the other two containing "half" of the vertices of degree 2).
Let $x$ be a vertex of degree $4$. Then $N(k)$ is the number of vertices of degree 4 in $B_x(k)$, and $A(k)$ is the total number of vertices in $B_x(k)$. If we write $a_k$ and $b_k$ for the number of vertices at distance exactly $k$ from $x$ which have degree 4 or 2 respectively, we get $a_0 = 1$, and $b_2l+1 = a_2l+2 = 4cdot3^l$ and $b_2l = a_2l+1 = 0$ for $l geq 0$. Note that
$$fracN(k)A(k) = fracsum_i leq k a_isum_i leq k a_i + b_i$$
and if I'm not mistaken, plugging in the above values gives a limit of $frac 12$ for the subsequence of even $k$, and $frac 14$ for the subsequence of odd $k$.
answered Apr 4 at 11:19
Florian LehnerFlorian Lehner
54138
$endgroup$
1
$begingroup$
Can you explain how the free group acts on the $(4,2)$-biregular tree? It is not obvious to me what is the obvious way.
$endgroup$
– i9Fn
Apr 5 at 18:00
$begingroup$
The $4$-regular tree is a Cayley graph of the free group on two generators, which gives a natural action of this group on it. The $(4,2)$-regular tree inherits this action since it can be obtained from the $4$-regular tree by replacing every edge by a path of length $2$.
$endgroup$
– Florian Lehner
Apr 8 at 8:45
add a comment |
$begingroup$
It is possible that the limit does not exist at all: Consider the free group on two generators acting on the $(4,2)$-biregular tree in the obvious way. This action is free and has 3 orbits (one containing all vertices of degree 4, and the other two containing "half" of the vertices of degree 2).
Let $x$ be a vertex of degree $4$. Then $N(k)$ is the number of vertices of degree 4 in $B_x(k)$, and $A(k)$ is the total number of vertices in $B_x(k)$. If we write $a_k$ and $b_k$ for the number of vertices at distance exactly $k$ from $x$ which have degree 4 or 2 respectively, we get $a_0 = 1$, and $b_2l+1 = a_2l+2 = 4cdot3^l$ and $b_2l = a_2l+1 = 0$ for $l geq 0$. Note that
$$fracN(k)A(k) = fracsum_i leq k a_isum_i leq k a_i + b_i$$
and if I'm not mistaken, plugging in the above values gives a limit of $frac 12$ for the subsequence of even $k$, and $frac 14$ for the subsequence of odd $k$.
answered Apr 4 at 11:19
Florian LehnerFlorian Lehner
54138
$endgroup$
1
$begingroup$
Can you explain how the free group acts on the $(4,2)$-biregular tree? It is not obvious to me what is the obvious way.
$endgroup$
– i9Fn
Apr 5 at 18:00
$begingroup$
The $4$-regular tree is a Cayley graph of the free group on two generators, which gives a natural action of this group on it. The $(4,2)$-regular tree inherits this action since it can be obtained from the $4$-regular tree by replacing every edge by a path of length $2$.
$endgroup$
– Florian Lehner
Apr 8 at 8:45
add a comment |
$begingroup$
It is possible that the limit does not exist at all: Consider the free group on two generators acting on the $(4,2)$-biregular tree in the obvious way. This action is free and has 3 orbits (one containing all vertices of degree 4, and the other two containing "half" of the vertices of degree 2).
Let $x$ be a vertex of degree $4$. Then $N(k)$ is the number of vertices of degree 4 in $B_x(k)$, and $A(k)$ is the total number of vertices in $B_x(k)$. If we write $a_k$ and $b_k$ for the number of vertices at distance exactly $k$ from $x$ which have degree 4 or 2 respectively, we get $a_0 = 1$, and $b_2l+1 = a_2l+2 = 4cdot3^l$ and $b_2l = a_2l+1 = 0$ for $l geq 0$. Note that
$$fracN(k)A(k) = fracsum_i leq k a_isum_i leq k a_i + b_i$$
and if I'm not mistaken, plugging in the above values gives a limit of $frac 12$ for the subsequence of even $k$, and $frac 14$ for the subsequence of odd $k$.
answered Apr 4 at 11:19
Florian LehnerFlorian Lehner
54138
$endgroup$
It is possible that the limit does not exist at all: Consider the free group on two generators acting on the $(4,2)$-biregular tree in the obvious way. This action is free and has 3 orbits (one containing all vertices of degree 4, and the other two containing "half" of the vertices of degree 2).
Let $x$ be a vertex of degree $4$. Then $N(k)$ is the number of vertices of degree 4 in $B_x(k)$, and $A(k)$ is the total number of vertices in $B_x(k)$. If we write $a_k$ and $b_k$ for the number of vertices at distance exactly $k$ from $x$ which have degree 4 or 2 respectively, we get $a_0 = 1$, and $b_2l+1 = a_2l+2 = 4cdot3^l$ and $b_2l = a_2l+1 = 0$ for $l geq 0$. Note that
$$fracN(k)A(k) = fracsum_i leq k a_isum_i leq k a_i + b_i$$
and if I'm not mistaken, plugging in the above values gives a limit of $frac 12$ for the subsequence of even $k$, and $frac 14$ for the subsequence of odd $k$.
answered Apr 4 at 11:19
Florian LehnerFlorian Lehner
54138
answered Apr 4 at 11:19
Florian LehnerFlorian Lehner
54138
answered Apr 4 at 11:19
Florian LehnerFlorian Lehner
54138
answered Apr 4 at 11:19
Florian LehnerFlorian Lehner
54138
54138
1
$begingroup$
Can you explain how the free group acts on the $(4,2)$-biregular tree? It is not obvious to me what is the obvious way.
$endgroup$
– i9Fn
Apr 5 at 18:00
$begingroup$
The $4$-regular tree is a Cayley graph of the free group on two generators, which gives a natural action of this group on it. The $(4,2)$-regular tree inherits this action since it can be obtained from the $4$-regular tree by replacing every edge by a path of length $2$.
$endgroup$
– Florian Lehner
Apr 8 at 8:45
add a comment |
1
$begingroup$
Can you explain how the free group acts on the $(4,2)$-biregular tree? It is not obvious to me what is the obvious way.
$endgroup$
– i9Fn
Apr 5 at 18:00
$begingroup$
The $4$-regular tree is a Cayley graph of the free group on two generators, which gives a natural action of this group on it. The $(4,2)$-regular tree inherits this action since it can be obtained from the $4$-regular tree by replacing every edge by a path of length $2$.
$endgroup$
– Florian Lehner
Apr 8 at 8:45
1
1
$begingroup$
Can you explain how the free group acts on the $(4,2)$-biregular tree? It is not obvious to me what is the obvious way.
$endgroup$
– i9Fn
Apr 5 at 18:00
$begingroup$
Can you explain how the free group acts on the $(4,2)$-biregular tree? It is not obvious to me what is the obvious way.
$endgroup$
– i9Fn
Apr 5 at 18:00
$begingroup$
The $4$-regular tree is a Cayley graph of the free group on two generators, which gives a natural action of this group on it. The $(4,2)$-regular tree inherits this action since it can be obtained from the $4$-regular tree by replacing every edge by a path of length $2$.
$endgroup$
– Florian Lehner
Apr 8 at 8:45
$begingroup$
The $4$-regular tree is a Cayley graph of the free group on two generators, which gives a natural action of this group on it. The $(4,2)$-regular tree inherits this action since it can be obtained from the $4$-regular tree by replacing every edge by a path of length $2$.
$endgroup$
– Florian Lehner
Apr 8 at 8:45
add a comment |
Thanks for contributing an answer to MathOverflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f327119%2fasymptotics-of-orbits-on-graphs%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Very interesting! Can you please add the reference or the source of inspiration for this problem?
$endgroup$
– SeF
Apr 4 at 8:50
$begingroup$
It's kind of a graph analogue of lattice point counting.
$endgroup$
– Zero
Apr 4 at 9:04
$begingroup$
"The theory of lattices in automorphism groups of trees. The theory of tree lattices was developed by Bass, Kulkarni and Lubotzky[25][26] by analogy with the theory of lattices in Lie groups (that is discrete subgroups of Lie groups of finite co-volume). For a discrete subgroup G of the automorphism group of a locally finite tree X one can define a natural notion of volume for the quotient graph of groups A as $vol(A) = sum_v in V frac1lvert A_v rvert$" - wiki on Bass-Serre theory
$endgroup$
– i9Fn
Apr 6 at 9:41