User dmitryz - MathOverflow

Uniform 4-hypergraph avoiding 2-cycles

2013-05-30T22:00:50Z

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: http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=8514699). 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.

Answer by DmitryZ for Existence of a solution to a system of Diophantine Inequalities

2013-05-30T22:19:53Z

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)

Integer dynamics hitting infinitely many primes

2013-04-26T00:10:18Z

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. S. This question seems to be related to the Bunyakovsky conjecture, so maybe somebody knows about any partial results in this direction?

Distinct prime multiples on an interval

2013-01-22T14:51:58Z

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 http://www.math.dartmouth.edu/~carlp/PDF/matching.pdf):

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

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

More positive pivotal edges than negative ones at critical bond percolation on Z^2?

2012-10-13T15:29:00Z

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

Is a "row discrepancy" of symmetric row-column increasing matrices unbounded?

2012-09-25T19:28:40Z

Let $A$ be a symmetric row-column increasing $n \times n$ matrix (i.e. $A(i, j) < A(i+1,j)$ and $A(i, j) < 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.

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

Hypercube isoperimetric inequality for non-increasing events

2012-08-23T21:05:06Z

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

Now, the question follows:

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?

More generally, can one bound $|D^+|-|D^-|$ to get an analog of sharp threshold results for symmetric but not necessary increasing events?

Comment by DmitryZ

2013-05-31T06:41:42Z

Nice answer! could you suggest a good reading on design theory?

Comment by DmitryZ

2013-05-31T04:42:43Z

the inequality is $|b_ic mod 1| > 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.

Comment by DmitryZ

2013-05-30T22:39:08Z

Ah, so if $a$ is given the last inequality can be satisfied if $a > 4$ or so.

Comment by DmitryZ

2013-05-30T22:35:22Z

Basically, for each $b_i$, you take $d_i$ such that $d_i+1-o(1) > b_ic > d_i+o(1)$. To be able to find such $d_i$ you just need $$\|b_ic\| > 2*o(1)$$ which is possible provided $a$ is sufficiently large.

Comment by DmitryZ

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

Comment by DmitryZ

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

Comment by DmitryZ

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.

Comment by DmitryZ

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

Comment by DmitryZ

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

Comment by DmitryZ

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 "EVERY MONOTONE GRAPH PROPERTY HAS A SHARP THRESHOLD". One could say much more for symmetric events in this case.