User andr&#225;s salamon - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T20:46:09Z http://mathoverflow.net/feeds/user/7252 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/132775/do-right-profiles-determine-graphs-up-to-isomorphism Do right-profiles determine graphs up to isomorphism? András Salamon 2013-06-04T20:21:51Z 2013-06-05T01:34:57Z <p>For graphs $G$ and $H$, let $h(G,H)$ denote the number of graph homomorphisms from $G$ to $H$. Fix some enumeration $G_1,G_2,\ldots$ of (isomorphism classes of) the set $\mathbf{D}$ of finite graphs, which contains only one representative from each isomorphism class. The <em>right $\mathbf{D}$-profile</em> of a graph $G$ is the infinite vector $(G \to \mathbf{D}) := (h(G,G_1),h(G,G_2),\dots)$.</p> <blockquote> <p>Is it true that $(G\to \mathbf{D}) = (H\to \mathbf{D})$ iff $G \simeq H$?</p> </blockquote> <p>The analogous left-profile is important in the theory of graph limits. Lovász showed that $(\mathbf{D}\to G) = (\mathbf{D}\to H)$ iff $G \simeq H$.</p> <ul> <li>L. Lovász, <em>Operations with structures</em>, Acta Mathematica Hungarica <strong>18</strong>(3), 1967, 321–328. doi:<a href="http://dx.doi.org/10.1007/BF02280291" rel="nofollow">10.1007/BF02280291</a> (<a href="http://www.cs.elte.hu/~lovasz/scans/opstruct.pdf" rel="nofollow">reprint</a>)</li> </ul> <p>It is also possible to restrict $\mathbf{D}$ to be a smaller set, for instance just the complete graphs. In this case, right-profile equivalence implies that $G$ and $H$ have the same chromatic polynomials. A conjecture of Bollobás, Pebody and Riordan about the chromatic polynomial implies that this is enough to show isomorphism for almost all graphs, although they also showed that it is likely to be nontrivial to construct examples of non-isomorphic graphs $G$ and $H$ which have the same right-profiles with respect to the set of complete graphs.</p> <p>One can also ask whether there is a set of target graphs (strictly smaller than the set $\mathbf{D}$ of all graphs) that can be used to determine graph isomorphism; clearly this would imply my question. If such a set is well-known, then I would appreciate a hint or pointer.</p> <ul> <li>B. Bollobás, L. Pebody, O. Riordan, <em>Contraction-deletion invariants for graphs</em>, JCTB <strong>80</strong>, 2000, 320–345. doi:<a href="http://dx.doi.org/10.1006/jctb.2000.1988" rel="nofollow">10.1006/jctb.2000.1988</a></li> </ul> <p>There are at least two related MO questions: <a href="http://mathoverflow.net/questions/11631/complete-graph-invariants" rel="nofollow"><em>Complete graph invariants?</em></a> and <a href="http://mathoverflow.net/questions/52141/invariants-that-might-determine-graph-up-to-isomorphism" rel="nofollow"><em>Invariants that might determine a graph up to isomorphism</em></a> although these address a somewhat different question.</p> http://mathoverflow.net/questions/129142/weakest-choice-principle-required-for-robertson-seymour-graph-minor-theorem Weakest choice principle required for Robertson-Seymour Graph Minor Theorem? András Salamon 2013-04-29T18:52:43Z 2013-04-30T12:04:44Z <p>The main <a href="https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem" rel="nofollow">Robertson-Seymour Theorem</a> states that finite graphs form a <a href="https://en.wikipedia.org/wiki/Well-quasi-ordering" rel="nofollow">well-quasi-ordering</a> under the <a href="https://en.wikipedia.org/wiki/Graph_minor" rel="nofollow">graph minor</a> relation. In other words, in every infinite set of finite graphs, there exist two graphs $G$ and $H$ such that $G$ is a minor of $H$.</p> <p>My question is:</p> <blockquote> <p>What is a weakest consequence $C$ of the Axiom of Choice that is sufficient in ZF to imply the Graph Minor Theorem?</p> </blockquote> <p>A little more precisely, what is a sentence $C$ of an appropriate logic (such as a form of second-order logic) such that:</p> <ol> <li>$C$ is known to be a theorem of ZFC,</li> <li>the Graph Minor Theorem is a theorem of ZF+$C$, and</li> <li>there is no known sentence $D$ that is a theorem of ZF+$C$ with the Graph Minor Theorem being a theorem of ZF+$D$?</li> </ol> <p>Ideally $C$ should be one of the already studied <a href="http://consequences.emich.edu/conseq.htm" rel="nofollow">consequences of AC</a>, and the quantification over "known" $D$ can also be restricted to such consequences.</p> <hr> <h2>Discussion</h2> <p>Another way to make my question precise would be to say that it is about the "first form" of the Graph Minor Theorem, rather than the "second form", in analogy with <a href="http://cs.nyu.edu/pipermail/fom/2008-September/013050.html" rel="nofollow">Ali Enayat writing about König's Lemma</a>. Forster and Truss showed that König's Lemma is equivalent to a rather weak choice principle:</p> <blockquote> <p>Every countably inﬁnite family of ﬁnite non-empty sets has a choice function.</p> </blockquote> <p>and I am asking which choice principle is a weakest one that is known to be sufficient to prove the Graph Minor Theorem: some stronger form of choice seems to be needed than for König's Lemma.</p> <ul> <li>T. E. Forster and J. K. Truss, <em>Ramsey's theorem and König's Lemma</em>, Archive for Mathematical Logic <strong>46</strong>, 2007, 37–42. doi:<a href="http://dx.doi.org/10.1007/s00153-006-0025-z" rel="nofollow">10.1007/s00153-006-0025-z</a></li> </ul> <p>I am waiting for the following possibly relevant paper, although hopefully something has been written about this in the intervening 26 years:</p> <ul> <li>H. Friedman, N. Robertson, and P. D. Seymour, <em>The metamathematics of the graph minor theorem</em>, in (S. G. Simpson, ed.) Logic and Combinatorics, Contemporary Mathematics <strong>65</strong>, AMS, 1987, 229–261.</li> </ul> <p>I am also aware of Timothy Chow's <a href="http://cstheory.stackexchange.com/a/4031/109" rel="nofollow">answer to a question of Ryan Williams</a> which suggests rephrasing the Graph Minor Theorem as a statement of arithmetic (which therefore can be proved in ZF, with no notion of choice required). However, I find it unsatisfactory to finesse away choice by only allowing graphs over vertices from $\mathbb{N}$, and encoding the graph minor relation as a particular relation over the natural numbers, about which we then ask the whether a particular arithmetical sentence is true. To my mind, the key difficulty seems to be precisely that if we don't have canonization, then these questions require additional machinery. (In fact, I would naively be tempted to use $C$ and $D$ as measures of just what we gain from canonization, in some sense.)</p> <p><a href="http://www.cs.nyu.edu/pipermail/fom/2013-April/017224.html" rel="nofollow">Harvey Friedman recently commented</a>:</p> <blockquote> <p>wqo statements, which are Pi-1-1. E.g., Kruskal's Theorem, graph minor theorem, Hilbert's basis theorem (appropriately formalized), etcetera. These are equivalent over RCA_0 to the well orderedness of familiar ordinal notations (in the case of GMT, the exact ordinal has not been determined, but has been determined for the important restriction to graphs of finite tree width).</p> </blockquote> <p>Hence, I expect that we currently do not know $C$ such that ZF+$C$ can prove GMT, while ZF+GMT can also prove $C$. But surely <em>something</em> is known about how "strong" a notion is needed? For instance, which choice principle is Friedman referring to above in the bounded tree-width case? This would suggest a candidate for $D$.</p> <p>(See also a <a href="http://www.cs.nyu.edu/pipermail/fom/2013-April/017228.html" rel="nofollow">related question by Joe Shipman</a>.)</p> http://mathoverflow.net/questions/127773/in-szemeredis-regularity-lemma-how-many-blocks-are-in-the-partition In Szemerédi's Regularity Lemma, how many blocks are in the partition? András Salamon 2013-04-16T23:49:03Z 2013-04-17T11:03:10Z <p>Suppose $G = (V,E)$ is a directed graph. For sets $A$ and $B$ of vertices of $G$, let $d(A,B) = |(A \times B) \cap E| / (|A||B|)$ denote the edge density between $A$ and $B$, and say that the pair $A,B$ is $\epsilon$-<em>regular</em> if $$|d(X,Y) - d(A,B)| \lt \epsilon$$ whenever $X \subseteq A, Y \subseteq B$, $X$ contains more than an $\epsilon$-fraction of the vertices of $A$, and $Y$ contains more than an $\epsilon$-fraction of the vertices of $B$. An <em>equipartition</em> is a partition with the sizes of blocks of the partition differing pairwise by at most 1.</p> <p>Szemerédi's Regularity Lemma can then be stated as:</p> <blockquote> <p>For any $\epsilon > 0$, there exists $M(\epsilon)$ such that for every graph $G=(V,E)$ there is some $k\le M(\epsilon)$ and an equipartition $V = V_1 \cup \ldots \cup V_k$ in which each block $V_i$ contains at most $\lceil \epsilon |V|\rceil$ vertices, and having the property that for all but at most $\epsilon k^2$ of the pairs $(i,j)$, the pair $V_i, V_j$ is $\epsilon$-regular.</p> </blockquote> <p>Do we have any bounds or asymptotics for how $M(\epsilon)$ behaves as a function of $\epsilon$?</p> <p>I vaguely recall having read a comment that $M(\epsilon)$ is likely to be extremely large, making the Regularity Lemma only useful for truly large graphs. But I have not been able to find this assessment again, so a pointer would be appreciated. (I did check Terence Tao's exposition again, and some of the more obvious references.)</p> http://mathoverflow.net/questions/117415/old-books-still-used/117610#117610 Answer by András Salamon for Old books still used András Salamon 2012-12-30T10:31:50Z 2012-12-30T10:31:50Z <p>N. G de Bruijn's <em>Asymptotic methods in analysis</em> is still the best reference for the topic. The current 1981 Dover reprint edition is largely unchanged since the 1958 first edition.</p> http://mathoverflow.net/questions/116275/simple-lower-bounds-for-bell-numbers-number-of-set-partitions Simple lower bounds for Bell numbers (number of set partitions)? András Salamon 2012-12-13T13:32:51Z 2012-12-28T14:22:00Z <p>The $n$-th Bell number $B_n$ represents the number of distinct partitions of a set with $n$ distinguished elements. It can be expressed as the infinite sum $B_n = (1/e)\sum_{k=1}^{\infty} (k^n/k!)$, which is also the $n$-th moment of a Poisson distribution with mean $1$. The first few values are known precisely; the Bell numbers form <a href="https://oeis.org/A000110" rel="nofollow">OEIS sequence A000110</a>. There are also several asymptotic expressions, but for an application I need lower bounds.</p> <p>Write $\log x$ for $\log_2 x$.</p> <blockquote> <p>For $n \ge 5$, is it true that $B_n \ge (n/\log n)^n$?</p> </blockquote> <p>Denote the set with elements $1,2,\dots,n$ by $[n]$. Since a partition of $[n]$ has at most $n$ blocks (equivalence classes), each partition of $[n]$ can be obtained via some function $f$ mapping $[n]$ to $[n]$, by regarding $f(i)$ as a name for the partition containing the number $i$. Many different names are possible for the same partition, so $B_n &lt; n^n$, as an easy but crude upper bound.</p> <p>It is possible to show tighter bounds. For convenience, when $n \ge 2$ we can express $B_n$ in terms of another sequence $c_n$ as $B_n = \left(\frac{c_n n}{\log n}\right)^n$. It seems that $\log c_n \ge -1.5$ for all integers $n \ge 2$, again by just counting functions (although a slightly more involved argument is required than for the trivial upper bound). Moreover, for any $\epsilon > 0$, this argument then also shows that $\log c_n \ge -(1+\epsilon)$ for all large enough $n$ (where the threshold for $n$ grows as $\epsilon$ becomes smaller). By a result of Berend and Tassa, it already follows that $\log c_n &lt; 0.1924$ for all positive $n$, and they state that from an asymptotic argument of de Bruijn it follows that $\log c_n > -0.914$ for all large enough $n$. My question is then whether the stronger bound $\log c_n \ge 0$ holds for $n \ge 5$. Note that the desired inequality fails for $n \le 4$, but can be verified numerically for small values $5\le n \le 26$ via the table of Bell numbers, and for slightly larger values (up to about 100) via computer algebra by computing finite partial sums.</p> <p>Consider a function $f \colon [n] \to [n]$. This induces a partition via the equivalence relation $\equiv_f$ defined as $i \equiv_f j$ iff $f(i) = f(j)$. As above, the function does not uniquely determine the induced partition. Another way to think about the question is then: can every function $[n] \to [\lceil n/\log n \rceil - 1]$ be mapped to a unique partition, for $n \ge 5$? (But note that this is a slightly different requirement, due to rounding.)</p> <ul> <li>Daniel Berend and Tamir Tassa, <a href="http://www.math.uni.wroc.pl/~pms/files/30.2/Article/30.2.1.pdf" rel="nofollow"><em>Improved Bounds on Bell Numbers and on Moments of Sums of Random Variables</em></a>, Probability and Mathematical Statistics <strong>30</strong>(Fasc. 2), 185–205, 2010.</li> <li>Donald Knuth, <em>The Art of Computer Programming</em>, Vol. 4A, Section 7.2.1.5. Addison-Wesley, 2011. (ISBN 0-201-03804-8; this section also appears in Fascicle 3, 2005, ISBN 0-201-85394-9)</li> </ul> http://mathoverflow.net/questions/116275/simple-lower-bounds-for-bell-numbers-number-of-set-partitions/116371#116371 Answer by András Salamon for Simple lower bounds for Bell numbers (number of set partitions)? András Salamon 2012-12-14T13:22:28Z 2012-12-14T13:22:28Z <p>On further reflection, it seems the answer is no.</p> <p>By considering the most significant terms in the asymptotic analysis of de Bruijn, and arguing that they dominate the other terms for large enough $n$, it seems possible to show that for every $\epsilon > 0$, there is some threshold $n_0 = n_0(\epsilon)$ such that $$-0.9139\dots &lt; \log c_n &lt; -0.9139\dots + \epsilon$$ for all $n \ge n_0$. Hence my proposed inequality cannot be true.</p> <p>(Here the mysterious constant $-0.9139\dots$ is just $\log_2\;\log_2 e - \log_2 e = -1/\ln 2 - \ln\;\ln 2/\ln 2$.)</p> <p>It would be interesting to establish precisely for which range of $n$ the simple expression $\log c_n \ge 0$ does hold.</p> http://mathoverflow.net/questions/114454/name-for-this-generalized-pigeonhole-principle Name for this generalized pigeonhole principle? András Salamon 2012-11-25T21:35:28Z 2012-11-26T00:10:54Z <p>For a set $X$, let $|X|$ denote its cardinality. A block of a partition is a non-empty element of the partition.</p> <blockquote> <p>Let $P$ and $Q$ be two partitions of a set $X$. If $|P| &lt; |Q|$ then $P$ contains a block $B$ which intersects two distinct blocks of $Q$.</p> </blockquote> <p>What is this principle called?</p> <p>The proof is immediate for finite $X$, and is an easy consequence of the Axiom of Choice for infinite $X$. I am interested in using this result, and would like to refer to its proper name and to cite it correctly. Jech's <em>Set Theory</em> and several online sources don't seem to mention this result. In particular the <a href="http://consequences.emich.edu/conseq.htm" rel="nofollow">Consequences of the Axiom of Choice project</a> doesn't seem to list it (at least not in this specific form).</p> <p>I would also be interested to know whether this principle is equivalent to some known consequence of the Axiom of Choice.</p> http://mathoverflow.net/questions/110663/survey-of-finite-axiomatizability-for-relational-theories Survey of finite axiomatizability for relational theories? András Salamon 2012-10-25T14:06:31Z 2012-10-25T15:44:40Z <p>An $L$-theory $T$ is finitely axiomatizable if there is a finite set $A$ of $L$-sentences with the same consequences as $T$, i.e. such that $M \models T$ iff $M \models A$ for every $L$-structure $M$. (Here $L$ is a first-order language, and I am mostly interested in languages with relational symbols and no function symbols.)</p> <blockquote> <p>Is there a survey of ways to show that finite axiomatizability holds or does not hold?</p> </blockquote> <p>The obvious way to establish that a theory is finitely axiomatizable is by (1) constructing a finite set of $L$-sentences $A$ and (2) proving that $A$ is a set of axioms for $T$. For finite axiomatizability, I am especially interested in any results that may help when it is difficult to establish part (2), even when given a likely candidate set of axioms $A$.</p> <p>For theories that are not finitely axiomatizable, I am thinking of results such as a theorem of Cherlin, Harrington and Lachlan, which is summarized by Theorem 12.2.18(a) in Hodges' <em>Model Theory</em> as:</p> <blockquote> <p>If $T$ is $\omega$-stable and $\omega$-categorical, then $T$ is not finitely axiomatizable.</p> </blockquote> <p>or a basic result such as Theorem 5.9.2 in Jezek's <em>Universal Algebra</em>:</p> <blockquote> <p>A class $K$ of $L$-structures is finitely axiomatizable iff both $K$ and the complement of $K$ in the class of all $L$-structures are axiomatizable.</p> </blockquote> <p>Finite axiomatizability is a rather natural notion, so it seems unlikely to me that there is no good source of results that can be used as tools to establish or deny it. So I am probably either missing some classic result (perhaps relating finite axiomatizability to recursive axiomatizability a la results of Kleene or Craig and Vaught for finite axiomatizability using additional predicates), or am not aware of one of the multitude of classic texts which exist but are difficult to locate via online searches. Any pointers would therefore be welcome!</p> <p><em>Edit</em>: I am slightly aware of the work in universal algebra that relates a finite basis of equations to properties of the lattice of congruences of the variety. A nice survey along these lines is by Maróti and McKenzie. However, my main interest is relational languages (and arbitrary axioms). This is in contrast to (usually functional) languages with equational (or quasi-equational) bases, which are sets of universal Horn sentences.</p> <ul> <li>Cherlin, G., Harrington, L., and Lachlan, A. H. $\aleph_0$-<em>categorical</em>, $\aleph_0$-<em>stable structures</em>, Annals of Pure and Applied Logic <strong>28</strong>(2), 1985, 103–135. <a href="http://dx.doi.org/10.1016/0168-0072%2885%2990023-5" rel="nofollow">doi:10.1016/0168-0072(85)90023-5</a></li> <li>Hodges, W. <em>Model Theory</em>. Cambridge University Press, 1993.</li> <li>Ježek, J. <em>Universal Algebra</em> (First edition, April 2008). (<a href="http://www.karlin.mff.cuni.cz/~jezek/ua.pdf" rel="nofollow">PDF version</a>)</li> <li>Maróti, M. and McKenzie, R. <em>Finite Basis Problems and Results for Quasivarieties</em>, Studia Logica <strong>78</strong>, 2004, 293–320. <a href="http://dx.doi.org/10.1007/s11225-005-3320-5" rel="nofollow">doi:10.1007/s11225-005-3320-5</a> (<a href="http://www.math.u-szeged.hu/~mmaroti/pdf/2004%20Finite%20basis%20problems%20and%20results%20for%20quasivarieties.pdf" rel="nofollow">reprint from author</a>)</li> </ul> http://mathoverflow.net/questions/101873/a-ramsey-like-lower-bound A Ramsey-like lower bound? András Salamon 2012-07-10T18:21:44Z 2012-07-10T21:06:58Z <blockquote> <p>Does there exist a graph $G$ which cannot be properly vertex-coloured with 3 colours (i.e. $G$ has chromatic number at least 4), such that for every graph $H$, if $H$ contains a triangle but there is no graph homomorphism from $G$ to $H$, then $H$ must contain at least as many vertices as $G$?</p> </blockquote> <p>This question arose from an application in computational complexity. Any pointers to similar results would be welcome, or a hint if this is trivial. I am familiar with Hell and Nešetřil's textbook <em>Graphs and Homomorphisms</em> and the classic constructions of rigid graphs by Chvátal et al. and Nešetřil/Rödl, but am not an expert in graph theoretic combinatorics.</p> <h2>Motivation</h2> <p>In some sense, this problem seeks a lower bound on the size of graphs $H$ which contain a triangle but which are also not homomorphic images of $G$. This compares to the usual Ramsey requirement, which can be phrased in terms of bounding the size of graphs which guarantee the presence of large enough complete subgraphs, or the absence of homomorphic images of large enough complete graphs.</p> <p>The linear relationship between the order of $G$ and $H$ is the first "interesting" one. If the bound is decreased by 1, requiring only $|V(H)| \ge |V(G)| - 1$, then $G = K_4$ suffices but the size condition on $H$ holds simply because $H$ contains a triangle. I would also be interested in extensions, such as establishing whether such a graph $G$ exists for other functions bounding the order of $H$ in terms of the order of $G$.</p> http://mathoverflow.net/questions/92783/random-task-scheduling-problem/92856#92856 Answer by András Salamon for Random Task Scheduling Problem András Salamon 2012-04-01T23:06:07Z 2012-04-02T15:24:08Z <p>The case where $n > m$ is "easy": if $F$ is the distribution function of each of the $m$ iid random variables, then the distribution function of the maximum is $F^m$. Of course, $F^m$ may be difficult to compute, so even bounding the expectation of the makespan can be tricky.</p> <ul> <li>Peter J. Downey, <em>Distribution-free bounds on the expectation of the maximum with scheduling applications</em>, Operations Research Letters <strong>9</strong>, 189–201. <a href="http://dx.doi.org/10.1016/0167-6377%2890%2990018-Z" rel="nofollow">doi:10.1016/0167-6377(90)90018-Z</a></li> </ul> <p>For the general case where $n \le m$ it seems difficult to obtain closed-form solutions.</p> <p>Using Kendall's notation for queueing systems, this is a D/GI/n system, or in the extended notation D/GI/n/m/m/FIFO. Nothing is lost by requiring the tasks to form a queue. However, I do not know whether systems with such one-shot arrival distributions have been studied in the queueing theory literature.</p> <p>The minimum of $n$ exponentially distributed random variables is also exponentially distributed. This does suggest a procedure to efficiently simulate the system, from which one can generate a numerical approximation to the distribution, but I don't immediately see how to obtain a closed form solution.</p> <p>Suppose you choose a random partition of the tasks into $n$ blocks. This may fail to correspond to a valid schedule, since the block with the largest sum may still exceed the smallest block sum, even with a task removed. This suggests the following correction procedure. For the block with the largest sum, remove one of the tasks. If the sum without this task is no larger than the smallest block sum, then put the task back and stop. Otherwise put the task into the block with the smallest sum, and iterate. This procedure yields a valid schedule.</p> <p>Now consider the maximum block sum. In the uncorrected case, this will be an upper bound for the makespan. As far as I can tell, it then seems feasible to find the distribution of the correction that is applied, as well as the distribution of the maximum block sum over all random partitions (though probably not in closed form). If $n \lt \lt m$ this might provide a reasonable way to go, perhaps in combination with bounding techniques for the distribution of the maximum.</p> <hr> <p><em>Edit:</em> This report by Coffman and Whitt seems to consider the precise question you ask. They say that <em>multiprocessor scheduling</em> is the generic name for this class of problems, and state: "Because of the difficulty of exact analysis, the results take the form of limits". There is also a published version from 1996 which explicitly focuses on Markov chain approaches to study the asymptotic behaviour.</p> <ul> <li>E. G. Coffman, Jr. and Ward Whitt, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.7891" rel="nofollow"><em>Recent Asymptotic Results in the Probabilistic Analysis of Schedule Makespans</em></a>. Unpublished, 1993.</li> <li>E. G. Coffman, Jr. and Ward Whitt, <em>Stochastic limit laws for schedule makespans</em>. Communications in Statistics. Stochastic Models <strong>12</strong>, 215–243, 1996. <a href="http://dx.doi.org/10.1080/15326349608807382" rel="nofollow">doi:10.1080/15326349608807382</a> (<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.3627" rel="nofollow">preprint</a>)</li> </ul> http://mathoverflow.net/questions/80228/compressing-graphs-kolmogorov-complexity-of-graphs/80252#80252 Answer by András Salamon for Compressing Graphs (Kolmogorov complexity of graphs) András Salamon 2011-11-06T22:13:07Z 2011-11-06T22:13:07Z <p>Li and Vitányi in their standard textbook on Kolmogorov complexity (3rd edition, p.456) observe</p> <blockquote> <p>Almost all strings have high complexity. Therefore, almost all tournaments and almost all undirected graphs have high complexity.</p> </blockquote> <p>This is made more precise in Section 6.4. In particular, they show that the number of distinct isomorphism classes of undirected graphs with $n$ vertices asymptotically approaches $2^\binom{n}{2}/n!$, with only a small error.</p> <p>By <a href="http://en.wikipedia.org/wiki/Stirling%27s_approximation" rel="nofollow">Stirling's approximation</a>, the Kolmogorov complexity of undirected graphs with $n$ vertices can then be seen to be close to $n(n-1)/2 + c$ bits. For undirected graphs the adjacency matrix is symmetric and has 0's on the diagonal, so one only needs to store the $n(n-1)/2$ bits above the diagonal.</p> <p>This makes more precise the claim made in another answer, that the adjacency matrix representation is optimal. (Note that <em>close</em> in this argument may still be an unbounded function of $n$; see also Lemma 6.4.6 and the comment after it.)</p> <ul> <li>Ming Li and Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd edition, Springer-Verlag, 2008. doi: <a href="http://dx.doi.org/10.1007/978-0-387-49820-1" rel="nofollow">10.1007/978-0-387-49820-1</a></li> </ul> http://mathoverflow.net/questions/74759/survey-on-structural-complexity/74766#74766 Answer by András Salamon for Survey on Structural Complexity András Salamon 2011-09-07T16:10:48Z 2011-09-07T16:10:48Z <p>The best reference for relationships between complexity classes is the <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo" rel="nofollow">Complexity Zoo</a>. It also includes useful sections such as the Petting Zoo and the Special Exhibit of quantum classes. Perhaps because the Zoo is so extensive (nearly 500 entries currently), new classes are added regularly, while many old classes have yet to be added, no-one has written a comprehensive survey.</p> <p>Some of the interesting structure of the lattice of classes is captured by <a href="http://www.cs.umass.edu/~immerman/descriptive_complexity.html" rel="nofollow">descriptive complexity</a>, which relates many of the main classes to fragments of logic.</p> <p>Recent textbooks like <a href="http://www.cs.princeton.edu/theory/complexity/" rel="nofollow">Arora/Barak</a>, <a href="http://www.amazon.com/Theory-Computation-Texts-Computer-Science/dp/1846282977/" rel="nofollow">Kozen</a>, and <a href="http://www-math.mit.edu/~sipser/book.html" rel="nofollow">Sipser</a> do cover many of the "standard" relationships you mention.</p> http://mathoverflow.net/questions/67371/higher-order-preservation-theorems Higher-order preservation theorems? András Salamon 2011-06-09T19:53:01Z 2011-06-16T18:25:59Z <p>The <a href="http://en.wikipedia.org/wiki/%C5%81o%C5%9B%E2%80%93Tarski_preservation_theorem" rel="nofollow">Łos-Tarski preservation theorem</a> states that a set of formulas $F$ of first-order language $L$ is preserved under substructures for models of theory $T$ in $L$ precisely when $F$ is equivalent modulo $T$ to a set of universal formulas of $L$. The often-seen corollary is that a formula of $L$ is preserved by embeddings between models of $T$ precisely when it is equivalent modulo $T$ to an existential formula of $L$.</p> <p>Lyndon's preservation theorem has a similar flavour, relating positive formulas and surjective homomorphisms. Moreover, first-order formulas preserved under homomorphisms are precisely those that are equivalent to an existential positive first-order formula with the same quantifier-rank.</p> <p>These kinds of preservation results use first-order theories. However, some higher-order logics, such as the monadic fragment of second-order logic, are sufficiently restricted that they retain many of the properties of first-order logic. This motivates my question:</p> <blockquote> <p>Are any preservation results known for logics $L$ and theories $T$ beyond first-order? In other words, are there results such as: <em>a formula of logic $L$ is preserved under embeddings between models of theory $T$ in $L$ precisely when it is equivalent modulo $T$ to an existential formula of $L$</em>?</p> </blockquote> <p>Pointers or even key phrases would be appreciated. I'm struggling to find relevant references, which may indicate that I have overlooked a trivial reason why such theorems cannot exist: if this is the case then a hint would be appreciated.</p> <p>References:</p> <ul> <li>Wilfrid Hodges, <em>Model Theory</em>, Cambridge University Press, 1993.</li> <li>Benjamin Rossman, <em>Homomorphism preservation theorems</em>, Journal of the ACM <strong>55</strong>(3), 2008. doi:<a href="http://dx.doi.org/10.1145/1379759.1379763" rel="nofollow">10.1145/1379759.1379763</a> (<a href="http://www.mit.edu/~brossman/hpt-jacm-final.pdf" rel="nofollow">preprint</a>)</li> </ul> http://mathoverflow.net/questions/58188/are-nontrivial-integer-solutions-known-for-x3y3z33 Are nontrivial integer solutions known for $x^3+y^3+z^3=3$? András Salamon 2011-03-11T19:05:47Z 2011-06-02T18:48:24Z <p>The Diophantine equation $$x^3+y^3+z^3=3$$ has four easy integer solutions: $(1,1,1)$ and the three permutations of $(4,4,-5)$. Elsenhans and Jahnel wrote in 2007 that these were all the solutions known at that time.</p> <blockquote> <p>Are any other solutions known?</p> </blockquote> <p>By a conjecture of Tyszka, it would follow that if this equation had finitely many roots, then each component of a solution tuple would be at most $2^{2^{12}/3} \lt 2^{1365.34}$ in absolute value. (To see this, it is enough to express the equation using a Diophantine system in 13 variables in the form considered by Tyszka.) This leaves a large gap, since Elsenhans and Jahnel only considered solutions with components up to $10^{14} \approx 2^{46.5}$ in absolute value. It is also not obvious whether Tyszka's conjecture is true.</p> <p>OEIS sequence <a href="http://oeis.org/A173515" rel="nofollow">A173515</a> refers to equations of the form $x^3+y^3=z^3-n$, for $n$ a positive integer, as "Fermat near-misses". Infinite families of solutions are known for $n=\pm 1$, including one constructed by Ramanujan from generating functions (see Rowland's survey).</p> <ul> <li>Andreas-Stephan Elsenhans and Jörg Jahnel, <em>New sums of three cubes</em>, Math. Comp. <strong>78</strong> (2009), 1227–1230. DOI: <a href="http://dx.doi.org/10.1090/S0025-5718-08-02168-6" rel="nofollow">10.1090/S0025-5718-08-02168-6</a>. (<a href="http://www.staff.uni-bayreuth.de/~btm216/elk_ants6c.pdf" rel="nofollow">preprint</a>)</li> <li>Apoloniusz Tyszka, <em>A conjecture on integer arithmetic</em>, Newsletter of the European Mathematical Society (75), March 2010, 56–57. (<a href="http://www.ems-ph.org/journals/newsletter/pdf/2010-03-75.pdf" rel="nofollow">issue</a>)</li> <li>Eric S. Rowland, <em>Known Families of Integer Solutions of $x^3+y^3+z^3=n$</em>, 2005. (<a href="http://www.math.tulane.edu/~erowland/papers/koyama.pdf" rel="nofollow">manuscript</a>)</li> </ul> http://mathoverflow.net/questions/35590/is-k-xorsat-p-complete Is #k-XORSAT #P-complete? András Salamon 2010-08-14T19:21:35Z 2011-04-05T10:44:27Z <p>k-XORSAT is the problem of deciding whether a Boolean formula $$\bigwedge_{i \in I} \oplus_{j=1}^k l_{s_{ij}}$$ is satisfiable. Here $\oplus$ denotes the binary <a href="http://en.wikipedia.org/wiki/Xor" rel="nofollow">XOR</a> operation, $I$ is some index set, and each clause has $k$ distinct literals $l_{s_{ij}}$ each of which is either a variable $x_{s_{ij}}$ or its negation.</p> <p>Equivalently, $k$-XORSAT requires deciding whether a set of linear equations, each of the form $\sum_{j=1}^k x_{s_{ij}}\equiv 1\; (\mod 2)$, has a solution over $\mathbb{Z}_2 = \mathbb{Z}/2\mathbb{Z}$.</p> <p>Every decision problem Q has an associated counting problem #Q, which (informally speaking) requires establishing the number of distinct solutions. Such counting problems form the complexity class <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3ASymbols#sharpp" rel="nofollow">#P</a>. The "hardest" problems in #P are #P-complete, as any problem in #P can be reduced to a #P-complete problem.</p> <p>The counting problem associated with any NP-complete decision problem is #P-complete. However, many "easy" decision problems (some even solvable in linear time) also lead to #P-complete counting problems. For instance, Leslie Valiant's original 1979 paper <a href="http://dx.doi.org/10.1016/0304-3975%2879%2990044-6" rel="nofollow"><em>The Complexity of Computing the Permanent</em></a> shows that computing the permanent of a 0-1 matrix is #P-complete. As a second example, the list of #P-complete problems in the companion paper <a href="http://dx.doi.org/10.1137/0208032" rel="nofollow"><em>The Complexity of Enumeration and Reliability Problems</em></a> includes #MONOTONE 2-SAT; this problem requires counting the number of solutions to Boolean formulas in conjunctive normal form, where each clause has two variables and no negated variables are allowed. (MONOTONE 2-SAT is of course rather trivial as a decision problem.)</p> <p>Andrea Montanari has written about the partition function of $k$-XORSAT in some <a href="http://www.stanford.edu/~montanar/TEACHING/Stat316/handouts/lecture-4.pdf" rel="nofollow">lecture notes</a>, and his book with Marc Mézard apparently discusses this (unfortunately I do not have a copy available to hand, and the relevant Chapter 17 is not included in Montanari's online draft).</p> <p>These considerations lead to the following question:</p> <blockquote> <p>Is #$k$-XORSAT #P-complete?</p> </blockquote> <p>Note that the formula in Montanari's notes does not obviously appear to answer this question. Just because there is a nice closed form solution, doesn't mean we can evaluate it efficiently: consider the <a href="http://en.wikipedia.org/wiki/Tutte_polynomial" rel="nofollow">Tutte polynomial</a>.</p> <p>Some difficult counting problems in #P can still be approximated in a certain sense, by means of a scheme called an FPRAS. Jerrum, Sinclair, and collaborators have linked the existence of an FPRAS for #P problems to the question of whether $NP = RP$. I would therefore also be interested in the subsidiary question</p> <blockquote> <p>Does #$k$-XORSAT have an FPRAS?</p> </blockquote> <p><em>Edit: clarified second question as per comment by Tsuyoshi Ito. Note that Peter Shor's answer renders this part of the question moot.</em></p> http://mathoverflow.net/questions/55151/stable-distributions-for-lindeberg-exchange-strategy Stable distributions for Lindeberg exchange strategy? András Salamon 2011-02-11T18:47:36Z 2011-02-11T18:47:36Z <p>Terence Tao has mentioned the importance of the Lindeberg exchange strategy, citing as an application how it was used in the proofs of some recent results relating to universality laws for random matrices. In a <a href="http://terrytao.files.wordpress.com/2009/08/random_matrix.pdf" rel="nofollow">presentation from 2009</a>, he explains the strategy as follows:</p> <ul> <li>Prove the result holds for $F(X_1,\dots,X_n)$. Here $F$ is a "nice" function, and the random variables $X_i$ are iid Gaussian.</li> <li>Prove that the distribution of $F$ is invariant under replacement of the distribution of the random variables, or more precisely, that when $n$ grows, $F(X_1,\dots,X_n)$ has the same distribution asymptotically as $F(Y_1,\dots,Y_n)$, where the $Y_i$ are iid from some distribution $D$.</li> </ul> <p>The original application of the exchange strategy seems to have been Lindeberg's proof of the Central Limit Theorem, where $F(X_1,\dots,X_n) = \sum_{i=1}^n X_i/\sqrt{n}$. (Tao discusses this example in slides 32-34.)</p> <p>My question is:</p> <blockquote> <p>Is it feasible to use the Lindeberg exchange strategy with a <a href="http://en.wikipedia.org/wiki/Stable_distribution" rel="nofollow">stable distribution</a> that does not have finite variance?</p> </blockquote> <p>It is possible that the Lindeberg exchange strategy essentially requires the finite variance assumption. Removing it certainly breaks the proofs I've looked at (although I am no expert and have not done an exhaustive survey). However, the overall strategy doesn't obviously require finite variance. Is there something fundamental about the exchange strategy that relies on Gaussians?</p> http://mathoverflow.net/questions/34710/succinctly-naming-big-numbers-zfc-versus-busy-beaver/34872#34872 Answer by András Salamon for Succinctly naming big numbers: ZFC versus Busy-Beaver András Salamon 2010-08-07T22:49:43Z 2010-08-07T22:49:43Z <p>This picks up Scott's further question</p> <blockquote> <p>can anyone come up with a better ZFC-based integer sequence that avoids these problems and matches or (better yet) exceeds the growth rate of f, while not being dependent on a particular model of ZFC?</p> </blockquote> <p>I can't see anything in the Turing machine style definition that can't be encoded with ZFC. Translate any TM-style definition of $f$ into a ZFC-style definition, using standard machinery such as treating the TM state transition table as a binary relation, letting an integer encode the current state of a tape, and collecting together the right objects into oracle sets. Then let $z$ be the ZFC-style definition of $f$.</p> <p>In your definition of $f$ you are using a description which is more compact than ZFC, in the sense that your parameterize it with $n$ states in each of the two TMs you compose, instead of $n$ symbols which is all you allow for $z$.</p> <p>What am I missing: what specific feature does the TM style definition bring that is not already in ZFC? I would agree that the TM style definition allows expressing larger numbers than an equivalent length ZFC description. But this seems to be a feature of what is being counted, not necessarily that TMs are more expressive, let alone "maximally" expressive.</p> http://mathoverflow.net/questions/34364/cliquewidth-of-cographs-kv/34425#34425 Answer by András Salamon for Cliquewidth of Cographs + kv András Salamon 2010-08-03T18:39:46Z 2010-08-03T18:39:46Z <p>I think the exponential bound is necessary. Here is why.</p> <p>Consider the disconnected graph $G$ on $n$ vertices, labelled $1$ to $n$. Denote the set of vertices that new vertex $i$ is connected to by $f(i)$, a subset of $\lbrace 1,2,\ldots,n \rbrace$. The question then becomes: is it possible to find such a function $f$ so that the set $\lbrace f(i) \mid 1 \le i \le k \rbrace$ of subsets of $V(G)$ generates a set of subsets of size $2^k$? With "generates" I mean the closure under the operation of taking pairwise subsets.</p> <p>The idea here is that to distinguish between any subsets one needs to label them differently. However, due to the way the cliquewidth operations are restricted, this can only happen if their intersection is constructed first, and then the remaining vertices.</p> <p>As far as I can tell, this scenario is possible, but clearly the above is quite far from a rigorous construction of an example.</p> http://mathoverflow.net/questions/34173/fast-matrix-multiplication/34178#34178 Answer by András Salamon for Fast Matrix Multiplication András Salamon 2010-08-02T00:21:11Z 2010-08-02T00:21:11Z <p>Sara Robinson's survey <a href="http://www.siam.org/news/news.php?id=174" rel="nofollow"><em>Toward an Optimal Algorithm for Matrix Multiplication</em></a>, SIAM News <strong>38</strong> (9), 2005, might be suitable.</p> http://mathoverflow.net/questions/32290/selecting-k-sub-posets/32300#32300 Answer by András Salamon for Selecting k sub-posets András Salamon 2010-07-17T18:11:46Z 2010-07-27T18:02:27Z <p>You seem to rely on a notion of a vertex preceding another (you use the terms "lattice" and "polyhierarchy", and refer to the direction "down"). So the edge relation $E$ appears to be transitive, forming a strict partial order.</p> <p>To show why the $k$ parameter is important, you suggest an example where the target set $G$ presumably contains the three children of the root $\mu$. In this case, $k=1$ would clearly allow $S = \lbrace \mu \rbrace$. On the other hand, setting $k=2$ would force each of the children to be in $S$, to avoid condition 2.</p> <p>This gives the key to the reduction of SET COVER to the decision version of your problem. Given is a set of subsets of a finite universe, and an integer $l$. The problem is to determine whether one can find at most $l$ subsets which cover the entire universe. For each subset create a vertex, and let $E$ be the subset relation between subsets, expressed in terms of the vertices. If the universe itself is one of the subsets, then let $k=1$ (note that in this case the problem is quite trivial, the solution $S$ will simply contain this one element). Otherwise let $k=2$ and add a new root vertex denoting the universe, with edges to every other vertex. Finally, let $G$ be the set of all minimal vertices (corresponding to all minimal subsets).</p> <p>This instance of your problem has a solution (a set of at most $l \ge k$ vertices, covering all minimal vertices) if, and only if, the set cover instance has a solution.</p> <p>I hope I have managed to capture your problem correctly.</p> http://mathoverflow.net/questions/33192/when-is-the-independence-number-of-a-graph-equals-the-clique-cover-number/33319#33319 Answer by András Salamon for when is the independence number of a graph equals the clique cover number András Salamon 2010-07-25T20:06:12Z 2010-07-25T20:06:12Z <p>Denote the independence number of $G$ by $\alpha(G)$, and the clique cover number by $\overline{\chi}(G)$. It is obvious that $\overline{\chi}(G) \ge \alpha(G)$. You are asking when $\alpha(G) = \overline{\chi}(G)$.</p> <p>This seems to be the question that drove the definition and investigation of perfect graphs. See <a href="http://dx.doi.org/10.1016/S0012-365X%2896%2900161-6" rel="nofollow">Berge's historical overview</a>. The definition of perfect graphs requires the equality between independence number and clique cover number <em>for every induced subgraph</em>. This is Berge's "Beautiful Property", defining what he calls "class 2". Rephrasing a <a href="http://dx.doi.org/10.1016/0012-365X%2872%2990006-4" rel="nofollow">comment by Lovász</a>, the induced subgraph condition is needed to remove the artificial examples where a large set $X$ of new vertices is added to a graph such that each vertex in $X$ is adjacent to each vertex of the original graph. Applying this construction to any graph yields a new graph that satisfies your condition.</p> <p>Berge also defined "class 3", those graphs for which the chromatic number equals the clique number for every induced subgraph, and "class 4", the graphs which contain no induced odd hole or induced odd antihole. In the paper mentioned above, Lovász proved the perfect graph theorem, that the complement of a perfect graph is perfect. This shows that "class 2" and "class 3" are the same. Perfect graphs are now usually defined as "class 3", and the strong perfect graph theorem shows that "class 4", of Berge graphs, is the same as "class 3". Berge claimed he was originally more interested in whether "class 2" and "class 3" coincided.</p> <p>One final remark: if $\alpha(G) = \overline{\chi}(G)$, then the <a href="http://dx.doi.org/10.1109/TIT.1956.1056798" rel="nofollow">Shannon capacity</a> of $G$ is $\log \alpha(G)$. This is Berge's "class 1" (note that the "log" is missing in the paper, clearly a typo). This is really saying that in the limit, when $\alpha(G) = \overline{\chi}(G)$ then the independence number dominates the channel performance in the long run. From this applied point of view, it makes sense to look for the kinds of graphs which have this property inherently, and not just by a large independent set being glued on.</p> <p>However, there may be other applications for graphs for which $\alpha(G) = \overline{\chi}(G)$ holds, but where this relationship fails for some induced subgraphs. This would then make it interesting to find the graphs that have this property but not via a glued-on independent set. To end this answer on a question: do you have such an application in mind?</p> http://mathoverflow.net/questions/32985/ramsey-pairs-of-classes-graphs/33115#33115 Answer by András Salamon for Ramsey pairs of classes graphs András Salamon 2010-07-23T17:24:37Z 2010-07-24T16:22:22Z <p>A semi-trivial pair: let $C$ be any class of graphs, and let $D$ contain the complete graphs on the vertex set of every graph in $C$.</p> <p>Less trivial: for $C$, start with any set of finite graphs, and when $G$ is a graph in the set, then require the disjoint union of $G$ with itself to also be in the set. Let $C$ be the class formed by closing this set under isomorphism, and let $D$ contain the disjoint union of every graph in $C$ with a complete graph with the same number of vertices.</p> <p>(Edit: an additional condition is needed to ensure that the choice of graph from $D$ has the required properties. One way is to start with a set of graphs where the sizes of the starting graphs are all relatively prime.)</p> <p>To make your definition more interesting, such examples perhaps need to be ruled out? (The second one has $D$ as complicated as $C$.)</p> http://mathoverflow.net/questions/32912/where-is-it-shown-how-to-construct-a-decomposition-tree-for-a-series-parallel-gra/32917#32917 Answer by András Salamon for Where is it shown how to construct a decomposition tree for a series-parallel graph in linear time? András Salamon 2010-07-22T08:23:39Z 2010-07-22T13:17:37Z <p>As you state, Valdes/Tarjan/Lawler is a recognition algorithm.</p> <p>There has been a <a href="http://www.liafa.jussieu.fr/~fm/HistDM.html" rel="nofollow">stream of work</a> on actually finding modular decompositions. The recent work of <a href="http://www.liafa.jussieu.fr/~fm/" rel="nofollow">Fabien de Montgolfier</a> (with collaborators) is pretty definitive; they have also produced a <a href="http://www.liafa.jussieu.fr/~fm/algos/index.html" rel="nofollow">C implementation</a>. I did a <a href="http://search.cpan.org/~azs/Graph-ModularDecomposition/" rel="nofollow">Perl implementation</a> of an older algorithm, and <a href="http://www-sop.inria.fr/members/Nathann.Cohen/tut/Graphs/" rel="nofollow">Nathann Cohen</a> is currently working to incorporate de Montgolfier's code into the <a href="http://www.sagemath.org/" rel="nofollow">Sage</a> framework (it looks like it should appear in version 4.5.2, due early August 2010).</p> http://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics/30332#30332 Answer by András Salamon for What are the most attractive Turing undecidable problems in mathematics? András Salamon 2010-07-02T18:30:56Z 2010-07-03T13:03:42Z <p>In your last criterion, you are essentially asking for a "natural" problem that is nonrecursive, recursively enumerable, and is not complete for the recursively enumerable sets. Post proved the existence of such problems in <em><a href="http://www.ams.org/journals/bull/1944-50-05/S0002-9904-1944-08111-1/" rel="nofollow">Recursively enumerable sets of positive integers and their decision problems</a></em>, for many-one reductions. Friedberg and Muchnik proved this also holds for Turing reductions, in separate papers <em><a href="http://www.jstor.org/stable/89817" rel="nofollow">Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post's problem, 1944)</a></em> and <em>On the unsolvability of the problem of reducibility in the theory of algorithms</em>. Whether these are "attractive" is probably determined by whether you like nonconstructive arguments. For a clear and self-contained exposition of these results, see Kozen's book Theory of Computation.</p> <p>So this is only a partial answer, and it would still be nice to exhibit a <em>real</em> problem with intermediate degree.</p> <p>Edit: in the survey <em><a href="http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf" rel="nofollow">Degrees of Unsolvability</a></em> (which appears to be a chapter of an unpublished Volume 9 of the <a href="http://www.johnwoods.ca/HHL/" rel="nofollow">Handbook of the History of Logic</a>), Ambos-Spies and Fejer state "it is fair to say that every particular c.e. set of natural numbers that has arisen from nonlogical considerations so far is either computable or complete... Thus one could say that the great complexity in the structure of the c.e. degrees arises solely from studying unnatural problems." This is quite a negative assessment! On a more positive note, Feferman showed in <em><a href="http://www.jstor.org/stable/2964178" rel="nofollow">Degrees of Unsolvability Associated with Classes of Formalized Theories</a></em> that every c.e. degree arises as the degree of some recursively axiomatizable consistent theory of first-order predicate calculus.</p> http://mathoverflow.net/questions/30191/software-for-tree-decompositions/30230#30230 Answer by András Salamon for Software for Tree-Decompositions András Salamon 2010-07-01T20:39:28Z 2010-07-01T20:39:28Z <p>For general graphs there are no good algorithms known, as the problem of determining the treewidth of a graph is NP-hard. So if your graphs are not from some special class, and instances are small, then a brute force search over all decompositions of small width is a reasonable approach.</p> <p>As a previous answer suggested, Röhrig's Diplomarbeit ranks highly in a Google search. His rather negative conclusion in 1998 was that when treewidth exceeds $4$, brute force enumeration was essentially the only realistic option; up to $4$ special-purpose algorithms were reasonable. This is not that surprising, as (intuitively speaking) iterating over all choices of bags of up to $k$ elements takes $\Omega(n^k)$ time, so the runtime grows quite fast.</p> <p>Do your graphs have some special features? The <a href="http://wwwteo.informatik.uni-rostock.de/isgci/" rel="nofollow">ISGCI</a> has many special graph classes, for some of which it is possible to find join-trees efficiently. (Join-tree decompositions are another name for tree decompositions, although this term nowadays seems to usually refer to join trees as used in Bayesian networks.)</p> <p>Taking a really high level perspective, do you really want to compute tree decompositions? If you are decomposing trees because you need to do something with them, then consider an easier-to-compute decomposition. For instance, the modular decomposition can be computed in linear time, and also guarantees fast algorithms for many problems via the modular decomposition tree. There is a <a href="http://search.cpan.org/~azs/Graph-ModularDecomposition/" rel="nofollow">Perl implementation</a> of an older algorithm, <a href="http://www-sop.inria.fr/members/Nathann.Cohen/tut/Graphs/" rel="nofollow">Nathann Cohen</a> is currently working to incorporate a more recent C implementation into the <a href="http://www.sagemath.org/" rel="nofollow">Sage</a> framework, or you could use <a href="http://www.liafa.jussieu.fr/~fm/algos/index.html" rel="nofollow">Fabien de Montgolfier's C code</a> directly if you read French (the papers describing the work are in English).</p> <p>If you really do need tree decompositions, then have a look at the simple approach via induced width, which can be easily implemented (and parallelized) by considering each possible vertex ordering, then checking the induced width it corresponds to. Section 2.3 of Rina Dechter's draft version of her chapter from the Handbook of Constraint Programming is quite useful as a starting point.</p> http://mathoverflow.net/questions/133184/hellys-number-from-biconvex-functions Comment by András Salamon András Salamon 2013-06-10T09:03:29Z 2013-06-10T09:03:29Z See <a href="http://math.stackexchange.com/questions/414971/hellys-number-from-biconvex-functions" rel="nofollow" title="hellys number from biconvex functions">math.stackexchange.com/questions/414971/&hellip;</a> http://mathoverflow.net/questions/132335/hellys-theorem-for-biconvex-sets Comment by András Salamon András Salamon 2013-06-10T09:01:34Z 2013-06-10T09:01:34Z See <a href="http://math.stackexchange.com/questions/406635/hellys-theorem-for-biconvex-sets" rel="nofollow" title="hellys theorem for biconvex sets">math.stackexchange.com/questions/406635/&hellip;</a> http://mathoverflow.net/questions/132859/bounding-roots-of-a-polynomial-by-coefficients Comment by András Salamon András Salamon 2013-06-06T12:23:03Z 2013-06-06T12:23:03Z If you are asking about bounds on the roots (which the title would seem to indicate), then Fujiwara's bound might be useful: <a href="http://en.wikipedia.org/wiki/Properties_of_polynomial_roots#Other_bounds" rel="nofollow">en.wikipedia.org/wiki/&hellip;</a> ; however, I am not sure precisely what you are asking. http://mathoverflow.net/questions/132775/do-right-profiles-determine-graphs-up-to-isomorphism Comment by András Salamon András Salamon 2013-06-05T00:16:34Z 2013-06-05T00:16:34Z Usual notion of homomorphism, as in the Lov&#225;sz paper: $u~v$ implies $f(u)~f(v)$. People don't seem to worry about loops and multi-edges in this context because it often seems easy to translate between the graph/multigraph cases with small tweaks. http://mathoverflow.net/questions/132775/do-right-profiles-determine-graphs-up-to-isomorphism/132780#132780 Comment by András Salamon András Salamon 2013-06-05T00:12:49Z 2013-06-05T00:12:49Z One switches sides, so one has to use surjections for the right-profile. When the number of surjective homomorphisms is always equal, then the graphs are isomorphic. So one just has to show that this holds when the right-profiles are identical. Partition the homomorphisms into those that are surjective on every subgraph of the target. The number of homomorphisms is the same, and the proper subgraphs lead to equal numbers by an inductive argument; the number of surjective homomorphisms is the difference, which is then equal for the two graphs. http://mathoverflow.net/questions/132775/do-right-profiles-determine-graphs-up-to-isomorphism/132780#132780 Comment by András Salamon András Salamon 2013-06-04T21:34:51Z 2013-06-04T21:34:51Z Thanks for the explicit pointer, &quot;somebody&quot;! http://mathoverflow.net/questions/132728/tutte-polynomials-graph-complements-and-degree-sequences Comment by András Salamon András Salamon 2013-06-04T20:44:26Z 2013-06-04T20:44:26Z In <a href="http://dx.doi.org/10.1006/jctb.2000.1988" rel="nofollow">dx.doi.org/10.1006/jctb.2000.1988</a> Bollob&#225;s, Pebody and Riordan conjecture that for almost all random graphs the Tutte polynomial determines the graph up to isomorphism; they also show that there is no way to locally modify a graph to leave the Tutte polynomial unchanged while breaking isomorphism, other than removing loops and re-attaching them in different places. So even finding two non-isomorphic graphs with the same Tutte polynomial is likely to be hard; your questions seem to be even harder (unless the answers are negative). http://mathoverflow.net/questions/131435/why-dont-more-mathematicians-improve-wikipedia-articles/131469#131469 Comment by András Salamon András Salamon 2013-05-22T21:42:32Z 2013-05-22T21:42:32Z Every Wikipedia page has its full date-stamped history available (it is one of the tabs visible on every page), complete with change tracking. In my experience truly anonymous edits tend to be either spam (and quickly reverted) or small fixes by someone who couldn't be bothered to log on; it is therefore usually easy to get a feel for who has made significant contributions. In fact, the sheer volume of Wikipedia change history can be overwhelming. http://mathoverflow.net/questions/131435/why-dont-more-mathematicians-improve-wikipedia-articles/131463#131463 Comment by András Salamon András Salamon 2013-05-22T21:34:56Z 2013-05-22T21:34:56Z I don't find this at all; the Wikipedia articles I look at daily (many of them in mathematics and technical subjects) could nearly all do with at least copy-editing or improvement of references. It takes about as long to fix a typo as it does to glance at the new mail in one's mailbox, and about as long to correct a sloppy reference as it does to read (but not contribute to) a soft question on MO with a dozen answers. http://mathoverflow.net/questions/131449/motivation-for-frankls-conjecture/131456#131456 Comment by András Salamon András Salamon 2013-05-22T21:21:25Z 2013-05-22T21:21:25Z From the abstract of Poonen's 1992 article Union-closed families <a href="http://dx.doi.org/10.1016/0097-3165(92)90068-6" rel="nofollow">dx.doi.org/10.1016/0097-3165(92)90068-6</a> comes the sentence &quot;Frankl conjectured in 1979 that...&quot;. http://mathoverflow.net/questions/131449/motivation-for-frankls-conjecture/131474#131474 Comment by András Salamon András Salamon 2013-05-22T21:16:36Z 2013-05-22T21:16:36Z The Handbook was first published in 1995, and there is only one edition. http://mathoverflow.net/questions/37272/are-all-sets-totally-ordered/37282#37282 Comment by András Salamon András Salamon 2013-05-19T16:20:31Z 2013-05-19T16:20:31Z The Howard/Rubin book cites: James D. Halpern and Azriel Levy, <i>The ordering theorem does not imply the axiom of choice</i>, Notices of the AMS <b>11</b> (1964), 56. http://mathoverflow.net/questions/129638/incremental-minimum-spanning-tree Comment by András Salamon András Salamon 2013-05-04T15:24:51Z 2013-05-04T15:24:51Z Relevant is David Eppstein's work on dynamic algorithms for minimum spanning trees <a href="http://dx.doi.org/10.1006/jagm.1994.1033" rel="nofollow">dx.doi.org/10.1006/jagm.1994.1033</a> or the preprint at <a href="http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-92-04.pdf" rel="nofollow">ics.uci.edu/~eppstein/pubs/Epp-TR-92-04.pdf</a> http://mathoverflow.net/questions/129142/weakest-choice-principle-required-for-robertson-seymour-graph-minor-theorem/129211#129211 Comment by András Salamon András Salamon 2013-05-02T11:45:10Z 2013-05-02T11:45:10Z That seems to settle things -- thanks for elaborating. http://mathoverflow.net/questions/129142/weakest-choice-principle-required-for-robertson-seymour-graph-minor-theorem/129211#129211 Comment by András Salamon András Salamon 2013-05-01T01:48:58Z 2013-05-01T01:48:58Z Andrey Bovykin's &quot;Unprovability threshold for the planar graph minor theorem&quot; from 2010 states that the upper bound for the Graph Minor Theorem is $\Pi_1^1-\text{CA}+\text{BI}$, from the Friedman/Robertson/Seymour paper mentioned in the question. I am not familiar with BI -- but is this just a fragment of second-order arithmetic?