Jump to content

Talk:Steinitz's theorem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Who

[edit]

Who was Steinitz who made that theorem? Maybe you should add that? — Preceding unsigned comment added by 193.2.132.123 (talk • contribs)

You stopped reading before the fourth sentence? —David Eppstein (talk) 17:51, 7 April 2013 (UTC)[reply]

GA Review

[edit]
GA toolbox
Reviewing
This review is transcluded from Talk:Steinitz's theorem/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Kusma (talk · contribs) 14:01, 8 August 2021 (UTC)[reply]

I'll take this one, will make in-depth comments over the next few days. —Kusma (talk) 14:01, 8 August 2021 (UTC)[reply]

Comments

[edit]

Global comments:

  • I'm a mathematician (but with very little knowledge of graph theory and discrete mathematics), so I might overlook some pieces of jargon that others would complain about. I will complain about any jargon that I find hard to understand, though.
  • What I'm missing a bit is the context and importance of the theorem. The lead says that Branko Grünbaum claims it is the most important and deepest result on 3-polytopes. This statement isn't repeated in the article body, and isn't explained. Is it important because it has applications (what are these?) or is it important because it is deep? Is it important as a result about polyhedra or as a result about 3-connected graphs? Can I learn about polyhedral combinatorics without encountering it or is it something I learn about in a first course?
    • Reworked the lead with a couple more sources to say something in that direction. —David Eppstein (talk) 17:20, 8 August 2021 (UTC)[reply]
      • Yes, that's the type of things I was looking for. Might be better in a context section in the body, though. (MOS:LEAD says Apart from basic facts, significant information should not appear in the lead if it is not covered in the remainder of the article.)
        • I think that, other than categorizing what kind of result it is (a classification theorem), the newly added claims (applications in proving other theorems and in graph drawing) all summarize material that can be found in the body of the article. —David Eppstein (talk) 22:15, 8 August 2021 (UTC)[reply]
          • OK, I see your point there.

Some further comments on content (style/presentation to follow later):

  • History and naming section: This isn't really about history or about naming. "Steinitz submitted a proof in 1916" isn't the entire history of the topic, and the existence of other theorems by Steinitz is more a question of disambiguation here and doesn't tell us since when this particular theorem has been called "Steinitz's theorem".
    • This was really intended as a disambiguation page, and didn't belong very well in this article. I moved it all to a new separate disambiguation page. The question of who first called it this name is really difficult to sort out in the absence of published sources specifically on that aspect of its history, because of the difficulty of searching pre-internet sources, the likelihood that a fair fraction of those sources will not be in English, the many ways that one could write a phrase equivalent to "Steinitz's theorem", and the difficulty of distinguishing phrases like that intended as descriptive phrases from phrases intended as names. —David Eppstein (talk) 22:46, 8 August 2021 (UTC)[reply]
      • I'm fine with not having a history section and with not discussing the naming unless you can find a book on the history of polyhedral combinatorics. While I'd love to read about the history and the historical context of the proofs, it is probably better to exercise restraint in making any claims of priority etc. here without much better sourcing. Found a history article that you might want to use: Grünbaum, Branko. Graphs of polyhedra; polyhedra as graphs. Discrete Math. 307 (2007), no. 3-5, 445–463. https://mathscinet.ams.org/mathscinet-getitem?mr=2287486
  • Proof: Is it worth explaining when the other proofs were found? Epifanov and Truemper are mentioned by name (without year), but "Lifting" and "Circle packing" do not mention any names or years.
    • Note that the part about Epifanov does not claim that Epifanov found the application of his reducibility theorem to polyhedra. That may have come later. The paper is in Russian at http://mi.mathnet.ru/dan31994 if you can read it (I can't), but the MR and zbl reviews describe it as purely about graphs, not polyhedra. Truemper credits Grünbaum for the application of this result to Steinitz's theorem. The history of the circle packing theorem is also complicated, and really belongs to that article rather than here. —David Eppstein (talk) 22:50, 8 August 2021 (UTC)[reply]
      • I can't read Russian, but I can read Cyrillic (I'm something like ru-0.5). Can't see any mention of Steinitz in there.
  • The German Wikipedia tells me that Steinitz himself gave three proofs in a 1934 book with Rademacher. Are these the same proofs that you show here?
    • I'm not familiar with that book and also don't read German but I strongly suspect it's three variations of induction proofs, rather than the three approaches (induction, lifting, and circle packing) described in this article. In particular the lifting proof depends heavily on the work of Tutte 1963 and would not be found in a 1934 publication. Similarly, I think the first work on circle packing was Koebe 1936. —David Eppstein (talk) 23:06, 8 August 2021 (UTC)[reply]
      • That makes sense. I'll still try to have a look at that book and will report back if I find anything surprising.
      • It's not written in the language of graph theory, which makes it difficult to read, but as I understand it, these are essentially just different variations of combinatorics/geometry that ultimately lead to an inductive argument. The only thing I'm wondering now is how the Y-Delta and Delta-Y transforms compare to Thomas Kirkman's face-splitting and vertex-splitting.
        • I don't think there are easy ways to transform the splitting operations into the YDY transformations, or vice versa. For one thing, you can build any planar graph with a linear number of vertex-splitting steps, but there is a nonlinear bound on YDY transformations. Do you have a reference that uses the splitting operations to prove Steinitz's theorem? —David Eppstein (talk) 23:17, 9 August 2021 (UTC)[reply]
          • No, I was just curious. From a casual observation, it looked like a similar type of operation.

