User dmitryz - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T18:37:37Z http://mathoverflow.net/feeds/user/25905 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/132372/uniform-4-hypergraph-avoiding-2-cycles Uniform 4-hypergraph avoiding 2-cycles DmitryZ 2013-05-30T22:00:50Z 2013-05-31T07:54:41Z <p>There is a paper by Gy\H{o}ry and Lemons "Hypergraphs with No Cycle of a Given Length", which bounds number of hyperedges for hypergraphs avoiding cycles of length $2k$ (unfortunately, I have access only to the abstract: <a href="http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=8514699" rel="nofollow">http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=8514699</a>). Particularly, in the case of a uniform 4-hypergraph avoiding 2-cycles it seems to provide $O(n^2)$ bound. I am wondering if it is possible to improve this to $o(n^2)$ or it is sharp? Here 2-cycle simply means two hyperedges $E_1, E_2$ which intersect in $2$ vertices.</p> http://mathoverflow.net/questions/132370/existence-of-a-solution-to-a-system-of-diophantine-inequalities/132375#132375 Answer by DmitryZ for Existence of a solution to a system of Diophantine Inequalities DmitryZ 2013-05-30T22:19:53Z 2013-05-30T22:19:53Z <p>If you divide on $a$ and let $a$ to be big you have basically a set of linear inequalities of the form $1-o(1) \geq b_ic-d_i \geq o(1)$. If you look at $b_ic$ geometrically, it is a beam of lines emanating from zero with slopes $b_1, ..., b_{a-1}$. And you want to find a point $c$ such that the line $x = c$ intersects each line in a strip $1+d_i-o(1) \geq y \geq d_i+o(1)$. It seems that if you order the lines according to the slope and starting from the line with the smallest slope (smallest $b_i$) it is possible to choose $d_i$ for each new line appropriately (based on the geometric representation above)</p> http://mathoverflow.net/questions/128780/integer-dynamics-hitting-infinitely-many-primes Integer dynamics hitting infinitely many primes DmitryZ 2013-04-26T00:10:18Z 2013-05-02T05:16:27Z <p>I am wondering if there are any rigorous results telling that some dynamical system hits infinitely many primes (except for the case when orbits are just arithmetic progressions). To make it specific, is there a polynomial $f(x)$ such that its iterations $f^n(x)$ are prime for infinitely many $n$ given that the integer $x$ is fixed. A simple observation here is that if $f(x) = 2x + 1$ then asking if iterations of $f(1)$ contain infinitely many primes is equivalent to the Mersenne primes conjecture. </p> <p>P. S. This question seems to be related to the Bunyakovsky conjecture, so maybe somebody knows about any partial results in this direction?</p> http://mathoverflow.net/questions/119573/distinct-prime-multiples-on-an-interval Distinct prime multiples on an interval DmitryZ 2013-01-22T14:51:58Z 2013-01-22T14:51:58Z <p>Back to 1980, P.Erd\H{o}s and C. Pomerance asked in their paper "Matching the natural numbers up to n with distinct multiples in another interval" (see page 160 of the journal scan <a href="http://www.math.dartmouth.edu/~carlp/PDF/matching.pdf" rel="nofollow">http://www.math.dartmouth.edu/~carlp/PDF/matching.pdf</a>):</p> <p>"Related to these questions, we ask if there is a large constant $c$ so that in any interval of length $cn$ there are $\pi(n)-\pi(n/2)$ distinct multiples of the primes in $(n/2, n]$ (there need not be a matching). "</p> <p>I am wondering if there is any progress on this question. Also, can we say anything if we require only some prime multiples to be present (e. g. we want to guarantee that there are distinct multiples of at least $O(n/\log n)$ primes from $(n/2, n]$)? </p> http://mathoverflow.net/questions/109537/more-positive-pivotal-edges-than-negative-ones-at-critical-bond-percolation-on-z More positive pivotal edges than negative ones at critical bond percolation on Z^2? DmitryZ 2012-10-13T15:29:00Z 2012-10-13T15:38:59Z <p>Consider critical bond percolation on $\mathbb{Z}^2$ inside a fixed rectangle $(0,0) - (an,n), a \geq 1$ and write $A$ for the event that there is an open crossing in the long (left to right) direction. For each configuration $\omega \in A$ one can define pivotal edges as such open edges in $w$, closure of which seizes the crossing. Let us call a pivotal edge $e$ positive (resp. negative) if passing through $e$ in our LR crossing (since it is pivotal, there is only one way to do so) we go outwards (resp. towards) the origin. It is known that at criticality the expected number of all pivotal edges is of order $\log n$. The question is, is it true that positive pivotal edges dominate negative ones such that the expectation of the difference goes to infinity as well? Can one prove that it is at least positive for large $n$?</p> <p>P. S. I would also appreciate a reference or an exposition of original Kesten's geometrical arguments to prove the $\log n$ estimate. It seems that modern books rely either on sharp threshold results (B. Bollobas, O. Riordan) or to exponential decay for subcritical values (G. Grimmett).</p> http://mathoverflow.net/questions/108090/is-a-row-discrepancy-of-symmetric-row-column-increasing-matrices-unbounded Is a "row discrepancy" of symmetric row-column increasing matrices unbounded? DmitryZ 2012-09-25T19:28:40Z 2012-09-27T14:57:24Z <p>Let $A$ be a symmetric row-column increasing $n \times n$ matrix (i.e. $A(i, j) &lt; A(i+1,j)$ and $A(i, j) &lt; A(i, j+1)$) with integer entries $A(i, j) \in \{1, 2, ..., n^2\}$. Moreover, let us assume that $A$ contains $\Theta(n^2)$ distinct entries, so the set of entries has positive density. </p> <p>Define a "row discrepancy" for a rectangle $R=\{A(i,j); a_1 \leq i \leq a_2, b_1 \leq j \leq b_2 \}$ as $$D(R) = \frac{(a_2-a_1)(b_2-b_1)}{\max_{b_1 \leq j \leq b_2} (A(a_2, j)-A(a_1, j))}.$$ Let us also define the total "row discrepancy" $D_r$ as a supremum of $D(R)$ over all rectangles $R$. Is it true that $D_r$ must go to infinity as $n \to \infty$ for any $A$?</p> http://mathoverflow.net/questions/105353/hypercube-isoperimetric-inequality-for-non-increasing-events Hypercube isoperimetric inequality for non-increasing events DmitryZ 2012-08-23T21:05:06Z 2012-08-24T20:26:53Z <p>It is well known that isoperimetric inequalities on a hypercube are closely related to influences, but all the theorems I'm aware of deal with monotone sets. Now suppose we have an arbitrary set $X \subset \{0, 1\}^n$, and let us color all vertices of a hypercube that lie in $X$ in black, others in white. The boundary edges (which have their endpoints colored in different colors), are of two types: going in positive direction we either go from white to black (positive influence) or from black to white (negative influence). Let us denote these edge sets by $D^+$ and $D^-$.</p> <p>Now, the question follows:</p> <p>Suppose that every node in $X$ is connected to $(1,1,...,1)$ (which belongs to $X$ as well) by a path that consists of only increasing edges (that is, following such path we always switch some coordinate from $0$ to $1$ and not otherwise). Suppose also that $P(X) = 1/2$, assuming the uniform measure on a hypercube. Moreover, let $X$ be symmetric. Is it true that $|D^+|-|D^-| > 0$? If not, what additional conditions should be posed on $X$ to make it true?</p> <p>More generally, can one bound $|D^+|-|D^-|$ to get an analog of sharp threshold results for symmetric but not necessary increasing events?</p> http://mathoverflow.net/questions/132372/uniform-4-hypergraph-avoiding-2-cycles/132390#132390 Comment by DmitryZ DmitryZ 2013-05-31T06:41:42Z 2013-05-31T06:41:42Z Nice answer! could you suggest a good reading on design theory? http://mathoverflow.net/questions/132370/existence-of-a-solution-to-a-system-of-diophantine-inequalities/132375#132375 Comment by DmitryZ DmitryZ 2013-05-31T04:42:43Z 2013-05-31T04:42:43Z the inequality is $|b_ic mod 1| &gt; 2/a$. so if a is less or equal to 4 it cannot be satisfied. otherwise i believe it something similar to the Kronecker approximation theorem, but i didn't write it down rigourously. http://mathoverflow.net/questions/132370/existence-of-a-solution-to-a-system-of-diophantine-inequalities/132375#132375 Comment by DmitryZ DmitryZ 2013-05-30T22:39:08Z 2013-05-30T22:39:08Z Ah, so if $a$ is given the last inequality can be satisfied if $a &gt; 4$ or so. http://mathoverflow.net/questions/132370/existence-of-a-solution-to-a-system-of-diophantine-inequalities/132375#132375 Comment by DmitryZ DmitryZ 2013-05-30T22:35:22Z 2013-05-30T22:35:22Z Basically, for each $b_i$, you take $d_i$ such that $d_i+1-o(1) &gt; b_ic &gt; d_i+o(1)$. To be able to find such $d_i$ you just need $$\|b_ic\| &gt; 2*o(1)$$ which is possible provided $a$ is sufficiently large. http://mathoverflow.net/questions/128780/integer-dynamics-hitting-infinitely-many-primes/128800#128800 Comment by DmitryZ DmitryZ 2013-04-28T09:38:46Z 2013-04-28T09:38:46Z thanks, Nilothal, but it looks like it difficult to prove anything useful about this number, so it hardly helps for integer dynamics http://mathoverflow.net/questions/108090/is-a-row-discrepancy-of-symmetric-row-column-increasing-matrices-unbounded/108168#108168 Comment by DmitryZ DmitryZ 2012-09-28T04:17:05Z 2012-09-28T04:17:05Z @domotorp You're right again. I should think more what are plausible conditions to make the question more interesting. My initial intuition was that if the matrix is dense in a sense it contains, say, all consecutive numbers $\\{1,..,cn^2\\$ than you can't avoid small jumps between neighboring entries keeping it row-column increasing symmetric. For example, if $S_i$ are entries $ni, ..., \(n+1)i$ than we have a partition of the square to approx $n$ symmetric row-column convex sets $S_i$ of size $n$ such that almost all rows contain elements from almost all of $S_i$. http://mathoverflow.net/questions/108090/is-a-row-discrepancy-of-symmetric-row-column-increasing-matrices-unbounded/108168#108168 Comment by DmitryZ DmitryZ 2012-09-27T14:54:21Z 2012-09-27T14:54:21Z @domotorp OK you're right. To avoid such counterexamples one should add that $A$ must contain $\Theta(n^2)$ distinct entries, which is important. I have updated the question. http://mathoverflow.net/questions/108090/is-a-row-discrepancy-of-symmetric-row-column-increasing-matrices-unbounded/108168#108168 Comment by DmitryZ DmitryZ 2012-09-27T10:23:27Z 2012-09-27T10:23:27Z @domotorp As Ilya said, the matrix should be symmetric. But you're right, $A(i,j) = n*(i-1)+j$ gives a counterexample in the non-symmetric case. P. S. It's more convenient to consider $A(i, j) \in \\{1,...,n^2\\}$, see the update http://mathoverflow.net/questions/105353/hypercube-isoperimetric-inequality-for-non-increasing-events/105366#105366 Comment by DmitryZ DmitryZ 2012-08-24T14:12:27Z 2012-08-24T14:12:27Z Thank you for the insightful answer! It's interesting if one can make your counterexample symmetric (in a sense I describe above). http://mathoverflow.net/questions/105353/hypercube-isoperimetric-inequality-for-non-increasing-events Comment by DmitryZ DmitryZ 2012-08-24T14:07:35Z 2012-08-24T14:07:35Z Sorry for being sloppy with this. I mean that there is a transitive permutation group $\Gamma$ on $\\{1,...,n\\}$ such that $X$ is invariant under $\Gamma$. I was keeping in mind the monotone case, considered e.g. in E. Freidgut, G. Kalai &quot;EVERY MONOTONE GRAPH PROPERTY HAS A SHARP THRESHOLD&quot;. One could say much more for symmetric events in this case.