User emil - MathOverflow

Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1

2012-05-14T15:31:09Z

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,

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$.

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$.

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.

The motivation is I would like to be able to compute 3-graph Lagrangians (see e.g. this paper) of arbitrary 3-graphs. (A 3-graph is a 3-uniform hypergraph.)

I would appreciate any pointers in the right direction...

Edit: I am only interested in obtaining exact answers. I know how to solve these problems numerically.

Why is edge-coloring less interesting than vertex-coloring?

2010-01-07T01:38:00Z

I was wondering why there is (apparently) much more research directed towards vertex-coloring than edge-coloring? Prima facie, it seems that edge-coloring is just as "natural" a thing to investigate.

I can think of a few reasons:

Vertex coloring is well behaved under deletion and contraction of edges.
Vertex colorability is closely linked to the cycle matroid.
Edge-coloring can be regarded as vertex-coloring restricted to line graphs.
Since Vizing's theorem (that the chromatic index of $G$ is either $\Delta(G)$ or $\Delta(G)+1$) edge-coloring has been solved (asymptotically).

But is it really true that edge-coloring is less interesting than vertex-coloring?

Answer by Emil for An Alternative to the Cook-Levin Theorem

2010-11-25T18:42:45Z

Yes, for example TMSAT (Turing Machine SAT):

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.$\}$

(Theorem 2.9 of Arora-Barak. See Chapter 2 draft: http://www.cs.princeton.edu/theory/index.php/Compbook/Draft#np)

It is quite easy to show that this problem is NP-complete!

Answer by Emil for Bound on the number of unlabeled cographs on n vertices

2010-09-06T13:12:24Z

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.

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.

I think this should give a $O(8^n)$ bound.

Answer by Emil for What is the relationship between "translation" and time complexity?

2010-07-17T23:24:36Z

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:

http://arxiv.org/abs/math/0702567

Decision problem restricted to inputs that satisfy some necessary condition.

2010-07-12T16:44:19Z

Consider the following decision problem:

Problem 1

INPUT: A graph G.

OUTPUT: YES if G is 3-colorable, NO if not.

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:

Problem 2

INPUT: A graph G that satisfies NC.

OUTPUT: YES if G is 3-colorable, NO if not.

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.

(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.)

Update

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.

Consider:

Problem 3

INPUT: A planar graph G.

OUTPUT: YES if G is 3-colorable, NO if not.

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:

Given an input string, determine if it represents a planar graph that is 3-colorable.

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.

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.)

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.

Answer by Emil for What are some good beginner graph theory texts?

2010-01-19T23:47:30Z

Wilson (many editions) - great to read quickly to get an overview.

Bondy and Murty (2008) - very clear, lots of stuff. My favorite book.

Diestel (2005) - clinical treatment.

Bollobas (1998?) - lots of stuff, but leaves a lot of gaps for the reader to fill.

West - quite good, not read much of it.

Regularizing graphs

2010-01-06T00:55:57Z

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, without increasing the maximum degree.

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.)

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?

Answer by Emil for Hamilton cycle decompositions of the complete graph

2010-01-03T20:06:12Z

In Two-factorizations of complete graphs it is stated that $K_9$ has 122 non-isomorphic Hamiltonian decompositions, and the corresponding number for $K_{11}$ is 3140 (EDIT: 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.)

Now you are interested in the labeled case, which may be easier. However I have not been able to find anything (on Google).

Answer by Emil for What introductory book on Graph Theory would you recommend?

2009-11-10T15:22:00Z

Robin Wilson's Introduction to Graph Theory 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.

Answer by Emil for Complexity of determining if two graphs have same cycle matroid?

2009-11-05T08:56:19Z

The following paper seems to show that this problem is polynomial equivalent to graph isomorphism (see section 5):

http://arxiv.org/abs/0811.3859

Answer by Emil for A name for a claw-graph with paths attached to it

2009-11-01T14:49:51Z

In this paper such graphs are referred to as "spiders" and "subdivisions of stars":

http://doi.wiley.com/10.1002/jgt.20244

Answer by Emil for What is the Tutte polynomial encoding?

2009-10-23T09:11:31Z

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.

Comment by Emil

2012-05-14T16:09:28Z

Thanks for the link! It looks like they are interested in numerical solutions though.

Comment by Emil

2012-05-14T16:07:11Z

Good point. However, I'm not really interested in the complexity of this problem.

Comment by Emil

2012-05-14T16:06:34Z

@Igor: no, the answer may not be rational (see page 10 of the linked paper). @Boris: thanks!

Comment by Emil

2011-08-06T11:42:10Z

Should this be tagged open-problem?

Comment by Emil

2010-11-25T19:43:35Z

@Peter, thanks!

Comment by Emil

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.

Comment by Emil

2010-11-06T12:27:27Z

Should be tagged co.combinatorics instead of pr.probability?

Comment by Emil

2010-09-19T21:33:01Z

Peter Cameron discussed these graphs in a blog post recently: cameroncounts.wordpress.com/2010/08/26/…

Comment by Emil

2010-09-07T19:27:04Z

I think Adam meant 2-vertex-connected, in which case the bowtie graph is not 2-connected.

Comment by Emil

2010-09-06T15:33:04Z

@JBL, thanks - I've corrected it.

Comment by Emil

2010-09-06T10:59:34Z

I don't understand the use of the term "recreational math". This seems to be a perfectly good graph theory question.

Comment by Emil

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.

Comment by Emil

2010-07-28T19:05:44Z

Wikipedia page is not bad: en.wikipedia.org/wiki/Cograph

Comment by Emil

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)$?

Comment by Emil

2010-07-17T19:46:33Z

Perhaps you should provide a link to the SO question (before you close this one).