User sergey - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T08:36:53Z http://mathoverflow.net/feeds/user/10639 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/55002/maximal-clique-intersection-graphs/55009#55009 Answer by Sergey for Maximal clique intersection graphs Sergey 2011-02-10T10:25:51Z 2011-02-12T15:51:54Z <p>Hi,</p> <p>It is not an answer, just a comment. This site may be relevant: <a href="http://www.eprisner.de/Journey/CliqueGraphs.html" rel="nofollow">http://www.eprisner.de/Journey/CliqueGraphs.html</a> </p> <p>Everything changes drastically if you manage to use not clique intersection but clique incidence matrix in your decomposition. Then you immediately fall into the realm of perfect graphs.</p> <p>The rows of clique-incidence matrix $A$ of a graph $G$ are incidence vectors of (maximal) cliques and vertices. For perfect graphs (that are graphs not containing induced odd cycles of the length greater than three or their complement) these matrices have several nice properties with respect to packing and covering the vertices by the subsets --- maximal cliques. Formally, the polytope ${x : Ax\leq e, x\geq 0}$ ($e$ is a vector of all $1$') is integral iff $G$ is perfect. In particular, a lot of NP-hard in general problems (e.g. chromatic number) are polynomial for perfect graphs. But coumting is a more subtle matter.</p> http://mathoverflow.net/questions/24542/how-to-prove-that-a-set-of-facets-are-all-the-facets-of-a-convex-polytope/52763#52763 Answer by Sergey for How to prove that a set of facets are all the facets of a convex polytope. Sergey 2011-01-21T13:06:37Z 2011-01-21T13:06:37Z <p>Hi,</p> <p>The question itself and all answers seem to be "practice-oriented" but as far as the complexity status of the problem is concerned then you are speaking about famous L.Lovasz's "polytope- polyhedron question". Namely, to check whether a polytope given by vertices coincides with a polyhedron given by facets. Note, that the lengths of the vertex and, respectively, the facet descriptions may differ exponentially and thus we should speak about incremental polynomial algorithms. Say, if a polyhedron is given by facets you should find a new vertex in polynomial time with respect to the input and the length of the list of already calculated vertices. In this format the question is still open for (bounded) polytopes but is proved to be NP-hard for (unbounded) polyhedrons (see, <a href="http://portal.acm.org/citation.cfm?id=1109640" rel="nofollow">http://portal.acm.org/citation.cfm?id=1109640</a> and references therein)</p> http://mathoverflow.net/questions/30976/condition-number-for-ellipsoid-method-matrix/45178#45178 Answer by Sergey for Condition number for Ellipsoid method matrix Sergey 2010-11-07T15:52:09Z 2010-11-07T15:52:09Z <p>Hi,</p> <p>As far as I understand your question, a partial answer may be recovered from the Khachiyan's original covergence proof of the ellipsoid algorithm. Namely, Khachiyan used the volume as an intermadiate parameter and expressed it via, what he called, the thickness $r(E)$ that is equal to $\lambda_{min}$ of the current ellipsoid $E$. The following inequality holds $r(E_{next})\geq \frac{d}{d+1} r(E_{previous})$. And $\lambda_{max}$ can be upperbounded by the inequality $\lambda_{max-next}\leq 2^{\frac1{d^2}}\lambda_{max-previous}$. Thus, the condition number increases not faster than $[\frac{d}{d+1} 2^{\frac1{d^2}}]^n$. It seems that you can check this exponential rate in your toy example (just consider the plane case $d=2$ to simplify the computations). By the way, precisely the fact that the ellipsoid algorithm USUALLY operates according to the theoretical estimates is a main reason for claims of it's practical'' impracticallity. But it's another story.</p> <p>Sergey</p>