User emil - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T14:53:38Z http://mathoverflow.net/feeds/user/1028 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/96909/finding-maximum-value-of-degree-3-homogeneous-polynomials-when-variables-sum-to-1 Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1 Emil 2012-05-14T15:31:09Z 2012-05-15T11:21:08Z <p>I would like to be able to find maximum values of degree-3 homogeneous polynomials, when the variables are non-negative real numbers that sum to 1. For example,</p> <p>For example, the maximum value of $xy^2$ subject to $x+y=1$, $x\ge0$, $y\ge0$, occurs when $x=1/3$ and $y=2/3$.</p> <p>And the maximum value of $xyz + xyw + xzw$ subject to $x+y+z+w=1$, $x,y,z,w\ge0$, occurs when $x=1/3$ and $y=z=w=2/9$.</p> <p>I have found that I can do many cases by hand (using Lagrange multipliers), but I would like to be able to do this computationally.</p> <p>The motivation is I would like to be able to compute 3-graph Lagrangians (see e.g. <a href="http://arxiv.org/abs/1110.4287" rel="nofollow">this paper</a>) of arbitrary 3-graphs. (A 3-graph is a 3-uniform hypergraph.)</p> <p>I would appreciate any pointers in the right direction...</p> <p><strong>Edit:</strong> I am only interested in obtaining exact answers. I know how to solve these problems numerically.</p> http://mathoverflow.net/questions/10996/why-is-edge-coloring-less-interesting-than-vertex-coloring Why is edge-coloring less interesting than vertex-coloring? Emil 2010-01-07T01:38:00Z 2010-11-29T19:34:57Z <p>I was wondering why there is (apparently) much more research directed towards vertex-coloring than edge-coloring? <em>Prima facie</em>, it seems that edge-coloring is just as "natural" a thing to investigate.</p> <p>I can think of a few reasons:</p> <ol> <li>Vertex coloring is well behaved under deletion and contraction of edges.</li> <li>Vertex colorability is closely linked to the cycle matroid.</li> <li>Edge-coloring can be regarded as vertex-coloring restricted to line graphs.</li> <li>Since Vizing's theorem (that the chromatic index of $G$ is either $\Delta(G)$ or $\Delta(G)+1$) edge-coloring has been solved (asymptotically).</li> </ol> <p>But is it really true that edge-coloring is less interesting than vertex-coloring? </p> http://mathoverflow.net/questions/37675/an-alternative-to-the-cook-levin-theorem/47361#47361 Answer by Emil for An Alternative to the Cook-Levin Theorem Emil 2010-11-25T18:42:45Z 2010-11-25T19:43:21Z <p>Yes, for example TMSAT (Turing Machine SAT):</p> <p>TMSAT = $\{ \langle \alpha, x, 1^n, 1^t \rangle : \exists u \in \{0,1\}^n$ such that $M_\alpha$ outputs 1 on input $\langle x,u \rangle$ within $t$ steps.$\}$</p> <p>(Theorem 2.9 of Arora-Barak. See Chapter 2 draft: <a href="http://www.cs.princeton.edu/theory/index.php/Compbook/Draft#np" rel="nofollow">http://www.cs.princeton.edu/theory/index.php/Compbook/Draft#np</a>)</p> <p>It is quite easy to show that this problem is NP-complete!</p> http://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices/37884#37884 Answer by Emil for Bound on the number of unlabeled cographs on n vertices Emil 2010-09-06T13:12:24Z 2010-09-06T15:32:23Z <p>A cograph on $n$ vertices can be created by starting with $n$ 1-vertex graphs and then going through a procedure of at each turn either (1) complementing a graph, or (2) replacing two of your graphs with their disjoint union, and stopping when you have one graph remaining.</p> <p>The number of ways that (2) can be done is the $n$th Catalan number, and at each stage you have the option of complementing.</p> <p>I think this should give a $O(8^n)$ bound.</p> http://mathoverflow.net/questions/32320/what-is-the-relationship-between-translation-and-time-complexity/32328#32328 Answer by Emil for What is the relationship between "translation" and time complexity? Emil 2010-07-17T23:24:36Z 2010-07-17T23:24:36Z <p>Your question reminded me of matroid problems. With these it is of great importance to specify how the input is given, as translating between input forms can increase the size of the input exponentially. There is a survey of this issue here:</p> <p><a href="http://arxiv.org/abs/math/0702567" rel="nofollow">http://arxiv.org/abs/math/0702567</a></p> http://mathoverflow.net/questions/31577/decision-problem-restricted-to-inputs-that-satisfy-some-necessary-condition Decision problem restricted to inputs that satisfy some necessary condition. Emil 2010-07-12T16:44:19Z 2010-07-13T11:47:21Z <p>Consider the following decision problem:</p> <blockquote> <p><strong>Problem 1</strong></p> <p>INPUT: A graph G.</p> <p>OUTPUT: YES if G is 3-colorable, NO if not.</p> </blockquote> <p>This is a well-known NP-complete problem. Now suppose that we have a necessary (but not sufficient) condition for a graph to be 3-colorable, called NC. Consider the following problem:</p> <blockquote> <p><strong>Problem 2</strong></p> <p>INPUT: A graph G that satisfies NC.</p> <p>OUTPUT: YES if G is 3-colorable, NO if not.</p> </blockquote> <p>Now suppose that it is not known whether NC can be determined in polynomial time. Can we say that Problem 2 is in NP? It seems to me that it should be, seeing as there is a succinct certificate for a YES answer.</p> <p>(However, I've been told by someone who I trust on other matters that this is a "promise problem" and not in NP, which is why I'm posting it here.)</p> <hr> <h2>Update</h2> <p>I'm not entirely happy with the answers below (although the subsequent discussions in the comments were useful), so I will attempt to answer the question myself.</p> <p>Consider:</p> <blockquote> <p><strong>Problem 3</strong></p> <p>INPUT: A planar graph G.</p> <p>OUTPUT: YES if G is 3-colorable, NO if not.</p> </blockquote> <p>Now, by the usual definitions, an NP problem is one where, from the set of all binary strings, certain ones (those in the "language") must be recognised. Now, it is not easy to come up with a way to represent planar graphs such that every binary string corresponds to a planar graph. So by convention, Problem 3 means the following:</p> <blockquote> <p>Given an input string, determine if it represents a planar graph that is 3-colorable.</p> </blockquote> <p>So by the same convention, Problem 2 defines an NP problem: Given an input string, determine if it represents a graph that satisfies NC that is 3-colorable.</p> <p>Now, the strings that should give "yes" answers are exactly the same as those that should give "yes" answers to Problem 1. So as NP problems, Problems 1 and 2 are exactly the same. (In other words, the languages they define are the same.)</p> <p>So to make Problem 2 useful, we need to cast it as a Promise problem, where the input is not all binary strings, but is restricted in some way. Posed in this form, it is not an NP problem.</p> http://mathoverflow.net/questions/12161/what-are-some-good-beginner-graph-theory-texts/12350#12350 Answer by Emil for What are some good beginner graph theory texts? Emil 2010-01-19T23:47:30Z 2010-01-19T23:47:30Z <p>Wilson (many editions) - great to read quickly to get an overview.</p> <p>Bondy and Murty (2008) - very clear, lots of stuff. My favorite book.</p> <p>Diestel (2005) - clinical treatment.</p> <p>Bollobas (1998?) - lots of stuff, but leaves a lot of gaps for the reader to fill.</p> <p>West - quite good, not read much of it.</p> http://mathoverflow.net/questions/10868/regularizing-graphs Regularizing graphs Emil 2010-01-06T00:55:57Z 2010-01-06T07:59:04Z <p>Let $G$ be a simple graph (undirected, no loops or parallel edges), with maximum degree $\Delta(G)$. I would like to add edges to the graph to make it regular, <em>without increasing the maximum degree</em>.</p> <p>In general this is not possible. (For example, take the 5-vertex graph formed by taking a triangle ($K_3$) and adding two pendant edges to different vertices.)</p> <p>However, what if we are also allowed to add vertices? I think I can see how to do it by creating many copies of the graph - so my question is: what is the least number of vertices we need to add?</p> http://mathoverflow.net/questions/10577/hamilton-cycle-decompositions-of-the-complete-graph/10616#10616 Answer by Emil for Hamilton cycle decompositions of the complete graph Emil 2010-01-03T20:06:12Z 2010-01-04T00:13:36Z <p>In <a href="http://www.cas.mcmaster.ca/~franek/journals/twofact.ps" rel="nofollow">Two-factorizations of complete graphs</a> it is stated that $K_9$ has 122 <em>non-isomorphic</em> Hamiltonian decompositions, and the corresponding number for $K_{11}$ is 3140 (<strong>EDIT</strong>: the actual figure is much more than this - see comment). I don't think they know any other values. (Sloane's database does not have any sequences with these numbers in.)</p> <p>Now you are interested in the labeled case, which may be easier. However I have not been able to find anything (on Google).</p> http://mathoverflow.net/questions/4836/what-introductory-book-on-graph-theory-would-you-recommend/4876#4876 Answer by Emil for What introductory book on Graph Theory would you recommend? Emil 2009-11-10T15:22:00Z 2009-11-10T15:22:00Z <p>Robin Wilson's <a href="http://www.amazon.com/Introduction-Graph-Theory-Robin-Wilson/dp/0582249937" rel="nofollow">Introduction to Graph Theory</a> is very easy to read - I read it over a weekend. I definitely recommend you give this a quick read before plunging into Bondy and Murty, Diestel or West.</p> http://mathoverflow.net/questions/4190/complexity-of-determining-if-two-graphs-have-same-cycle-matroid/4230#4230 Answer by Emil for Complexity of determining if two graphs have same cycle matroid? Emil 2009-11-05T08:56:19Z 2009-11-05T08:56:19Z <p>The following paper seems to show that this problem is polynomial equivalent to graph isomorphism (see section 5):</p> <p><a href="http://arxiv.org/abs/0811.3859" rel="nofollow">http://arxiv.org/abs/0811.3859</a></p> http://mathoverflow.net/questions/3668/a-name-for-a-claw-graph-with-paths-attached-to-it/3672#3672 Answer by Emil for A name for a claw-graph with paths attached to it Emil 2009-11-01T14:49:51Z 2009-11-01T14:49:51Z <p>In this paper such graphs are referred to as "spiders" and "subdivisions of stars":</p> <p><a href="http://doi.wiley.com/10.1002/jgt.20244" rel="nofollow">http://doi.wiley.com/10.1002/jgt.20244</a></p> http://mathoverflow.net/questions/724/what-is-the-tutte-polynomial-encoding/2061#2061 Answer by Emil for What is the Tutte polynomial encoding? Emil 2009-10-23T09:11:31Z 2009-10-23T09:11:31Z <p>No-one so far has mentioned matroids. The Tutte polynomial encodes some of the information from the cycle matroid of the graph. Two graphs with the same cycle matroid (and number of vertices) have the same Tutte polynomials. So if a graph property is not determined by the cycle matroid (and the number of vertices) then it can't be obtained from the Tutte polynomial.</p> http://mathoverflow.net/questions/96909/finding-maximum-value-of-degree-3-homogeneous-polynomials-when-variables-sum-to-1/96916#96916 Comment by Emil Emil 2012-05-14T16:09:28Z 2012-05-14T16:09:28Z Thanks for the link! It looks like they are interested in numerical solutions though. http://mathoverflow.net/questions/96909/finding-maximum-value-of-degree-3-homogeneous-polynomials-when-variables-sum-to-1/96913#96913 Comment by Emil Emil 2012-05-14T16:07:11Z 2012-05-14T16:07:11Z Good point. However, I'm not really interested in the complexity of this problem. http://mathoverflow.net/questions/96909/finding-maximum-value-of-degree-3-homogeneous-polynomials-when-variables-sum-to-1 Comment by Emil Emil 2012-05-14T16:06:34Z 2012-05-14T16:06:34Z @Igor: no, the answer may not be rational (see page 10 of the linked paper). @Boris: thanks! http://mathoverflow.net/questions/72161/graphs-with-few-induced-subgraphs Comment by Emil Emil 2011-08-06T11:42:10Z 2011-08-06T11:42:10Z Should this be tagged open-problem? http://mathoverflow.net/questions/37675/an-alternative-to-the-cook-levin-theorem/47361#47361 Comment by Emil Emil 2010-11-25T19:43:35Z 2010-11-25T19:43:35Z @Peter, thanks! http://mathoverflow.net/questions/37675/an-alternative-to-the-cook-levin-theorem/47361#47361 Comment by Emil Emil 2010-11-25T18:46:32Z 2010-11-25T18:46:32Z I'm having trouble putting the set brackets (braces) around the 0,1. If anyone knows how to fix it, please let me know, or edit it. http://mathoverflow.net/questions/45061/linear-ordering-of-color-balls Comment by Emil Emil 2010-11-06T12:27:27Z 2010-11-06T12:27:27Z Should be tagged co.combinatorics instead of pr.probability? http://mathoverflow.net/questions/39312/smallest-non-isomorphic-strongly-regular-graphs/39319#39319 Comment by Emil Emil 2010-09-19T21:33:01Z 2010-09-19T21:33:01Z Peter Cameron discussed these graphs in a blog post recently: <a href="http://cameroncounts.wordpress.com/2010/08/26/the-shrikhande-graph/" rel="nofollow">cameroncounts.wordpress.com/2010/08/26/&hellip;</a> http://mathoverflow.net/questions/37989/does-this-graph-exist/37991#37991 Comment by Emil Emil 2010-09-07T19:27:04Z 2010-09-07T19:27:04Z I think Adam meant 2-vertex-connected, in which case the bowtie graph is not 2-connected. http://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices/37884#37884 Comment by Emil Emil 2010-09-06T15:33:04Z 2010-09-06T15:33:04Z @JBL, thanks - I've corrected it. http://mathoverflow.net/questions/37665/degree-sequences-and-graph-enumeration Comment by Emil Emil 2010-09-06T10:59:34Z 2010-09-06T10:59:34Z I don't understand the use of the term &quot;recreational math&quot;. This seems to be a perfectly good graph theory question. http://mathoverflow.net/questions/36368/efficient-way-to-count-hamiltonian-paths-in-a-grid-graph-for-a-given-pair-of-vert Comment by Emil Emil 2010-08-22T18:13:04Z 2010-08-22T18:13:04Z Then answer is sometimes zero. Color the vertices like a chessboard. If there are an odd number of vertices you can't start and end on a white vertex. http://mathoverflow.net/questions/33228/simple-proof-that-these-graphs-are-perfect/33231#33231 Comment by Emil Emil 2010-07-28T19:05:44Z 2010-07-28T19:05:44Z Wikipedia page is not bad: <a href="http://en.wikipedia.org/wiki/Cograph" rel="nofollow">en.wikipedia.org/wiki/Cograph</a> http://mathoverflow.net/questions/33057/cover-time-of-weighted-graphs/33065#33065 Comment by Emil Emil 2010-07-23T23:36:29Z 2010-07-23T23:36:29Z So the question now seems to be: does the conditions on the weights given in the first paragraph cause the cover time to be $O(n^2\log n)$, rather than merely $O(n^3)$? http://mathoverflow.net/questions/32304/finding-the-major-and-minor-axes-of-an-ellipse-knowing-a-certain-point-p-and-its Comment by Emil Emil 2010-07-17T19:46:33Z 2010-07-17T19:46:33Z Perhaps you should provide a link to the SO question (before you close this one).