User domotorp - MathOverflow

Answer by domotorp for A question about the size of a L1 ball

2013-03-23T15:51:28Z

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

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!!!):

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.

Answer by domotorp for Turing-complete primitive blind automata

2013-03-17T09:58:23Z

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.

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.

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.

I also suggest that you try posting your problem on http://cstheory.stackexchange.com/ instead of MO.

Answer by domotorp for Is this min not less than a min

2013-02-25T08:59:29Z

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

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

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.

What properties does generalized Delaunay triangulation have?

2013-02-21T14:02:40Z

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.

Answer by domotorp for Edge-coloring of the complete graph without any rainbow paths

2013-01-29T17:28:00Z

This is an open problem, see the intro of this paper for more details: http://www.renyi.hu/~gyarfas/Cikkek/136_orthogonal.pdf

Answer by domotorp for Non-unique 2-factorization of 2k-regular graphs

2013-01-25T07:48:08Z

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.

Answer by domotorp for Majority vote of total orders

2013-01-18T10:55:39Z

These tournaments are called majority tournaments and are studied in several papers, e.g.

http://www.math.dartmouth.edu/~pw/papers/dice.pdf

http://arxiv.org/abs/1109.6172

What are conjectures that are true for primes but then turned out to be false for some composite number?

2013-01-02T19:03:10Z

Note: This is an update formulation since many people misunderstood the question before.

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?

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

Also the existence of Carmichael numbers 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 solved is Colorful Tverberg, still unknown is Evasiveness or this little MO problem.

Answer by domotorp for Bipartiteness criterion

2012-12-26T11:45:19Z

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

Answer by domotorp for Complexity of a matching problem on the grid $\mathbb Z^2$

2012-12-18T15:54:06Z

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.

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

Answer by domotorp for The optimal constant in Vitali covering lemma

2012-12-12T20:41:03Z

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.

Answer by domotorp for Zero subsums of integer vectors

2012-12-08T18:56:06Z

For n=1 we have recently solved the problem, the answer is around $d^d$, see http://arxiv.org/abs/0912.0424 By we I mean my coauthors and by solve I mean gave a reasonable lower and upper bound.

Answer by domotorp for On well separated point sets in the plane

2012-12-07T01:26:01Z

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.

Does every bipartite graph with 512 edges have an induced subgraph with 256 edges?

2012-11-06T21:14:08Z

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?

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.

Answer by domotorp for max # of words with restricted total content

2012-11-12T20:20:22Z

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 http://mathworld.wolfram.com/GraphicSequence.html

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 http://www.math.uiuc.edu/~west/regs/hypergraphic.html

Answer by domotorp for Sperner's lemma and paths from one side to the opposite one in a grid

2012-11-11T18:20:04Z

This looks very similar to a 45 degree rotated board of the Bridg-it game: http://www.sites4all.co.uk/bridjit/ (About the winning strategy, see also http://en.wikipedia.org/wiki/Shannon_switching_game.)

But I really don't see how the existence of no draw (<=> there is a through path) would imply the same in your case. Of course in your example there can also be two through paths.

Answer by domotorp for Looking for construction related to Erdos-Szekeres theorem

2012-11-01T21:04:16Z

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&3\cr 2&4\cr \end{array}$. After repeating it on, we get $\begin{array}{cccc} 1&3&9&11\cr 2&4&10&12\cr 5&7&13&15\cr 6&8&14&16\cr \end{array}$ and so on.

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

Update: I was mistaken, as pointed out by Aaron, so the width should be smaller.

Answer by domotorp for Is a "row discrepancy" of symmetric row-column increasing matrices unbounded?

2012-09-26T14:58:34Z

This is my updated answer, probably still wrong somewhere...

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

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

Answer by domotorp for Finding the matroids with a specified set of non-bases

2012-09-15T07:31:58Z

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 http://www.cs.elte.hu/~frank/jegyzet/matroid/ulmat.2011.pdf

Answer by domotorp for Minimizing the excursion of a sum of unit vectors

2012-09-12T05:41:50Z

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 http://www.renyi.hu/~barany/cikkek/steinitz.pdf , section 3.

Answer by domotorp for Does every polycube tiling imply a regular polycube tiling?

2012-09-08T14:14:08Z

I am almost sure that the answer is no. Your question is strongly related to Keller's conjecture 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}$.

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.

How hard is it to solve SAT if the promise is that it has an odd number of solutions?

2010-04-11T15:39:42Z

SAT 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?

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.

Is this stronger Knaster-Kuratowski-Mazurkiewicz Lemma true?

2012-08-25T16:04:41Z

The Knaster-Kuratowski-Mazurkiewicz Lemma is the continuous analogue of Sperner's lemma. I wonder if the following, more general version is true.

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

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.

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?

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?

Can a simple curve intersect every subspace of dim 2 and avoid the origin?

2012-08-25T11:37:16Z

Is there, e.g. in $\mathbb R^4$ a simple curve that does not contain the origin and intersects every subspace of dimension 2?

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?

Answer by domotorp for A prime number pattern

2012-07-29T09:12:39Z

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.

The induction hypothesis is that taking the primes up to p and starting from any |z|<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<2p. Initially, |z|<2q. Once we subtract (supposing z>0) q from it, we get z< q< 2p.

Answer by domotorp for Covering a (hyper)cube with lines

2012-06-21T17:00:58Z

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

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

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

Now of course we cannot be sure about how big A is. But if we replace the above $<1$ with a $<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.

Answer by domotorp for (p,q) versus Glivenko-Cantelli

2012-06-19T16:59:30Z

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

Answer by domotorp for On the number of lines of given points

2012-04-15T16:32:33Z

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 http://mathworld.wolfram.com/OrdinaryLine.html

2, No, you miss something, I think it is correct on wikipedia (or I miss some logic...)

Answer by domotorp for Is there an upper bound on the number of uppersets/antichains in a partially ordered set

2012-04-15T16:26:56Z

If the poset is a power set, then the answer is $2^{{n \choose n/2}(1-o(1))}$.

A brief history of the problem:

http://mathworld.wolfram.com/DedekindsProblem.html

http://oeis.org/A014466

http://www.ams.org/journals/proc/1969-021-03/S0002-9939-1969-0241334-6/S0002-9939-1969-0241334-6.pdf

Answer by domotorp for Density in van der Waerden's theorem

2012-04-07T03:42:05Z

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.

Comment by domotorp

2013-05-22T08:19:21Z

For someone not into axioms, this can be the proof that they are practically "equivalent" - only one more line (compactness) is needed to derive Brouwer from Sperner.

Comment by domotorp

2013-04-06T08:11:50Z

This is homework level.

Comment by domotorp

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.

Comment by domotorp

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.

Comment by domotorp

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

Comment by domotorp

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.

Comment by domotorp

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.

Comment by domotorp

2013-03-17T17:35:58Z

Well, I told you I probably don't understand the question...

Comment by domotorp

2013-03-01T16:10:13Z

It seems that I have misunderstood the definition of reference-request, thank you for your answer.

Comment by domotorp

2013-02-27T13:56:56Z

Cross-posted on CSTheory: cstheory.stackexchange.com/questions/16661/…

Comment by domotorp

2013-02-27T13:55:36Z

I managed to access the book, it does not even mention Delaunay triangulations.

Comment by domotorp

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.

Comment by domotorp

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: fernuniversitaethagen.de/imperia/md/content/…

Comment by domotorp

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.

Comment by domotorp

2013-01-28T13:27:40Z

Let me counter-question - what is known about moving between 1-factorizations of regular bipartite graphs?