Timeline for Is the empty graph a tree?
Current License: CC BY-SA 3.0
38 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 19, 2022 at 8:14 | comment | added | bof | By definition, an empty graph is a graph with no edges. An empty graph with $n$ vertices is a tree if $n=1$; it's not a tree if $n\gt1$. | |
| Mar 19, 2022 at 3:19 | answer | added | Russ Woodroofe | timeline score: 1 | |
| S Jan 27, 2014 at 20:58 | history | suggested | F. C. |
added one tag
|
|
| Jan 27, 2014 at 20:53 | review | Suggested edits | |||
| S Jan 27, 2014 at 20:58 | |||||
| Feb 7, 2013 at 14:22 | answer | added | Günter Rote | timeline score: 8 | |
| Feb 7, 2013 at 14:15 | comment | added | Günter Rote | @Jernej: what do you mean by "subdivision" in "Sage simply computes the subdivision of the Laplacian matrix"? For non-empty graphs, one can remove an arbitrary row and column and compute the determinant. How does sage remove a row from the empty matrix. | |
| Feb 5, 2013 at 19:12 | comment | added | Andrew D. King | By the way, Jernej, when making contributions to Sage, boring technical questions are of the utmost importance, particularly when recursion is involved! | |
| Feb 5, 2013 at 8:05 | answer | added | ACL | timeline score: 2 | |
| Feb 5, 2013 at 3:06 | comment | added | Todd Trimble | Tsk, tsk, Ronnie Brown! The others don't surprise me a bit. | |
| Feb 5, 2013 at 1:04 | comment | added | ACL | @Brendan McKay. Apparently, derivations of the $n^{n-2}$ formula all assume that $n\geq 1$. For example, in Kirchoff theorem, it is question of cofactor; and an empty matrix has no cofactor. In the Prüfer sequences story, you even need to assume that $n\geq 2$ since the Prüfer sequence has length $n-2$. | |
| Feb 5, 2013 at 0:53 | comment | added | ACL | Just for fun, I browsed in the litterature to find what definition of connectedness was used. For Tom Dieck (Algebraic Topology), Munkres (Topology, A First Course), Ronnie Brown (Topology and groupoids), the empty set is connected. For Ethan Bloch, the empty space might be connected, but the first theorem he mentions is that the... non-empty connected sets of real numbers are the interval. :-) | |
| Feb 4, 2013 at 23:26 | answer | added | André Henriques | timeline score: 14 | |
| Feb 4, 2013 at 22:43 | comment | added | ACL | Why would the empty graph have a spanning tree? Not every graph has a spanning tree! But every graph has a spanning forest. And the empty graph has exactly one. | |
| Feb 4, 2013 at 22:42 | comment | added | ACL | @Angelo. In EGA, the empty scheme is connected, as witnessed by the statement of Zariski's connectedness theorem (III, 4.3.1), where Grothendieck and Dieudonné precise that the fibers are connected and non-empty. Of course it is not irreducible. | |
| Feb 3, 2013 at 5:09 | comment | added | Gerhard Paseman | I remember attending a MSRI conference in a previous millenium on universal algebra and category theory. I was wondering if a religious battle would break out over the notion of an empty algebra. Fortunately no blood was shed at that conference over the issue. This post reminds me of those years. Tom, I'm afraid I dealt more with nonempty algebras than potentially empty relational structures, so I am not entirely convinced by your comment. Not that you should worry. Gerhard "Pronounces Tom Devoid Of Blame" Paseman, 2013.02.02 | |
| Feb 2, 2013 at 14:41 | comment | added | Tom Goodwillie | @Andy Putnam: I am a big proponent of that definition of "$k$-connected", and in our world "1-connected" and "0-connected" are common synonyms for "path-connected" and "simply connected". But I gather that in graph theory "$k$-connected" has another unrelated meaning. | |
| Feb 2, 2013 at 14:32 | answer | added | Andreas Blass | timeline score: 18 | |
| Feb 2, 2013 at 14:20 | comment | added | Tom Goodwillie | @Gerhard: Your comment works if a graph is a set of vertices and edges, but not if a graph is, say, an ordered pair consisting of a set of vertices and a set of edges. True, there is only one empty set, but "empty thing" need not mean "thing which is an empty set". If a topological space means an ordered pair $(X,T)$ where $X$ is a set and $T$ is a topology on $X$, then "empty space" means "space $(X,T)$ such that $X$ is empty". Tom "Talk to me about the empty set" Goodwillie | |
| Feb 2, 2013 at 14:00 | comment | added | Todd Trimble | If a tree falls in a forest and no one is around to notice, could it be empty? | |
| Feb 2, 2013 at 8:46 | answer | added | Todd Trimble | timeline score: 25 | |
| Feb 2, 2013 at 8:17 | comment | added | Fred Rohrer | Ah, I see. There seems to be some confusion between "connected spaces/graphs/things..." and "connected components of spaces/graphs/things...". If the empty thing is one of the former but none of the latter, then the problems about unique decompositions disappear. | |
| Feb 2, 2013 at 6:08 | comment | added | Terry Tao | To expand upon Angelo's analogy: one needs to exclude 1 from the set of primes if one wants to decompose every natural number uniquely (up to permutation) as the product of primes (i.e. the fundamental theorem of arithmetic). Similarly, one needs to exclude the empty set from the set of trees if one wants to decompose every forest uniquely (up to permutation) as the disjoint union of trees. | |
| Feb 2, 2013 at 4:06 | comment | added | Brendan McKay | The number of trees of order $n$ is $n^{n-2}$ as everyone knows. So if the empty graph is a tree, which of the $0^{-2}$ possible trees is it? Which only goes to show that the question is not really meaningful except in the lexicographical sense. | |
| Feb 2, 2013 at 3:57 | comment | added | Benjamin Steinberg | See ncatlab.org/nlab/show/empty+space | |
| Feb 1, 2013 at 21:36 | comment | added | Fred Rohrer | @Angelo: I do not understand your argument. May I ask you to explain? | |
| Feb 1, 2013 at 21:30 | answer | added | Fred Rohrer | timeline score: 10 | |
| Feb 1, 2013 at 21:27 | vote | accept | Jernej | ||
| Feb 1, 2013 at 21:07 | answer | added | Samuel Vidal | timeline score: 4 | |
| Feb 1, 2013 at 20:55 | comment | added | Gerald Edgar | Is the empty graph a tree? No, but it's a forest. | |
| Feb 1, 2013 at 20:41 | comment | added | Andy Putman | In topology, a useful convention is to say that a space $X$ is $k$-connected if every map of an $\ell$-sphere into $X$ with $\ell \leq k$ can be extended to a map of an $(\ell+1)$-ball. With this convention, all spaces are $(-2)$-connected, and all nonempty spaces are $(-1)$-connected. So to a topologist, the empty graph is not $1$-connected, so it is not a tree. | |
| Feb 1, 2013 at 20:31 | comment | added | Jernej | @Günter Rote Sage simply computes the subdivision of the Laplacian matrix and its determinant. | |
| Feb 1, 2013 at 20:26 | answer | added | Aaron Meyerowitz | timeline score: 1 | |
| Feb 1, 2013 at 20:22 | comment | added | Günter Rote | I wonder how sage does the calculation. The complete graph on $k$ vertices is not $k$-connected. Here, the condition that a $k$-connected graph must have at least $k+1$ vertices is usually formulated explicitly. Setting $k=1$ it would mean that not even the graph with one vertex is 1-connected (=connected). So these analogies break down when it come to small values. | |
| Feb 1, 2013 at 20:15 | answer | added | Sergey Norin | timeline score: 53 | |
| Feb 1, 2013 at 20:03 | comment | added | Gerhard Paseman | Trees have roots and leaves, and when they are big enough they have branches as well. The one vertex graph is a not big tree, and the empty graph is not a tree, in my view. (The empty graph could be soil, or a dog, or a pink elephant, depending on the metaphor. Unless you need an additive identity though, the empty graph is not a tree.) Gerhard "It Is What You Need" Paseman, 2013.02.01 | |
| Feb 1, 2013 at 20:02 | comment | added | Vidit Nanda | I agree with Angelo: a "connected acyclic graph" must have the homology of a point (this is what acyclic means topologically) so even this definition does not lead to the conclusion that one should call the empty graph a tree. | |
| Feb 1, 2013 at 19:52 | comment | added | Angelo | A connected space should always be assumed to be non-empty, for the same reason that 1 is not considered to be a prime. | |
| Feb 1, 2013 at 19:33 | history | asked | Jernej | CC BY-SA 3.0 |