Asymptotics of orbits on graphsGrowth 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
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 14 hours ago
ZeroZero
2567
$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 14 hours ago
ZeroZero
2567
$endgroup$
$begingroup$
Very interesting! Can you please add the reference or the source of inspiration for this problem?
$endgroup$
– SeF
12 hours ago
$begingroup$
It's kind of a graph analogue of lattice point counting.
$endgroup$
– Zero
12 hours ago
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 14 hours ago
ZeroZero
2567
$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 14 hours ago
ZeroZero
2567
asked 14 hours ago
ZeroZero
2567
edited 12 hours ago
Zero
asked 14 hours ago
ZeroZero
2567
asked 14 hours ago
ZeroZero
2567
asked 14 hours ago
ZeroZero
2567
2567
$begingroup$
Very interesting! Can you please add the reference or the source of inspiration for this problem?
$endgroup$
– SeF
12 hours ago
$begingroup$
It's kind of a graph analogue of lattice point counting.
$endgroup$
– Zero
12 hours ago
add a comment |
$begingroup$
Very interesting! Can you please add the reference or the source of inspiration for this problem?
$endgroup$
– SeF
12 hours ago
$begingroup$
It's kind of a graph analogue of lattice point counting.
$endgroup$
– Zero
12 hours ago
$begingroup$
Very interesting! Can you please add the reference or the source of inspiration for this problem?
$endgroup$
– SeF
12 hours ago
$begingroup$
Very interesting! Can you please add the reference or the source of inspiration for this problem?
$endgroup$
– SeF
12 hours ago
$begingroup$
It's kind of a graph analogue of lattice point counting.
$endgroup$
– Zero
12 hours ago
$begingroup$
It's kind of a graph analogue of lattice point counting.
$endgroup$
– Zero
12 hours ago
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 10 hours ago
Florian LehnerFlorian Lehner
54138
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
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 10 hours ago
Florian LehnerFlorian Lehner
54138
$endgroup$
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 10 hours ago
Florian LehnerFlorian Lehner
54138
$endgroup$
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 10 hours ago
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 10 hours ago
Florian LehnerFlorian Lehner
54138
answered 10 hours ago
Florian LehnerFlorian Lehner
54138
answered 10 hours ago
Florian LehnerFlorian Lehner
54138
answered 10 hours ago
Florian LehnerFlorian Lehner
54138
54138
add a comment |
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
12 hours ago
$begingroup$
It's kind of a graph analogue of lattice point counting.
$endgroup$
– Zero
12 hours ago