Height of the Uniform Random Tree Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Maximum height of a quad treeUnderstanding various definitions of TREE($n$) in Friedman's finite form of Kruskal's tree theorem.Height of a full binary treeVariance of Height of TreeHalting probability of random tree-generating algorithmIs this random binary tree finite?Height of quasi-complete binary treeCounting spanning trees in labelled graphsNumber of binary search tree of height $6$Example of uniform tree lattice?
Fantasy story; one type of magic grows in power with use, but the more powerful they are, they more they are drawn to travel to their source
What is the meaning of the simile “quick as silk”?
Amount of permutations on an NxNxN Rubik's Cube
8 Prisoners wearing hats
Trademark violation for app?
How to Make a Beautiful Stacked 3D Plot
Is it cost-effective to upgrade an old-ish Giant Escape R3 commuter bike with entry-level branded parts (wheels, drivetrain)?
Do I really need recursive chmod to restrict access to a folder?
2001: A Space Odyssey's use of the song "Daisy Bell" (Bicycle Built for Two); life imitates art or vice-versa?
Why are both D and D# fitting into my E minor key?
Circuit to "zoom in" on mV fluctuations of a DC signal?
How to show element name in portuguese using elements package?
Is there such thing as an Availability Group failover trigger?
Why do we bend a book to keep it straight?
Is it ethical to give a final exam after the professor has quit before teaching the remaining chapters of the course?
What does the "x" in "x86" represent?
What is the longest distance a player character can jump in one leap?
Find the length x such that the two distances in the triangle are the same
How would a mousetrap for use in space work?
Has negative voting ever been officially implemented in elections, or seriously proposed, or even studied?
Do I really need to have a message in a novel to appeal to readers?
Is it a good idea to use CNN to classify 1D signal?
First console to have temporary backward compatibility
Using et al. for a last / senior author rather than for a first author
Height of the Uniform Random Tree
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Maximum height of a quad treeUnderstanding various definitions of TREE($n$) in Friedman's finite form of Kruskal's tree theorem.Height of a full binary treeVariance of Height of TreeHalting probability of random tree-generating algorithmIs this random binary tree finite?Height of quasi-complete binary treeCounting spanning trees in labelled graphsNumber of binary search tree of height $6$Example of uniform tree lattice?
$begingroup$
Consider $mathcalT_n$ the uniform rooted labelled tree on $n$ vertices (i.e. each spanning tree on $K_n$ has the same probability to be picked, and the root is picked uniformly among the $n$ vertices).
Denote $h(t)=max_v d(textroot,v)$ be the height of the tree $t$.
I'm interested in understanding $h(mathcalT_n)$.
While Renyi and Szekeres proved in this paper that $mathbbE(mathcalT_n)tosqrt2pi n$ (and actually computed the limiting distribution of the scaled height), many authors, like Aldous in here, claim that just realizing that the height behaves like $sqrtn$ should be "easy" to derive.
Does anybody know of an "easy" way to prove this? I would guess the formal fact we want to show is that $h(mathcalT_n)=O(sqrtn)$ in probability, but this might be wrong.
Thank you very much.
probability combinatorics graph-theory trees
asked Mar 27 at 2:56
Francisco MartínezFrancisco Martínez
10918
$endgroup$
add a comment |
$begingroup$
Consider $mathcalT_n$ the uniform rooted labelled tree on $n$ vertices (i.e. each spanning tree on $K_n$ has the same probability to be picked, and the root is picked uniformly among the $n$ vertices).
Denote $h(t)=max_v d(textroot,v)$ be the height of the tree $t$.
I'm interested in understanding $h(mathcalT_n)$.
While Renyi and Szekeres proved in this paper that $mathbbE(mathcalT_n)tosqrt2pi n$ (and actually computed the limiting distribution of the scaled height), many authors, like Aldous in here, claim that just realizing that the height behaves like $sqrtn$ should be "easy" to derive.
Does anybody know of an "easy" way to prove this? I would guess the formal fact we want to show is that $h(mathcalT_n)=O(sqrtn)$ in probability, but this might be wrong.
Thank you very much.
probability combinatorics graph-theory trees
asked Mar 27 at 2:56
Francisco MartínezFrancisco Martínez
10918
$endgroup$
add a comment |
$begingroup$
Consider $mathcalT_n$ the uniform rooted labelled tree on $n$ vertices (i.e. each spanning tree on $K_n$ has the same probability to be picked, and the root is picked uniformly among the $n$ vertices).
Denote $h(t)=max_v d(textroot,v)$ be the height of the tree $t$.
I'm interested in understanding $h(mathcalT_n)$.
While Renyi and Szekeres proved in this paper that $mathbbE(mathcalT_n)tosqrt2pi n$ (and actually computed the limiting distribution of the scaled height), many authors, like Aldous in here, claim that just realizing that the height behaves like $sqrtn$ should be "easy" to derive.
Does anybody know of an "easy" way to prove this? I would guess the formal fact we want to show is that $h(mathcalT_n)=O(sqrtn)$ in probability, but this might be wrong.
Thank you very much.
probability combinatorics graph-theory trees
asked Mar 27 at 2:56
Francisco MartínezFrancisco Martínez
10918
$endgroup$
Consider $mathcalT_n$ the uniform rooted labelled tree on $n$ vertices (i.e. each spanning tree on $K_n$ has the same probability to be picked, and the root is picked uniformly among the $n$ vertices).
Denote $h(t)=max_v d(textroot,v)$ be the height of the tree $t$.
I'm interested in understanding $h(mathcalT_n)$.
While Renyi and Szekeres proved in this paper that $mathbbE(mathcalT_n)tosqrt2pi n$ (and actually computed the limiting distribution of the scaled height), many authors, like Aldous in here, claim that just realizing that the height behaves like $sqrtn$ should be "easy" to derive.
Does anybody know of an "easy" way to prove this? I would guess the formal fact we want to show is that $h(mathcalT_n)=O(sqrtn)$ in probability, but this might be wrong.
Thank you very much.
probability combinatorics graph-theory trees
probability combinatorics graph-theory trees
asked Mar 27 at 2:56
Francisco MartínezFrancisco Martínez
10918
asked Mar 27 at 2:56
Francisco MartínezFrancisco Martínez
10918
asked Mar 27 at 2:56
Francisco MartínezFrancisco Martínez
10918
asked Mar 27 at 2:56
Francisco MartínezFrancisco Martínez
10918
asked Mar 27 at 2:56
Francisco MartínezFrancisco Martínez
10918
10918
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
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%2fmath.stackexchange.com%2fquestions%2f3164040%2fheight-of-the-uniform-random-tree%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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%2fmath.stackexchange.com%2fquestions%2f3164040%2fheight-of-the-uniform-random-tree%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
