most recent 30 from http://mathoverflow.net 2013-05-20T01:27:24Z http://mathoverflow.net/feeds/user/18372 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84305/finding-optimal-vertex-partitioning-of-graphs-to-maximize-cohesion-and-minimize-c/84339#84339 Chad Musick 2011-12-26T21:54:28Z 2011-12-27T01:07:40Z

<p>This is a variant of graph clustering. The primary method of solving this problem is to decide on desirable parameters for the outcome and apply an energy (or force) model to approximate these. According to <a href="http://www.springerlink.com/content/bnkwtl1vanl222ln/" rel="nofollow">Noack</a>, many variants of this problem are NP-hard, but there are reasonable approximation methods.</p> <p>There is a nice piece of open-source software, <a href="https://gephi.org/features/" rel="nofollow">Gephi</a>, that automates clustering in visually beautiful ways. The graphviz project (originally from AT&amp;T) also implements some of these methods, but its focus is not on clustering and so it lacks some of the versatility in clustering that Gephi has. </p>

http://mathoverflow.net/questions/82936/is-there-a-known-method-for-finding-the-minimum-bridge-index-of-a-knot Chad Musick 2011-12-08T06:34:31Z 2011-12-19T20:19:23Z

<p>It is easy to establish an upper bound $n$ for the bridge index of a knot by producing a diagram with the knot in $n$-bridge position. </p> <blockquote> <p>Is there a known method to produce a reasonable lower bound on the bridge index? </p> </blockquote> <p>For example, knot <a href="http://katlas.org/wiki/Image:K11a1.gif" rel="nofollow">11a1</a> has at most bridge index $4$, because a $4$-bridge position of this knot can be drawn: DT code (42, 66, 44, 56, 54, 46, 64, 40, -38, 86, 94, 76, 100, 80, 82, 98, 74, 96, 84, -110, -108, -68, -104, -22, -34, -32, -24, -102, -26, -30, -36, -20, -106, 90, 122, 60, 50, -116, -10, -6, -120, -70, -112, -14, -2, -4, -12, -114, -72, -118, -8, 78, 92, 88, 16, 18, 62, 48, 52, 58, -28) gives one such diagram. What is known about methods to eliminate the possibility that this knot has a $2$-bridge or $3$-bridge projection?</p> <h3>Update</h3> <p>After posting this question I found a $3$-bridge projection (and because the knot is not rational, this is the lowest possible projection), given by DT code (12, 16, 58, 60, 14, -92, -90, -94, -32, -40, 120, 102, 108, 112, 98,116, 124, 106, 104, 122, 118, 100, 110, -26, -34, -38, -22, -42,-30, -96, -28, -44, -24, -36, 50, 18, 56, 62, 46, 64, 54, 20, 52, 66, 48, 128, 126, 114, -6, -74, -80, -86, -68, -88, -78, -76, -8, -4, -72, -82, -84, -70, -2, -10), but I am still interested in what is already known about establishing lower bounds more generally. Ryan Budney's suggestion of the Heegaard genus is a good one, but I haven't found a reference that shows this bound to be sharp.</p>

http://mathoverflow.net/questions/77569/tree-graph-restructuring/77572#77572 Chad Musick 2011-10-09T01:19:58Z 2011-10-09T01:19:58Z

<p>I think the following paper will probably answer your first question</p> <p>Henzinger, M., &amp; Valerie, K. (1997). Maintaining minimum spanning trees in dynamic graphs. <i>Automata, Languages and Programming, 1256</i>, 594-604. Doi: 10.1007/3-540-63165-8_214</p> <p>The answer to your second question can be found in several places. The page at <a href="http://treegraph.bioinfweb.info/Help/wiki/Rerooting" rel="nofollow">http://treegraph.bioinfweb.info/Help/wiki/Rerooting</a> has a visual explanation of one technique.</p>

http://mathoverflow.net/questions/77520/a-competitive-root-finding-game/77522#77522 Chad Musick 2011-10-08T09:57:45Z 2011-10-08T09:57:45Z

<p>This is not a complete answer, but I lack the reputation to post as a comment.</p> <p>The strategy must account for the winning/losing streak because the advantage of a smaller interval compounds. If both players choose 0.5 for the first turn, by the rules neither one wins. This highlights an ambiguity in the rules as stated. In the case of a tie, do the players know that they tied?</p> <p>Suppose after some number of moves, player X has a losing streak of N moves and first lost with an interval of length I. Then player X knows that player Y will have an interval no larger than $I^{-2(N-1)}$ if player Y is following a bisection strategy. Player X must make a guess with an interval smaller than this number to have any chance of winning, unless player Y is following some other strategy.</p> <p>Suppose instead that player X has a winning streak of N moves and first won with an interval of length I. Then player X knows that player Y must be guessing smaller and smaller intervals with each loss. As a result, player X can attempt to safeguard the streak by choosing non-bisecting moves. This requires also knowing how much time is left (as Will Sawin says) because the more turns left the more important it is not to start losing.</p> <p>Fascinating question. Have you tried any Monte Carlo simulations on it?</p>

http://mathoverflow.net/questions/84305/finding-optimal-vertex-partitioning-of-graphs-to-maximize-cohesion-and-minimize-c/84339#84339 Chad Musick 2011-12-29T00:40:14Z 2011-12-29T00:40:14Z

