Mathematics desk
< January 27	<< Dec \| January \| Feb >>	January 29 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 28

Plausability of "Squidward" knot

In Home Sweet Rubble, from SpongeBob SquarePants season 8, Squidward Tentacles is tied into a support system for the titular character's failing house. If Squidward is viewed as an ideal "six-ended rope" (i.e. a point from which six ropes protrude which can stretch and bend (continuously) indefinitely away), then what possible "support systems" can he be tied into?

It might be easier to generalize in graph theory: Given a (simple) graph, a vertex v therein, and n at least 1, are there exactly n edge-disjoint simple paths (no edge used twice) rooted at v that cover the graph? (For n = 1 this is just the Euler path problem). It is clear that v must have degree at least n, but as shown in the cartoon, the degree can be greater as long as it is of the same parity as n (so in Squidward's case, an even number at least 6)--Jasper Deng (talk) 07:06, 28 January 2021 (UTC)[reply]

I am trying to get my (hardly stretchable) head around what problem is being defined here. Is it important that v is given? One may also wonder whether a given graph can be covered by any articulated n-star ("articulated" meaning that the "legs" may be multi-edge paths), or what the least such n (if any) is. I also do not understand the relationship with the submarine pineapple support system; is the latter supposed to correspond to the given graph? In that case, the original question is the converse of this graph-theoretical formulation. It is more like: given n, characterize the graphs that can be covered by an articulated n-star. (For n = 1, the connected graphs with zero or two vertices of odd degree.) --Lambiam 12:44, 28 January 2021 (UTC)[reply]

@Lambiam: You are correct about the graph representing Squidward's shape in the episode where each vertex is a place where one of his legs touches another, whether knotted or not. The use of v as part of the input then provides a complete graph-theoretical description of Squidward's shape. Some more elementary results can be drawn: every vertex with odd degree must represent the end of one of the edge-disjoint paths, so there can be no more than n such vertices (excepting possibly v itself). I already covered that the case n = 1 is the Euler path problem, but so is n = 2. If we had only required n edge-disjoint paths without a common end, then I think the condition that there be no more than n odd-degree vertices might also be sufficient, but the restriction to an n-articulated star makes the problem more interesting. Again, this is a necessary condition, and clearly isn't sufficient (consider trees or other "barely"-connected graphs). Also, for any subgraph of the graph not containing v, the number of paths entering must be at least the number of odd vertices in that subgraph plus the number of paths leaving. I would think the most natural algorithm for this problem would be based on max flow or breadth-first search.--Jasper Deng (talk) 05:35, 30 January 2021 (UTC)[reply]

A pointed graph is a pair (G, v), consisting of a finite connected graph G and one of its vertices v. Call such a pointed graph SQT-coverable if it can be covered by an n-articulate star rooted at v, where n equals the degree of v. Here is an algorithm that assigns a property, which I call prunability, to a pointed graph. Call a vertex even or odd according to its degree.

Algorithm: Start: If all vertices are even, terminate, reporting prunability. Otherwise, there is at least some odd vertex u other than v. If a path connects u and v, remove the path and repeat from the start. Otherwise, terminate, reporting non-prunability.

(The sum, over all vertices, of their degrees equals twice the number of edges, so there can be no lone odd vertex. Since each step removes one or more edges, the process always terminates.)

Conjecture: (G, v) is SQT-coverable iff (G, v) is prunable.

I have not attempted to prove this. When started with a SQT-coverable pointed graph, not all intermediate graphs are necessarily also SQT-coverable, since they can fall apart by edge removal. I think though SQT-coverability is preserved if connected components that get detached but have only even vertices are instantly deleted in a normalizing operation. Then after the first step the first termination condition equivales: no edges are left. --Lambiam 16:29, 30 January 2021 (UTC)[reply]

@Lambiam: I think this notion of pruneability is not well-defined, because pruning a path's edges could remove the edges needed by other paths, and that can be problematic. Consider the graph with points a, b, c, d, u, v, with edges (v, a), (v, b), (v, c), (a, b), (a, c) (a, u), (b, u), (u, d). Clearly this graph is SQT-coverable with paths (v, b), (b, u), (u, d); (v, a), (a, b); (v, c), (c, a), (a, u). But if we happen to choose the path (v, b), (a, b), (a, u) first, then this leaves d out as an odd-degree vertex in a separate connected component. Something has to be done to inform our choice of path.--Jasper Deng (talk) 06:18, 31 January 2021 (UTC)[reply]

Max-flow seems to get us rather far: assign every edge unit capacity and find a max-flow from v to every odd-degree vertex. This is guaranteed to generate n edge-disjoint paths or otherwise prove that there do not exist n such paths. But even if it does find n edge-disjoint paths, they need not cover the graph. The question then would be whether these paths can be extended to cover the remaining edges.--Jasper Deng (talk) 06:53, 31 January 2021 (UTC)[reply]

I think this is the solution we want, actually.

Algorithm: Start: Count the number of odd vertices; let this be known as k. If k > n then halt and output false (not SQT-coverable), otherwise run max-flow from v to all odd-degree vertices; let that flow be known as f. Then output the result of f == k.

Proof of correctness: Every odd vertex must terminate a path from v and we are limited to n such paths, and max-flow produces the greatest number possible of edge-disjoint paths (up to k), so clearly the graph is not SQT-coverable if k > n or f < k. Otherwise, if f == k, then the flow can be easily extended to a set of edge-disjoint paths to every odd vertex, and each odd-degree vertex terminates exactly one of these paths, so deleting the edges of the flow leaves only even-degree vertices in every connected component. Every connected component thus has an Euler tour, and if k == n then none of those paths pass through v and so every such Euler tour can be simply inserted into any path touching it, while if k < n then there must be edges from v that are unused and an Euler tour including said edges. Clearly the number of such edges remaining must be even (as there can be no lone odd-degree vertex) and the Euler tour is one or more cycles including v; each such cycle can then be covered by a pair of paths from v that coterminate somewhere else in the cycle. Since this uses every edge emanating from v, we have that the number of such paths plus k is equal to n and the graph is SQT-coverable.

In the cartoon, although we are not shown the whole knot, we know that Squidward's form as depicted is impossible because I count at least ten odd-degree vertices in that graph, while we have n = 6. Squidward actually has his legs cross over his face, but the above algorithm still works in the case that some paths cross v–just take the max flow as before, and after n paths have been created as above, augment any paths with Euler cycles through v.--Jasper Deng (talk) 07:34, 31 January 2021 (UTC)[reply]

In the standard formulation of the max-flow problem, the edges of the network are directed. I assume here they should be bidirectional, as if each edge of the graph is a pair of directed edges in the flow network (each with unit cost). Also, the sink is a single vertex, but this can be modelled by adding a dummy sink vertex to which all odd vertices other than v are connected by an unlimited-capacity edge. A minor remark: If, at the Start, k and n do not have the same parity, the algorithm can also terminate and report non-SQT-coverability. --Lambiam 13:55, 31 January 2021 (UTC)[reply]

I'm guessing Spongebob's house has nothing to do with this problem. It might be better for you to watch the episode, I guess. Eridian314 (talk) 14:32, 28 January 2021 (UTC)[reply]

Who is the "you" referred to, and "better" in what respect? --Lambiam 15:10, 28 January 2021 (UTC)[reply]

You is referring to Lambiam,and "Better" means you would have a visual representation. Sorry if I was unclear. — Preceding unsigned comment added by Eridian314 (talk • contribs) 19:18, 28 January 2021 (UTC)[reply]

For future reference, there is a convention on talk pages that when you react to a contribution in a thread, the reaction is indented one level deeper. See Help:Talk pages § Indentation. Also, please always identify yourself by closing off with ~~~~; see Help:Talk pages § Identifying yourself. (The Reference desk pages are, strictly speaking, not talk pages, but we follow the general talk page guidelines here, as noted at Wikipedia:Reference desk/Guidelines § Talk page guidelines.) By the way, I was more interested in the graph-theoretical problem than in the state and preservation of the fictional dwelling of a cartoon character. --Lambiam 20:16, 28 January 2021 (UTC)[reply]

It's got to be infinite, assuming his tentacles can stretch to an unlimited degree. You could just keep knotting and knotting any combination of them, maybe even including overhand knots on single tentacles or leaving out a tentacle entirely, so there's no limit to what can be made. Red Panda 25 21:09, 3 February 2021 (UTC)[reply]

What is "it" that's got to be infinite? The plausability? Try covering this graph of six vertices and five edges:

\rangle \!\!\!-\!\!\!\langle ~.

--Lambiam 22:52, 3 February 2021 (UTC)[reply]

How to understand Timeline of mathematics ?

Recent changes of Riemann hypothesis#Numerical calculations didn't make list in Timeline of mathematics. I was confused why recent development of Riemann hypothesis#Numerical calculation is missing in Timeline of mathematics. Rizosome (talk) 16:22, 28 January 2021 (UTC)[reply]

Two things. First, improving articles is entirely a volunteer effort, to which anyone who can consult Wikipedia can also contribute. If an improvement has not been made, it is because no one who saw the possibility of an improvement volunteered their effort to realize it. But there are advances in mathematics every day, and we should include only the most significant ones]. One may wonder if the advance made by Platt & Trudgian is important enough to merit inclusion. As far as I can see it has not been published in a peer-reviewed journal. It does not even have an article of its own on Wikipedia, but merely a line in a table. --Lambiam 17:05, 28 January 2021 (UTC)[reply]

@Rizosome: I have replaced obscured ULRs in your question with clear wikilinks to our article. --CiaPan (talk) 10:37, 2 February 2021 (UTC)[reply]

Because unless a counterexample is found, more zeroes getting checked is not important enough to be included in timeline of mathematics, since more zeroes getting checked with no counterexample found doesn't change the unresolved status of the Riemann hypothesis. —SeekingAnswers (reply) 07:31, 3 February 2021 (UTC)[reply]