User domotorp - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T20:38:02Z http://mathoverflow.net/feeds/user/955 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/123456/a-question-about-the-size-of-a-l1-ball/125385#125385 Answer by domotorp for A question about the size of a L1 ball domotorp 2013-03-23T15:51:28Z 2013-03-23T16:41:47Z <p>I realized that once we suppose $\kappa$, $|\mathcal{X}|$ and $|\mathcal{Y}|$ are all $O(1)$, there is a much simpler argument. For each entry of the matrix that is not in the last column, pick a number from $[-\sqrt n,\sqrt n]$ and select the last number of each row such that the marginal becomes $t$. This gives the required $\sqrt n^{(|\mathcal{Y}|-1)\cdot|\mathcal{X}|}$.</p> <p>For completeness, here is my $Old$ $answer$: I think they use the following fact: The number of ways to put A (identical) balls into B (ordered) bins is ${A+B-1 \choose B-1}$. If A is big compared to B, this is about $A^{B-1}$. More precisely, I think they suppose $|\mathcal{X}|$ and $|\mathcal{Y}|$ are both $O(1)$. Here is a sketch of the computation (not rigorous at all!!!):</p> <p>In the problem, first we have to decide in which rows the at most $\kappa \sqrt n$ difference will appear, so we put at most $\kappa \sqrt n$ balls to $|\mathcal{X}|$ bins, so far, omitting $\kappa$ and summing for the number of balls from 0 to $\sqrt n$, about $\sqrt n\cdot \sqrt n ^{|\mathcal{X}|-1}= 2^{|\mathcal{X}|\log n /2}$ possibilities. Obviously in most cases this distribution will be quite even, so in each row we further have to divide $\kappa \sqrt n/ |\mathcal{X}|$ balls into $|\mathcal{Y}|-1$ bins and then use the last bin to make the marginal equal to $t$, so we get (ignoring $|\mathcal{X}|$ as it is $O(1)$) about $2^{(|\mathcal{Y}|-2)\log n /2}$ possibilities in each row. In total $2^{|\mathcal{X}|\log n /2} \cdot (2^{(|\mathcal{Y}|-2)\log n /2})^{|\mathcal{X}|}$, just what we wanted.</p> http://mathoverflow.net/questions/124604/turing-complete-primitive-blind-automata/124767#124767 Answer by domotorp for Turing-complete primitive blind automata domotorp 2013-03-17T09:58:23Z 2013-03-17T09:58:23Z <p>Probably I also don't understand the question but then by universality you mean that Q can change or that p can change? I think both cases are easy to be seen to be universal but I must misunderstand something.</p> <p>In the first, pick p=(1,11) and let the integers correspond to the steps of your favorite Turing-machine such that you take some computable injection from (x-tape content, s-machine state, h-position of head) to the integers. In this case Q will be also nice, you don't even need the 0's.</p> <p>If Q is fixed, then proceed similar as before, except now encode (T-description of TM,x,s,h) into the integers and p will have some form like (00001,000011) where the first k zeros take us to the start conditions of the k-th TM.</p> <p>I also suggest that you try posting your problem on <a href="http://cstheory.stackexchange.com/" rel="nofollow">http://cstheory.stackexchange.com/</a> instead of MO.</p> http://mathoverflow.net/questions/122786/is-this-min-not-less-than-a-min/122864#122864 Answer by domotorp for Is this min not less than a min domotorp 2013-02-25T08:59:29Z 2013-02-25T08:59:29Z <p>I think it is not hard to see that the second quantity is minimized by the regular pentagon. First, using Günter's observation, the problem is equivalent to find</p> <p>$$\max_{v_{0},v_{1},v_{2},v_{3},v_{4}\in\partial\mathbf{D}} \min_{0\le i,j,k\le4} \mbox{inradius}(v_i,v_j,v_k).$$</p> <p>If we don't have a regular pentagon, then there are 3 points who are contained in an arc whose length is strictly less than $4\pi/5$, suppose they are $v_1,v_2,v_3$ in this order. The $\mbox{inradius}(v_1,v_2,v_3)$ is maximized if $v_2$ is halfway between $v_1$ and $v_3$. So this quantity will be less than the inradius of three consecutive vertices of the pentagon, which is less than the inradius of three non-consecutive vertices of the pentagon.</p> http://mathoverflow.net/questions/122535/what-properties-does-generalized-delaunay-triangulation-have What properties does generalized Delaunay triangulation have? domotorp 2013-02-21T14:02:40Z 2013-02-21T16:25:09Z <p>Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is a homothet of D that contains both of them on its boundary and no points inside. If the points are in a general position such that no four fall on the boundary of a homothet of D, then we still obtain a triangulation (plus some infinite face). Can anyone provide a good reference for this statement, how should I cite it? I need it not only for smooth D but also for polygons.</p> http://mathoverflow.net/questions/120148/edge-coloring-of-the-complete-graph-without-any-rainbow-paths/120234#120234 Answer by domotorp for Edge-coloring of the complete graph without any rainbow paths domotorp 2013-01-29T17:28:00Z 2013-01-29T17:28:00Z <p>This is an open problem, see the intro of this paper for more details: <a href="http://www.renyi.hu/~gyarfas/Cikkek/136_orthogonal.pdf" rel="nofollow">http://www.renyi.hu/~gyarfas/Cikkek/136_orthogonal.pdf</a></p> http://mathoverflow.net/questions/119785/non-unique-2-factorization-of-2k-regular-graphs/119818#119818 Answer by domotorp for Non-unique 2-factorization of 2k-regular graphs domotorp 2013-01-25T07:48:08Z 2013-01-25T07:48:08Z <p>No and in fact your multigraph construction is the counterexample. Just replace each edge with an "almost 6-regular" graph, like $K_7$ minus one edge, uv, and connect u and v respectively to the endpoints of the original edge.</p> http://mathoverflow.net/questions/119240/majority-vote-of-total-orders/119252#119252 Answer by domotorp for Majority vote of total orders domotorp 2013-01-18T10:55:39Z 2013-01-18T10:55:39Z <p>These tournaments are called majority tournaments and are studied in several papers, e.g.</p> <p><a href="http://www.math.dartmouth.edu/~pw/papers/dice.pdf" rel="nofollow">http://www.math.dartmouth.edu/~pw/papers/dice.pdf</a></p> <p><a href="http://arxiv.org/abs/1109.6172" rel="nofollow">http://arxiv.org/abs/1109.6172</a></p> http://mathoverflow.net/questions/117891/what-are-conjectures-that-are-true-for-primes-but-then-turned-out-to-be-false-for What are conjectures that are true for primes but then turned out to be false for some composite number? domotorp 2013-01-02T19:03:10Z 2013-01-04T17:20:33Z <p>Note: This is an update formulation since many people misunderstood the question before.</p> <p>Of course it is easy to make a statement like "Every n is a prime or at most 1000", which is true for every prime $n$ and every small $n$ but fails for $n=1002$. What are "real" conjectures that were known to hold for primes and small values, then turned out to be false?</p> <p>An excellent example about cyclotomic polynomials was given by Aaron in the comments. Here the conjecture was that the coefficients are $0, \pm 1$ for every $n$. This holds for primes and small $n$'s, but fails for $105$.</p> <p>Also the existence of <a href="http://en.wikipedia.org/wiki/Carmichael_number" rel="nofollow">Carmichael number</a>s comes close, but here the problem itself involves primes, I would like something less "primey". I know conjuctures that are or were known only for primes. Recently <a href="http://arxiv.org/abs/0910.4987" rel="nofollow">solved is Colorful Tverberg</a>, still unknown is <a href="http://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture" rel="nofollow">Evasiveness</a> or <a href="http://mathoverflow.net/questions/26358/can-we-color-z-with-n-colors-such-that-a-2a-na-all-have-different-colors" rel="nofollow">this little MO problem</a>.</p> http://mathoverflow.net/questions/117071/bipartiteness-criterion/117247#117247 Answer by domotorp for Bipartiteness criterion domotorp 2012-12-26T11:45:19Z 2012-12-26T11:45:19Z <p>No, there isn't because deciding whether a hypergraph is bipartite (2-colorable) or not is NP-complete (reduction from NAE-SAT) already for 3-uniform hypergraphs. Of course if by similar you mean something that is not necessarily verifiable in polynomial time, then the answer might be yes...</p> http://mathoverflow.net/questions/116592/complexity-of-a-matching-problem-on-the-grid-mathbb-z2/116717#116717 Answer by domotorp for Complexity of a matching problem on the grid $\mathbb Z^2$ domotorp 2012-12-18T15:54:06Z 2012-12-18T15:54:06Z <p>I am almost sure this problem is NP-complete. The reduction is from Planar 1-in-3-SAT, where we are given a 3CNF and a planar bipartite graph whose vertices are the variables and the clauses, with an edge between them if the corresponding variable is in the given clause. A very sketchy reduction is to start for each variable with 4k points, where k is the number of its occurrences, e.g. with (0,1),(0,2),..,(0,k),(1,0),..,(k,0),(k+1,1),..,(k+1,k),(1,k+1),..,(k,k+1), so we either take k horizontal or k vertical segments. Then our choice is led through a polygonal path to the clause component, which is another simple gadget that requires one incoming path.</p> <p>I know this is not a full proof, in fact I might be wrong, but working out the details is usually a tedious job that goes beyond a MO answer...</p> http://mathoverflow.net/questions/115455/the-optimal-constant-in-vitali-covering-lemma/116198#116198 Answer by domotorp for The optimal constant in Vitali covering lemma domotorp 2012-12-12T20:41:03Z 2012-12-12T20:41:03Z <p>It is not hard to see that we can improve the constant a bit. Denote the ball with the biggest radius by B and its radius by r. If there are two disjoint balls intersecting B with radius at least 0.99r, than put them in S, this will be "locally better" than $\frac 1{3^n}$ as the blow-up of the balls intersect. If there are no two such balls, then put B into S, this is again "locally better" than $\frac 1{3^n}$. Optimizing the constants will probably give something reasonable, but not 2, which I find to be a very nice conjecture.</p> http://mathoverflow.net/questions/115816/zero-subsums-of-integer-vectors/115827#115827 Answer by domotorp for Zero subsums of integer vectors domotorp 2012-12-08T18:56:06Z 2012-12-08T18:56:06Z <p>For n=1 we have recently solved the problem, the answer is around $d^d$, see <a href="http://arxiv.org/abs/0912.0424" rel="nofollow">http://arxiv.org/abs/0912.0424</a> By we I mean my coauthors and by solve I mean gave a reasonable lower and upper bound.</p> http://mathoverflow.net/questions/115477/on-well-separated-point-sets-in-the-plane/115664#115664 Answer by domotorp for On well separated point sets in the plane domotorp 2012-12-07T01:26:01Z 2012-12-07T01:26:01Z <p>No, there is a counterexample. Take a circle, whose diameter is slightly larger than 1 and put |A|-1 points evenly around its boundary and the last point to its center. This set will be 1-separated, but no matter how you partition it, the part containing the center will not be 1-separated.</p> http://mathoverflow.net/questions/111684/does-every-bipartite-graph-with-512-edges-have-an-induced-subgraph-with-256-edges Does every bipartite graph with 512 edges have an induced subgraph with 256 edges? domotorp 2012-11-06T21:14:08Z 2012-11-15T00:23:32Z <p>Suppose we have a (simple) bipartite graph with $2^k$ edges. Is it true that there is a subset of the vertices such that their induced subgraph has exactly $2^{k-1}$ edges?</p> <p>I know that the answer is no for general graphs, since you can take a $K_6$ plus a disjoint edge. I also know that if we don't require the number of edges to be a power of 2, the answer is again no as shown by a $K_{5,9}$ plus a disjoint edge. I suspect that the answer to my question is also no.</p> http://mathoverflow.net/questions/112195/max-of-words-with-restricted-total-content/112219#112219 Answer by domotorp for max # of words with restricted total content domotorp 2012-11-12T20:20:22Z 2012-11-12T20:20:22Z <p>First suppose that L=2. In this case imagine that each element of $\alpha$ is the vertex of a graph and its multiplicity in M is its required degree. (Except that you also allow words like aa, moreover, ab and ba count distinct, but I don't think this really changes the problem.) So whether we can produce |M|/L words or not depends on whether the given sequence is graphic or not. See <a href="http://mathworld.wolfram.com/GraphicSequence.html" rel="nofollow">http://mathworld.wolfram.com/GraphicSequence.html</a></p> <p>Now if L>2, then we don't know the answer to the corresponding hypergraph problem, so probably also your problem is hard. (In the sense that it is probably NP-hard.) See <a href="http://www.math.uiuc.edu/~west/regs/hypergraphic.html" rel="nofollow">http://www.math.uiuc.edu/~west/regs/hypergraphic.html</a></p> http://mathoverflow.net/questions/112067/sperners-lemma-and-paths-from-one-side-to-the-opposite-one-in-a-grid/112098#112098 Answer by domotorp for Sperner's lemma and paths from one side to the opposite one in a grid domotorp 2012-11-11T18:20:04Z 2012-11-11T18:20:04Z <p>This looks very similar to a 45 degree rotated board of the Bridg-it game: <a href="http://www.sites4all.co.uk/bridjit/" rel="nofollow">http://www.sites4all.co.uk/bridjit/</a> (About the winning strategy, see also <a href="http://en.wikipedia.org/wiki/Shannon_switching_game" rel="nofollow">http://en.wikipedia.org/wiki/Shannon_switching_game</a>.)</p> <p>But I really don't see how the existence of no draw (&lt;=> there is a through path) would imply the same in your case. Of course in your example there can also be two through paths.</p> http://mathoverflow.net/questions/111207/looking-for-construction-related-to-erdos-szekeres-theorem/111214#111214 Answer by domotorp for Looking for construction related to Erdos-Szekeres theorem domotorp 2012-11-01T21:04:16Z 2012-11-04T08:26:55Z <p>These runs are strongly related to Young tableaux. So it is the best to first make a tableau that has the corresponding property. This we can construct by induction: Start with 1, then make a copy of it +1 and put it below, then copy it +2 and put it right from it. So you should get: $\begin{array}{cc} 1&amp;3\cr 2&amp;4\cr \end{array}$. After repeating it on, we get $\begin{array}{cccc} 1&amp;3&amp;9&amp;11\cr 2&amp;4&amp;10&amp;12\cr 5&amp;7&amp;13&amp;15\cr 6&amp;8&amp;14&amp;16\cr \end{array}$ and so on.</p> <p>To make a sequence of this, first take the last row of the tableau, then the last but one and so on, so you should get $6, 8, 14, 16, 5, 7, 13, 15, 2, 4, 10, 12, 1, 3, 9, 11$. Now, without giving a formal proof, any long enough run must skip over two correspondingly big "breaks" in the matrix which will make it have a large width. Unless I am mistaken, a run of length $c\sqrt n$ should have width $\Omega(c n)$.</p> <p>Update: I was mistaken, as pointed out by Aaron, so the width should be smaller.</p> http://mathoverflow.net/questions/108090/is-a-row-discrepancy-of-symmetric-row-column-increasing-matrices-unbounded/108168#108168 Answer by domotorp for Is a "row discrepancy" of symmetric row-column increasing matrices unbounded? domotorp 2012-09-26T14:58:34Z 2012-09-27T11:54:27Z <p>This is my updated answer, probably still wrong somewhere...</p> <p>If $A(i,j)=\lfloor (i+j)n/10\rfloor$, then the matrix is symmetric and satisfies strict inequalities if $n$ is at least $10$.</p> <p>Also $A(a_2,j)-A(a_1,j)=(a_2-a_1)n/10$ (plus/minus 1, if you want integers and round the $A(i,j)$'s) and since $b_2-b_1\le n$, we get that $D(R)\le 10$.</p> http://mathoverflow.net/questions/107138/finding-the-matroids-with-a-specified-set-of-non-bases/107239#107239 Answer by domotorp for Finding the matroids with a specified set of non-bases domotorp 2012-09-15T07:31:58Z 2012-09-15T07:31:58Z <p>There are a bit too many parameters - how big is k compared to n, how much is bunch and how fast you want the algorithm to be. In general, there cannot be a very fast algorithm, as there are too many such matroids (many depending on bunch), there could be as many as around $2^{n \choose k}$ such matroids. Unfortunately I only know these results in Hungarian, but nevertheless here is a link if you have someone around you who speaks Hungarian: 2.2.2 of <a href="http://www.cs.elte.hu/~frank/jegyzet/matroid/ulmat.2011.pdf" rel="nofollow">http://www.cs.elte.hu/~frank/jegyzet/matroid/ulmat.2011.pdf</a></p> http://mathoverflow.net/questions/105065/minimizing-the-excursion-of-a-sum-of-unit-vectors/106979#106979 Answer by domotorp for Minimizing the excursion of a sum of unit vectors domotorp 2012-09-12T05:41:50Z 2012-09-12T05:41:50Z <p>This is a famous open problem, $r_{min}\le d$ is known as the Steinitz-lemma. It is conjectured that $r_{min}= O(\sqrt d)$ but even $r_{min}= o(d)$ is open. See also <a href="http://www.renyi.hu/~barany/cikkek/steinitz.pdf" rel="nofollow">http://www.renyi.hu/~barany/cikkek/steinitz.pdf</a> , section 3.</p> http://mathoverflow.net/questions/93365/does-every-polycube-tiling-imply-a-regular-polycube-tiling/106672#106672 Answer by domotorp for Does every polycube tiling imply a regular polycube tiling? domotorp 2012-09-08T14:14:08Z 2012-09-09T21:10:36Z <p>I am almost sure that the answer is no. Your question is strongly related to <a href="http://en.wikipedia.org/wiki/Keller%27s_conjecture" rel="nofollow">Keller's conjecture</a> which turned out to be false. There a tiling of $\mathbb Z^{10}$ was given by translates of the unit cube such that the center of each translate is a halfinteger. Moreover, the tiling has a very strong lattice-like structure, 1024 cubes whose center is in $[0,2]^{10}$ are translated by every vector from $2\mathbb Z^{10}$.</p> <p>Of course, the cube won't give a counterexample to your question. But you can divide each cube from this construction to like $3^{99}$ little cubes and then "dig little tunnels" among adjacent cubes to make sure the resulting polyominos only fit in the given way. This leaves many details to work out and I am not 100% sure it can be done but looks like a promising approach.</p> http://mathoverflow.net/questions/21016/how-hard-is-it-to-solve-sat-if-the-promise-is-that-it-has-an-odd-number-of-soluti How hard is it to solve SAT if the promise is that it has an odd number of solutions? domotorp 2010-04-11T15:39:42Z 2012-08-30T08:39:42Z <p><a href="http://en.wikipedia.org/wiki/Boolean_satisfiability_problem" rel="nofollow">SAT</a> is NP-complete even if we promise that it has an even number of solutions (by introducing a new dummy variable). However, USAT (when the promise is that it has exactly one solution) is not known to be NP-complete (except if we allow randomized reductions). What if we promise an odd number of solutions? The complexity must of course lie between the above two but can we prove that it is deterministically reducible to USAT or that SAT is deterministically reducible to it?</p> <p>Remark. Of course I mean that we promise an odd or zero number of solutions. Or, another related problem would be, to find a solution under the promise. For related results see the excellent "survey" answer by Ryan.</p> http://mathoverflow.net/questions/105471/is-this-stronger-knaster-kuratowski-mazurkiewicz-lemma-true Is this stronger Knaster-Kuratowski-Mazurkiewicz Lemma true? domotorp 2012-08-25T16:04:41Z 2012-08-26T07:10:24Z <p>The Knaster-Kuratowski-Mazurkiewicz Lemma is the continuous analogue of Sperner's lemma. I wonder if the following, more general version is true.</p> <p>Let S be the standard simplex spanned by the standard orthonormal basis for $\mathbb R^{n+1}$, so S equals the convex hull of $(e_i:i\in [n+1])$. Assume we have n+1 closed subsets $C_1, \ldots, C_{n+1}$ with the property that for every subset $I$ of [n+1] the following holds: the convex hull of $(e_i:i\in I)$ is disjoint from $\cup_{i\notin I} C_i$. Is it true that either there are t $C_i$'s that intersect OR there is a k-dimensional "subspace" of S that is disjoint from all the $C_i$'s, if n is large enough (compared to t and k)?</p> <p>By k-dim subspace of S I mean a linear subspace (passing through the origin) whose intersection with S is k-dimensional. Any better formulations of the problem and retags are welcome.</p> <p>Note that for k=0 we get back the KKM lemma. I do not know the answer already for k=1. In case it is false, is it possible to replace the affine subspace by something else?</p> <p>Edit: As Ilya pointed out in the Edit part of his answer, we cannot hope for a k-dim subspace. Any other reasonable "big" manifold we can hope for?</p> http://mathoverflow.net/questions/105458/can-a-simple-curve-intersect-every-subspace-of-dim-2-and-avoid-the-origin Can a simple curve intersect every subspace of dim 2 and avoid the origin? domotorp 2012-08-25T11:37:16Z 2012-08-25T13:17:01Z <p>Is there, e.g. in $\mathbb R^4$ a simple curve that does not contain the origin and intersects every subspace of dimension 2?</p> <p>Sorry if the question is too easy, but I just cannot figure it out. In three dimensions such a curve exists, but I cannot imagine four dimensions. Is it possible to somehow lift-up the Peano-curve? What about higher dimensions and higher dimensional subspaces?</p> http://mathoverflow.net/questions/103433/a-prime-number-pattern/103436#103436 Answer by domotorp for A prime number pattern domotorp 2012-07-29T09:12:39Z 2012-07-29T09:12:39Z <p>I think it is enough to use induction and Bertrand's postulate, that there is always a prime between n and 2n for n>1. Let me try to sketch the proof that we always reach 0, 1 or 2.</p> <p>The induction hypothesis is that taking the primes up to p and starting from any |z|&lt;2p, we reach 0, 1 or 2. Suppose we want to prove this for the next prime after p, denoted by q. We know that q&lt;2p. Initially, |z|&lt;2q. Once we subtract (supposing z>0) q from it, we get z&lt; q&lt; 2p.</p> http://mathoverflow.net/questions/100082/covering-a-hypercube-with-lines/100260#100260 Answer by domotorp for Covering a (hyper)cube with lines domotorp 2012-06-21T17:00:58Z 2012-06-23T12:46:46Z <p>I think the probabilistic method gives an A of size $O_d(n^{d/2}\sqrt\log n)$. (Formula updated according to js's comment.)</p> <p>Put every point to A independently with probability p. What is the probability that a point x will be in S(A)? For any x, we can find $\Omega(n^d)$ pairs of points that are all different such that x lies on the line of any pair. (This is true because e.g. for d=2 if x is in the bottom-left part of $K_n$, then we can take the $n/4\times n/4$ grid upper-right from it, contract the $n/8 \times n/8$ bottom-left of this grid, and double each point from x to get its pair.)</p> <p>The probability that both points of a fixed pair are in A is $p^2$, the probability that no such pair exists is $(1-p^2)^{n^d}$. So if $n^d(1-p^2)^{n^d}&lt;1$, then we are done using the union bound. Unless I am mistaken this is true if $p>\Omega_d(n^{-d/2}\sqrt\log n)$.</p> <p>Now of course we cannot be sure about how big A is. But if we replace the above $&lt;1$ with a $&lt;1/2$, then we can even add the condition that A should be at most $pn^d$, for which the probability is $\ge 1/2$. So we get $O_d(n^{d/2}\sqrt\log n)$ points. Maybe this can be further improved with some more advanced probabilistic methods.</p> http://mathoverflow.net/questions/99642/p-q-versus-glivenko-cantelli/100024#100024 Answer by domotorp for (p,q) versus Glivenko-Cantelli domotorp 2012-06-19T16:59:30Z 2012-06-19T16:59:30Z <p>I think the (p,q) theorem is completely different from Glivenko-Cantelli. Why do you say that the convex sets form a GL class? Consider the following family in R: Intervals containing 0 or 1. This is a (3,2) family but it is not GL, as it contains the {0} point. (Of course if you change the measure and concentrate it on {0,1}, then this does become a GL class, which is not surprising knowing the proof of the (p,q) theorem.) </p> http://mathoverflow.net/questions/93796/on-the-number-of-lines-of-given-points/94129#94129 Answer by domotorp for On the number of lines of given points domotorp 2012-04-15T16:32:33Z 2012-04-15T16:32:33Z <p>1, Yes, it only holds with at least two, otherwise you get the ordinary lines problem, for which the answer is linear in n, for more see <a href="http://mathworld.wolfram.com/OrdinaryLine.html" rel="nofollow">http://mathworld.wolfram.com/OrdinaryLine.html</a></p> <p>2, No, you miss something, I think it is correct on wikipedia (or I miss some logic...)</p> http://mathoverflow.net/questions/94116/is-there-an-upper-bound-on-the-number-of-uppersets-antichains-in-a-partially-orde/94128#94128 Answer by domotorp for Is there an upper bound on the number of uppersets/antichains in a partially ordered set domotorp 2012-04-15T16:26:56Z 2012-04-15T16:26:56Z <p>If the poset is a power set, then the answer is $2^{{n \choose n/2}(1-o(1))}$.</p> <p>A brief history of the problem:</p> <p><a href="http://mathworld.wolfram.com/DedekindsProblem.html" rel="nofollow">http://mathworld.wolfram.com/DedekindsProblem.html</a></p> <p><a href="http://oeis.org/A014466" rel="nofollow">http://oeis.org/A014466</a></p> <p><a href="http://www.ams.org/journals/proc/1969-021-03/S0002-9939-1969-0241334-6/S0002-9939-1969-0241334-6.pdf" rel="nofollow">http://www.ams.org/journals/proc/1969-021-03/S0002-9939-1969-0241334-6/S0002-9939-1969-0241334-6.pdf</a></p> http://mathoverflow.net/questions/85606/density-in-van-der-waerdens-theorem/93380#93380 Answer by domotorp for Density in van der Waerden's theorem domotorp 2012-04-07T03:42:05Z 2012-04-07T03:42:05Z <p>They grow very fast. Denote by N(l) the largest integer such that we can color the numbers with two colors from 1 to N(l) without an l-long arithmetic progression. Now if you use this coloring for (k-1)/2-long sequences and put such colorings after each other, then any k-long arithmetic progression will be longer than N((k-1)/2), which means that even its difference will be at least N((k-1)/2)/k, which is HUGE.</p> http://mathoverflow.net/questions/131413/in-what-rigorous-sense-are-sperners-lemma-and-the-brouwer-fixed-point-theorem-eq/131414#131414 Comment by domotorp domotorp 2013-05-22T08:19:21Z 2013-05-22T08:19:21Z For someone not into axioms, this can be the proof that they are practically &quot;equivalent&quot; - only one more line (compactness) is needed to derive Brouwer from Sperner. http://mathoverflow.net/questions/126696/ghandhan-problem-general-number-problem-on-divisor Comment by domotorp domotorp 2013-04-06T08:11:50Z 2013-04-06T08:11:50Z This is homework level. http://mathoverflow.net/questions/122786/is-this-min-not-less-than-a-min/122864#122864 Comment by domotorp domotorp 2013-03-30T06:53:01Z 2013-03-30T06:53:01Z I think all functions are differentiable in this problem. Or is your problem the max? It only takes the max of a few functions, so it should not cause a big problem. http://mathoverflow.net/questions/125488/hobbled-rook-tour-hamiltonian-cycle-on-square-grid Comment by domotorp domotorp 2013-03-27T08:18:17Z 2013-03-27T08:18:17Z I have three comments: 1, Meanders are different, there a vertex can be touched twice. 2, There is a related game called Slitherlink. 3, Similar (stronger/weaker?) concept is called Balanced Gray code. http://mathoverflow.net/questions/123456/a-question-about-the-size-of-a-l1-ball/125385#125385 Comment by domotorp domotorp 2013-03-24T07:16:03Z 2013-03-24T07:16:03Z (3) You are right, this is a problem indeed. If $s^*$ is some fix distribution with positive entries while $n\rightarrow\infty$, then the proof is correct, but otherwise not necessarily. E.g., if $s^*$ is zero in all but one row, then we cannot put any coins in the other rows, so we simply get $2^{|\mathcal Y|\log n}$. Either the Lemma is incorrect, or they allow negative entries, or something else is known about $s^*$. http://mathoverflow.net/questions/123456/a-question-about-the-size-of-a-l1-ball/125385#125385 Comment by domotorp domotorp 2013-03-24T07:09:53Z 2013-03-24T07:09:53Z (2) I don't see what is the question here - is it why the distribution is close to even in most cases? You can simply upper bound the cases when in a row the total is, say, 1/10 of the given value and see these do not contribute much. http://mathoverflow.net/questions/123456/a-question-about-the-size-of-a-l1-ball/125385#125385 Comment by domotorp domotorp 2013-03-24T07:07:50Z 2013-03-24T07:07:50Z (1) Because that is approximately that much. If you some from $\sqrt n/2$ to $\sqrt n$, you already get about this much. http://mathoverflow.net/questions/124604/turing-complete-primitive-blind-automata/124767#124767 Comment by domotorp domotorp 2013-03-17T17:35:58Z 2013-03-17T17:35:58Z Well, I told you I probably don't understand the question... http://mathoverflow.net/questions/122535/what-properties-does-generalized-delaunay-triangulation-have/122544#122544 Comment by domotorp domotorp 2013-03-01T16:10:13Z 2013-03-01T16:10:13Z It seems that I have misunderstood the definition of reference-request, thank you for your answer. http://mathoverflow.net/questions/122535/what-properties-does-generalized-delaunay-triangulation-have Comment by domotorp domotorp 2013-02-27T13:56:56Z 2013-02-27T13:56:56Z Cross-posted on CSTheory: <a href="http://cstheory.stackexchange.com/questions/16661/what-properties-does-a-generalized-delaunay-triangulation-have" rel="nofollow" title="what properties does a generalized delaunay triangulation have">cstheory.stackexchange.com/questions/16661/&hellip;</a> http://mathoverflow.net/questions/122535/what-properties-does-generalized-delaunay-triangulation-have/122544#122544 Comment by domotorp domotorp 2013-02-27T13:55:36Z 2013-02-27T13:55:36Z I managed to access the book, it does not even mention Delaunay triangulations. http://mathoverflow.net/questions/122786/is-this-min-not-less-than-a-min/122864#122864 Comment by domotorp domotorp 2013-02-26T17:03:00Z 2013-02-26T17:03:00Z I think it would be the simplest to find the extreme configuration for that problem too but that seems harder, but probably not much. Maybe you can show by using Lagrange multipliers where the extreme value is. http://mathoverflow.net/questions/122535/what-properties-does-generalized-delaunay-triangulation-have/122544#122544 Comment by domotorp domotorp 2013-02-22T16:12:58Z 2013-02-22T16:12:58Z Thank you, I think I will cite the book, as in the dissertation the simple properties are not stated. (I hope they are in the book, since I could not access it.) Also, here is a direct link to the dissertation: <a href="http://www.fernuniversitaethagen.de/imperia/md/content/fakultaetfuermathematikundinformatik/forschung/berichte/bericht_267.pdf" rel="nofollow">fernuniversitaethagen.de/imperia/md/content/&hellip;</a> http://mathoverflow.net/questions/121227/invariant-measures-for-cellular-automata Comment by domotorp domotorp 2013-02-09T19:13:06Z 2013-02-09T19:13:06Z @R W: I think that if you have x followed by y, then you must take the x+1-st row of the matrix and the y+1-st column of it to get the new value of x. http://mathoverflow.net/questions/119785/non-unique-2-factorization-of-2k-regular-graphs/119818#119818 Comment by domotorp domotorp 2013-01-28T13:27:40Z 2013-01-28T13:27:40Z Let me counter-question - what is known about moving between 1-factorizations of regular bipartite graphs?