Yes, that's the one. It does give you a partition if you use the found clusters as your partition. The paper I linked to (Noack, &quot;An Energy Model for Visual Graph Clustering&quot;) gives an algorithm for separating clusters. Once you've done this, the partition places each node in the cluster that it's part of. If you're using this for actual software, you might want to weight the edges based on what type of connection they have; if you are only doing static analysis where all links are of the same type, this might not matter, but for things like ipc, it can make a significant impact.

http://mathoverflow.net/questions/82936/is-there-a-known-method-for-finding-the-minimum-bridge-index-of-a-knot/83894#83894 Chad Musick 2011-12-19T21:05:15Z 2011-12-19T21:05:15Z

Thanks. I had read Coward's paper before, but I hadn't seen Wilson's.

http://mathoverflow.net/questions/82936/is-there-a-known-method-for-finding-the-minimum-bridge-index-of-a-knot/82941#82941 Chad Musick 2011-12-19T08:49:50Z 2011-12-19T08:49:50Z

Thanks, I appreciate the thought.

http://mathoverflow.net/questions/4918/can-you-fool-snappea/81471#81471 Chad Musick 2011-11-22T06:49:41Z 2011-11-22T06:49:41Z

Yes, you are correct. I've edited the answer to reflect this. I'm using a different knot-drawing software, and it produced the correct projection and then assigned it the wrong DT code. Calculating the code by hand showed this mistake.

http://mathoverflow.net/questions/79136/reference-for-sparseness-of-incomparability-graphs-implying-sparseness-of-coverin Chad Musick 2011-10-26T23:47:05Z 2011-10-26T23:47:05Z

Looking at this again today, it doesn't seem all that direct to me. I think I see how to construct the argument from Frank's Theorem 3, but it requires a fair amount of care.

http://mathoverflow.net/questions/79136/reference-for-sparseness-of-incomparability-graphs-implying-sparseness-of-coverin Chad Musick 2011-10-26T06:45:11Z 2011-10-26T06:45:11Z

You might try: Andr&#225;s Frank, On chain and antichain families of a partially ordered set, Journal of Combinatorial Theory, Series B, Volume 29, Issue 2, October 1980, Pages 176-184, ISSN 0095-8956, 10.1016/0095-8956(80)90079-9. (<a href="http://www.sciencedirect.com/science/article/pii/0095895680900799" rel="nofollow">sciencedirect.com/science/article/pii/&hellip;</a>) The result is not exactly what you are looking for, but it seems to me that what you ask about is directly implied by it.

http://mathoverflow.net/questions/78157/covering-a-sphere-using-reflections-of-an-intersection-of-three-lunes/78173#78173 Chad Musick 2011-10-14T22:43:22Z 2011-10-14T22:43:22Z

I think the intent of the construction is this: Take the $2$-sphere in $\mathbb{R}^3$ given by $x^2 + y^2 + z^2 = 1$. Given distinct planes $ax + by + cz = 0$ and $dx + ey + fz = 0$, the portion of the $2$-sphere lying in the intersection of $ax + by + cz \geq 0$ and $dx + ey + fz \geq 0$ is a digon. If you take three planes that don't have a mutual line of intersection, you can obtain a $3$-sided piece of the $2$-sphere. For the $xy$, $yz$, and $xz$ this is the portion lying in one of the octants.

http://mathoverflow.net/questions/77846/local-variables-in-first-order-formulas/77852#77852 Chad Musick 2011-10-12T01:16:09Z 2011-10-12T01:16:09Z

You can find an explicit construction of this in Muchnick's &quot;Advanced Compiler Design &amp; Implementation&quot; in the section on static single-assignment form (SSA).

http://mathoverflow.net/questions/77804/maximal-number-of-edges-in-a-dag-when-we-bound-the-degree-of-the-nodes/77808#77808 Chad Musick 2011-10-11T13:43:06Z 2011-10-11T13:43:06Z

You might find &quot;DAG-width and parity games&quot; (Berwanger, Dawar, Hunter, and Kreutzer) helpful: <a href="http://www.springerlink.com/content/x3316wx248373vvk/" rel="nofollow">springerlink.com/content/x3316wx248373vvk</a>

http://mathoverflow.net/questions/77804/maximal-number-of-edges-in-a-dag-when-we-bound-the-degree-of-the-nodes Chad Musick 2011-10-11T11:45:52Z 2011-10-11T11:45:52Z

Should this DAG be a subgraph of some given graph?

http://mathoverflow.net/questions/77569/tree-graph-restructuring/77572#77572 Chad Musick 2011-10-09T20:42:48Z 2011-10-09T20:42:48Z

The case where the existing root is not being deleted is straightforward: simply reverse the parent-child relationship between the new node and its extant parent. The new root and the old root cannot share any descendants, because then there would have been a cycle in the tree. In the directed case, add a path from $v_i$ to $v_o$ to $T$, remove the link from the parent of $v_i$ to $v_i$ and break any cycles created.

http://mathoverflow.net/questions/77520/a-competitive-root-finding-game/77522#77522 Chad Musick 2011-10-09T05:24:24Z 2011-10-09T05:24:24Z

That makes it a much different problem than I was considering. I'll give it some more thought.