Prose and detail comments:

  • Lead: it's not a 1922 "paper". Better to use "publication".
  • Proofs: 3-connectivity seems intuitively obvious (any vertex connected to only two other vertices should induce a "two-dimensional" piece of the polyhedron?) so maybe comment on at least the idea of the proof in addition to citing it from Balinski? Is the 3-connectivity true under weaker assumptions on the polyhedron than convexity?
    • It's not true for all non-convex polyhedra, under reasonably restrictive assumptions (topologically spherical, all faces simple polyhedra). It is true if for topologically-spherical polyhedra where pairs of faces to intersect in (empty, single vertex, or single edge) but to some extent that's just making a definition and then saying that it implies a slightly-rewritten version of itself. I swapped out the image of a non-convex polyhedron with a new one that shows some non-3-connected graphs. I also added a one-sentence summary of the proof of Balinski's theorem. —David Eppstein (talk) 23:17, 9 August 2021 (UTC)[reply]
      • OK, so my intuition was wrong, that's always helpful to know. I like the new image (in "Related results").
  • Induction: As Steinitz's (you say "Steinitz'" here, which I like, but I think the MOS likes "Steinitz's") proof uses very different (combinatorial, not graph-theoretical) language, you should probably cite the description of this proof to a modern source.
  • Induction section: The wye-delta article you link to is mostly about electric circuits, with the graph theory hidden deeply inside it. I'm not sure you need to change anything in the present article (you could potentially link to the very short "graph theory" section).
  • You could also mention here again that the original proof was not written in the language of graph theory.
  • Ω(n^3/2): jargon without a link. (Big_O_notation#The_Knuth_definition). But the "sometimes" essentially implies you mean the liminf is large.
  • the degree-two vertices that might be performed by this removal performed?
  • Lifting: each vertex is in the position given by the weighted sum of its neighbors sum->average? Or do you prefer "sum" because average sounds too much like positive weights / convex combination?
  • A picture of the frustrum that belongs to this graph could be nice, but only if it doesn't overwhelm the article.
  • Consider splitting the final sentence of the Lifting section. I don't quite understand what you say about the "incremental method" and the "a liftable planar drawing that does not have equal weights for all the interior edges": is it a good or a bad thing that we do not have equal weights?
    • Split long sentence and removed the part about the incremental method. I was under the impression that it allows more general outer faces, but it doesn't (only triangles). Really that reference is about a point from later in the article, on realizations with well-separated vertices and linear volume. —David Eppstein (talk) 19:04, 12 August 2021 (UTC)[reply]
  • Circle packing: Looks good.
  • Integer coordinates: Source for doubly exponential is a blog, not superb. What does the "graph drawing" reference say?
    • It only gives a single-exponential lower bound, not the double-exponential upper bound stated here. But Onn and Sturmfels also state the double-exponential upper bound, so I replaced the blog source by reusing that source. —David Eppstein (talk) 19:52, 12 August 2021 (UTC)[reply]
  • Equal slopes: As I understand it, this is an extra property that we get only under (much?) stronger assumptions on the type of graph. Are there other graphs than Halin graphs that have equal slope representation?
    • I think that such a representation necessarily comes from lifting a straight skeleton of a convex polygon and therefore necessarily comes from a Halin graph. Intuitively, one can't introduce new equal-slope faces higher up than the base because the edge they'd replace is already lower than that slope. But that's not a proof and I don't know of a source that explicitly says that (Incidentally, the Aichholzer et al source that we're using for this part is phrased in terms of trees and straight skeletons, not Halin graphs and polyhedra. The correspondence between straight skeletons and equal-slope polyhedral surfaces can be found in plenty of other sources. The equal-slope realization of Halin graphs is stated more explicitly in my paper "Treetopes and their graphs", credited to Aichholzer et al., but out of modesty I didn't add it as a source here. I can add it if you think I should.) —David Eppstein (talk) 19:52, 12 August 2021 (UTC)[reply]
      • I think what I'm looking for is a clearer statement linking the Halin graphs with the rest of the result. Basically, make it clear also for the less observant reader that Halin graphs are a special subclass of 3-connected plane graphs, and Steinitz's theorem for these graphs can be strengthened by asking for equal slopes.
  • Circle packing theorem: I don't like the links to Koebe and Thurston (and not to Andreev) very much, do you need them here?
  • The characterization involves edge weights, constrained by systems of linear inequalities. I don't quite know what is happening here.
  • Related results: "algorithmic Steinitz problem" could be italic as a definition? (I think there's some more like that). Or do we not do that here?
  • It is complete: Can you make it clearer (also to readers not clicking the link) that you are talking about complexity theory? Or explain in layman's (well, semi-layman's) terms what "complete for the existential theory of the reals" means?
  • Could you explain more what Lovasz's theorem is?
  • History: "cryptic", well, it's only cryptic if you expect graph theory I guess.
    • "Cryptic" was intended less to be about the fact that it was written in a different formalism, and more as a summary of Grünbaum's "The difficult chore of deciphering what this means is probably responsible for the long-lasting ignorance of this basic theorem about convex polyhedra. ... The formulation of Steinitz’s criteria is quite cumbersome." —David Eppstein (talk) 01:06, 13 August 2021 (UTC)[reply]
      • OK.

It's a very nice article overall. I'll leave you with my comments for now and will do a second pass then, but I don't think it will take much longer. —Kusma (talk) 16:09, 10 August 2021 (UTC)[reply]

Nice improvements. I hope I wasn't asking for something impossible with the Lovasz question. I found one other issue in your history edits: the Steiner reference doesn't look right. The publisher of the 1896 (not 1832) edition you link to isn't Fincke, but Wilhelm Engelmann in Leipzig. Also, the actual statement is not in the thing you link to, but in the second part, p. 144, question 77.
After writing the above, I found the actual 1832 Fincke edition: [1], where it is p. 316. Cite what you like, but don't mix them up. —Kusma (talk) 21:34, 13 August 2021 (UTC)[reply]

Table

[edit]
Rate Attribute Review Comment
1. Well-written:
1a. the prose is clear, concise, and understandable to an appropriately broad audience; spelling and grammar are correct. Prose and spelling are fine, and the article is understandable to an appropriately broad audience. Some parts are more difficult than others, but that is just natural, and readers with some understanding of mathematics should manage a large part of it.
1b. it complies with the Manual of Style guidelines for lead sections, layout, words to watch, fiction, and list incorporation. It does, and the lead is a good summary of the article.
2. Verifiable with no original research:
2a. it contains a list of all references (sources of information), presented in accordance with the layout style guideline. Fine.
2b. reliable sources are cited inline. All content that could reasonably be challenged, except for plot summaries and that which summarizes cited content elsewhere in the article, must be cited no later than the end of the paragraph (or line if the content is not in prose). Almost everything is high quality mathematics sources (save perhaps one blog for a statement that's not super important). I don't like MathWorld much, but its use here is fine.
2c. it contains no original research. Fine.
2d. it contains no copyright violations or plagiarism. Fine.
3. Broad in its coverage:
3a. it addresses the main aspects of the topic. History has been added.
3b. it stays focused on the topic without going into unnecessary detail (see summary style). Looks about right.
4. Neutral: it represents viewpoints fairly and without editorial bias, giving due weight to each. Fine
5. Stable: it does not change significantly from day to day because of an ongoing edit war or content dispute. Yes
6. Illustrated, if possible, by media such as images, video, or audio:
6a. media are tagged with their copyright statuses, and valid non-free use rationales are provided for non-free content. Thank you for creating these images!
6b. media are relevant to the topic, and have suitable captions. Good images illustrating the topic well, relevant and useful.
7. Overall assessment. A good article.

Simple graphs

[edit]

Should the statement of Steinitz Theorem specify a simple graph? See for example Lectures on Polytopes by Gunter Ziegler. Greenlinda (talk) 21:03, 25 August 2022 (UTC)[reply]

If we're being pedantic, we need to specify that we are talking about finite simple undirected 3-vertex-connected planar graphs. This might be appropriate in the "definitions" section. In the lead, clarity is more important than pedantry. —David Eppstein (talk) 00:06, 26 August 2022 (UTC)[reply]
I only asked because, as a novice to graph theory, I spent about 10 minutes confused by this before asking a friend, wondering, for example, if simple might be part of the definition of 3-vertex connected, while I did not hesitate to assume that the graphs were finite and undirected. But I understand the balance between brevity / clarity and completeness. Thanks for the article! Greenlinda (talk) 23:08, 26 August 2022 (UTC)[reply]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Steinitz%27s_theorem&oldid=1212703952"