User boris bukh - MathOverflow

Answer by Boris Bukh for Dimension of incomplete matrix over finite fields.

2013-04-30T13:16:59Z

It is true. Let $N=2^n$ be the dimension, and $q=p^k$ be the size of the field. Let $v_i$ be the $i$'th column vector. Define multiplication of vectors coordinate-wise, i.e., $uu'$ is vector whose $i$'th coordinate is $u_i u'_i$. Similarly, for a vector $u$ define $u^r$ be the result of raising all the elements of $u$ to $r$'th power. Note that the vectors $v_1^{q-1},\dotsc,v_N^{q-1}$ are linearly independent.

Suppose, now that the rank of the matrix is $r$, i.e, some $r$ column vectors span the column space. Without loss, every $v_i$ is a linear combination of $v_1,\dotsc,v_r$. Let $S$ be the set of all the products of $q-1$ vectors from ${v_1,\dotsc,v_r}$ (repeations are allowed). If $$v_i=\sum_{j=1}^r \alpha_j v_j,$$ then $$v_i^{q-1}=\left(\sum_{j=1}^r \alpha_j v_j\right)^{q-1}=\sum_{j_1,\dotsc,j_{q-1}=1}^r (\alpha_{j_1}\dotsb\alpha_{j_{q-1}}) v_{j_1}\dotsb v_{j_{q-1}}$$ is a linear combination of vectors from $S$. Since $v_i^{q-1}$'s are linearly independent, we conclude that $|S|\geq N$. Since $|S|\leq r^{q-1}$, it follows that the rank is $$r\geq N^{1/(q-1)}.$$

This argument is a variation on the proofs of Frankl–Wilson theorem, and of Ray-Chaudhuri–Wilson theorem.

Answer by Boris Bukh for Intersection of 2 visibility polygons

2013-04-30T11:53:14Z

The answer is yes. I do not see a clean proof. Here is a proof by case-checking. Consider two points $q$ and $q'$ that are visible from both $p_1$ and $p_2$. There are several cases:

1) Suppose four points $p_1$, $p_2$, $q$, $q'$ are in convex position, and points $p_1$, $p_2$ are opposite vertices of the convex hull. Then convex hull is completely inside the polygon, and in particular in the intersection of two visibility polygons. Thus, $q$ and $q'$ are in the same connected component.

2) Four points $p_1$, $p_2$, $q$, $q'$ are in convex position, and points $p_1$, $p_2$ are adjacent vertices of the convex hull. Without loss, assume that the order is $p_1$, $p_2$, $q$, $q'$. Let $r$ be the intersection point of line segments $p_1q$ and $p_2q'$. Then the line segments $qr$ and $q'r$ are contained in the intersection of visibility regions.

3) Point $q$ is in the convex hull of $p_1$, $p_2$ and $q'$. Then the nonconvex $4$-gon $p_1qp_2q'$ is in the intersection of visibility polygons, and line segment $qq'$ is completely contained in it.

4) Point $p_1$ is in the convex hull of $p_2$, $q$ and $q'$. In that case the line segments $qp_1$ and $q'p_1$ are in both visibility polygons. Again, $q$ and $q'$ are connected.

Answer by Boris Bukh for A generalisation of Sperner families (union-free families)

2013-03-19T11:52:33Z

For $k=3$ case, there is a result of Kleitman, Shearer and Sturtevant, which gives a bound of $2^{0.7549 n}$ on the size of $C$. In fact they show a similar bound for a $k$-uniform family for any $k$. In a follow-up paper by Alon an explicit set family of exponential size is constructed.

Answer by Boris Bukh for Estimating L1 functions over the ball with radius 2r

2013-03-15T20:48:28Z

The answer is negative. Let $n=1$, $\Omega=(0,\infty)$ and $f(x)=\min\bigl(1/x^2,1\bigr)$. Let $x_i=2\cdot 4^i$ and $r_i=4^i$. Then $B(x_i,2r_i)$ contains $(0,1)$, and so $\int_{B(x_i,r_i)} |f|\geq \int_0^1 |f|=1$. Therefore, the putative function $g$ satisfies $$\int_0^\infty |g|\geq \sum_{i=1}^\infty \int_{B(x_i,r_i)} |g|\geq \sum_{i=1}^\infty \frac{1}{C}\int_{B(x_i,r_i)} |f|\geq \sum_{i=1}^\infty \frac{1}{C}=\infty.$$

Counting roots: multidimensional Sturm's theorem

2010-10-28T14:37:14Z

Sturm's theorem gives a way to compute the number of roots of a one-variable polynomial in an interval [a,b]. Is there a generalization to boxes in higher dimensions? Namely, let $P_1,\dotsc,P_n\in \mathbb{R}[X_1,\dotsc,X_n]$ be a collection of $n$ polynomials such that there are only finitely many roots of $P_1=P_2=\dotsb=P_n=0$. I want to be able to compute the number of roots in $[a,b]^n$. I do not care if the roots are counted with or without multiplicity.

I would also be interested in upper bounds on the number of roots that is similar to Descartes' rule of signs. The only work in this connection that I managed to find is by Itenberg and Roy, who postulated a conjectural extension of Descartes' rule of signs, which however later was shown to be false.

Answer by Boris Bukh for A mixing property for finite fields of characteristic $2$

2012-07-24T16:08:11Z

This is a justification of Peter Mueller's guess. Write $n=|\mathbb{F}|$ and put $m=\delta n$ where $\delta>1-1/e$ is arbitrary. Let $\phi_0$ be a random function, chosen uniformly from among all functions $\mathbb{F}\to\mathbb{F}$. For each $a$, the function $\phi_a$ is uniformly distributed. Let $X$ be the size of image of $\phi_0$. Let $p=\Pr[X>m]$. If $pn<1$, then there is a choice of $\phi_0$ such the image of $\phi_a$ is at most $m$. The expected size of $X$ is $\bigl(1-1/e+o(1)\bigr)n$ since the probability that any given element is in the image of $\phi$ is $1-(1-1/n)^n$. Furtermore, if we think of throwing $n$ balls into $n$ bins as a martingale of length $n$, Azuma's inequality implies that $\Pr\bigl[X-E[X]>C\sqrt{n\log n}\,\bigr]<n^{-C'}$ . Choosing $C$ large enough, we get the desired conclusion.

Answer by Boris Bukh for Lower bound of the size of a collection of subsets with a intersecting property

2012-07-09T10:00:34Z

The two problems are equivalent. Indeed, let $\mathcal{F}$ be the family of sets of size at least $n/2+1$ such that no two sets have $n/2$ elements in common. Clearly, such an $\mathcal{F}$ cannot contain two sets $S,T$ such that $S\subset T$. If there is a set $S\in \mathcal{F}$ of size greater than $n/2+1$, then replace it by a set $S'=S\setminus\{x\}$ where $x$ is any element of $S$. The result is the family $\mathcal{F}'=\mathcal{F}\cup \{S'\}\setminus \{S\}$ which has the same size as $\mathcal{F}$, and satisfies the same condition. Repeat as long as there are sets of size greater than $n/2+1$.

Does a variety contain a cartesian product of two curves?

2011-06-04T14:13:06Z

We are given an affine variety $V\subset \mathbb{A}^n\times\mathbb{A}^n$, and wish to know if it contains a product of the form $C_1\times C_2$, where $C_1$ and $C_2$ are two curves in $\mathbb{A}^n$. First, is there an algorithm to decide this? Second, is it true that if $V$ is of degree $d$ and does contain a product of the form $C_1\times C_2$, then $V$ contains a product of the form $C_1\times C_2$ with $\deg C_1,\deg C_2\leq f(d,n)$, for some function $f$?

Answer by Boris Bukh for Does a variety contain a cartesian product of two curves?

2012-07-05T09:12:40Z

Yes, there is such an algorithm. There is an effectively computable constant $N$ such that if $V$ contains a product $S\times T$ where $S,T$ are $N$-point sets, then $V$ contains product of two curves. It is actually true even in the semialgebraic setting. The result is Theorem 1.9 from http://arxiv.org/abs/1207.0705

[ Apologies for answering my own question with a reference to my own paper. When I asked the question, I did not know the answer. ]

Answer by Boris Bukh for Ruzsa-type inequalities for additive energy

2012-04-09T09:17:03Z

1) No. Let $A=B=C$ be a set that is a union of interval $\{1,\dots,N\}$ and $N$ random elements from $\{1,\dotsc,N^2\}$ . Then $F(A,A)=KN$ for some constant $K$. On the other hand, $A+A$ is basically the interval $\{1,\dotsc,N^2\}$ . So, $F(A,A+A)\approx N^2$.

2) Example above show that it fails for $k=1$ and $l=2$ (from the context I assume that $k\cdot A$ means $k$-fold sumset $A+\dotsb+A$, not the $k$-dilate $\{ka:a\in A\}$ . If dilates were meant, then the assertion is true, and one can deduce this from the Balog–Szemerédi–Gowers theorem).

I want to add that there do exist Ruzsa-type inequalities for additive energy. Instead of sumsets, they involve a suitable extension of additive energy to more than two sets. See Razborov's paper on the product theorem in the free group (in section 6), for example.

Answer by Boris Bukh for Careless packing

2012-03-06T18:42:37Z

This is a rigorous justification of Johan Wästlund's intuition. Namely, I will show that if we tile a round ball $B$ of area $\pi\zeta(\alpha)$ by round balls of area $\pi/n^\alpha$ for some $1<\alpha<1.1716$, then we never get stuck provided we have placed enough balls already.

For later use note that the radius of $n$'th ball is $n^{-\alpha/2}$. Suppose we have placed the first $N-1$ balls. Let $U$ be the union of them, and let $U'$ be the complement of $B$. We can place $N$'th ball iff the $N^{-\alpha/2}$-neighborhood of $U\cup U'$ does not contain all of $B$. We can bound the area of the neighborhood of $U$ by $$\sum_{n < N} \pi(n^{-\alpha/2}+N^{-\alpha/2})^2=\sum_{n < N} \pi(n^{-\alpha}+2n^{-\alpha/2}N^{-\alpha/2}+N^{-\alpha})=\pi(\Sigma_1+\Sigma_2+\Sigma_3).$$ We have $\Sigma_1\approx \zeta(\alpha)-\frac{N^{1-\alpha}}{\alpha-1}$, $\Sigma_2\approx 2N^{-\alpha/2} \frac{N^{1-\alpha/2}}{1-\alpha/2}=\frac{2}{1-\alpha/2}N^{1-\alpha}$ and $\Sigma_3\approx N^{1-\alpha}$. The area of the neighborhood of $U'$ is less than $2\pi\zeta(\alpha)^{1/2}N^{-\alpha/2}=o(N^{1-\alpha})$. The result follows since $$\frac{1}{\alpha-1}-\frac{2}{1-\alpha/2}-1$$ is positive for $\alpha<4-2\sqrt{2}=1.17157\ldots$.

Edit: Actually, the argument works for any centrally symmetric convex shapes. The only thing I used about balls is that the Minkowski sum of a ball and a ball is a ball of the correct size.

Edit 2: It is clear that if one wants a stronger conclusion that one never gets stuck, then one needs to make explicit errors in the asymptotic estimates above. Then one can either decrease $\alpha$ to subsume those errors, or to consider the balls of area $\pi m^{-\alpha},\pi(m+1)^{-\alpha},\dotsc$ in a ball of total area $\pi\sum_{n\geq m} n^{-\alpha}$ to reduce the errors. This mirrors the suggestion of John Shier in the write-up linked above.

Answer by Boris Bukh for Erdős-Szekeres for first differences

2012-03-04T10:11:37Z

The $N(n)$ is exponential in $n$. First, I present a lower bound. The construction is recursive. Call a sequence whose first differences are monotone, $1$-monotone. Suppose $\mathbf{a}=a_1,\dotsc,a_M$ is a sequence that contains no $1$-monotone $N$-term subsequence. Pick an number $R$ that is larger than $\max_{i,j}(a_i-a_j)$. Then the sequence $\mathbf{b}=a_1,\dotsc,a_M,a_1+R,\dotsc,a_M+R$ contains no $1$-monotone subsequence of length $N+1$. Indeed, the subsequence cannot contain $N$ elements from the same half of $\mathbf{b}$. Hence, it must contain at least $2$ elements from each of the halves, which is impossible by the choice of $R$.

The upper bound is also recursive. We will find a monotone increasing subsequence with a stronger property that either $a_i-a_1\leq a_{i+1}-a_i$ (fast-increasing) or $a_{last}-a_i\leq a_i-a_{i-1}$ (fast-decreasing). It suffices to only work with the sequences that are monotone increasing (by losing only a square, and reversing the sequence if necessary). Let $N(I,D)$ be the length of the longest monotone sequence without a fast-increasing subsequence of length $I$, and without fast-decreasing subsequence of length $D$. I claim that $N(I,D)\leq N(I-1,D)+N(I,D-1)$ (and so $N(n,n)$ is bounded by an exponential function). Suppose $\mathbf{a}$ is a monotone increasing sequence. Let $X$ be the median of $\mathbf{a}$. The median splits $\mathbf{a}$ into two equally long sequences $\mathbf{b}$ and $\mathbf{c}$. By induction applied to $\mathbf{b}$ we can find either fast-increasing sequence of length $I-1$ or fast-decreasing sequence of length $D$. In the latter case, we are done. Else, let $\mathbf{b}'$ be the fast-increasing subsequence of $\mathbf{b}$. Similarly, there is $\mathbf{c}'$ in $\mathbf{c}$ that is fast-decreasing. If $X-a_1\leq a_{last}-X$, then the concatenation of $\mathbf{b}'$ with $a_{last}$ is the desired sequence. If $X-a_1\geq a_{last}-X$ then the concatenation of $a_1$ with $\mathbf{c}'$ is a desired subsequence.

Answer by Boris Bukh for A requst for clarification of the analysis of the Moser-Tardos algorithmic proof of the Local Lemma

2012-03-03T13:28:58Z

The reason the bound you obtain is worse than the advertised bound is that you sum over all $k$, including those $k$ for which the bound on $Q(k)$ is greater than $1$.

Suppose $T$ is an integer-valued random variable about which we know that $\Pr[T\geq k]\leq (1-\varepsilon)^k X$. Then \begin{align*} E[T]\leq (\log X/\varepsilon) \Pr[T\geq \log X/\varepsilon] + \sum_{k\geq \log X/\varepsilon} \Pr[T\geq k] =(\log X/\varepsilon)+X\sum_{k\geq \log X/\varepsilon}(1-\varepsilon)^k \end{align*} which is $O(\log X/\varepsilon)$.

Answer by Boris Bukh for Best online mathematics videos?

2012-01-28T22:06:20Z

As of today, the digitized tapes of CBMS Lectures on Probability Theory and Combinatorial by Michael Steele are online. I heartily recommend them — the style is informal, but educating: there are jokes, juggling lessons, speculations about the stock market, and all of these amidst beautiful mathematics.

Answer by Boris Bukh for An isoperimetric problem on the hypercube

2011-09-22T09:00:06Z

If $E$ consists not only of unit vectors, but also of the zero vector, then according to Alon & Spencer ``Probabilistic method'' chapter 7, the sharp isoperimetric inequality was proved by Harper. It asserts that the Hamming ball minimizes $A+E$. In that chapter they show how to get a very good asymptotic bound for the same problem.

Entropy of the Ising model

2011-07-24T13:40:11Z

Consider the standard Ising model on $[0,N]^2$ for $N$ large. By that I mean the square-lattice Ising model without external field, inside an $N$-by-$N$ square. What is its entropy for $N$ large? It must behave asymptotically as $c(\beta)N^2$ for some constant $c(\beta)$ depending on the inverse temperature $\beta$. What is $c(\beta)$? Has it been computed?

Lower bounds on the easier Waring problem

2011-05-11T16:06:15Z

The easier Waring problem asks for the least number $v=v(k)$ such that every every integer is a sum of $v$ $k$'th powers with signs, i.e. every $n\in \mathbb{N}$ is of the form $$n=x_1^k\pm x_2^k\pm\dotsb\pm x_v^k.$$

The problem is ``easier'' because unlike the usual Waring problem (without the signs) the existence of $v(k)$ is easy --- the bound $v(k)\leq 2^{k-1}+\tfrac{1}{2}k!$ follows from the repeated differencing. Of course, the upper bounds on the usual Waring problem apply, and so fact $v(k)=O(k\log k)$.

All the lower bounds on $v(k)$ I have seen come from the congruence considerations. For example, $v(3)\geq 4$ because we need at least four terms modulo $9$. However, if we discard the congruential obstacles is there a non-trivial lower bound? To put bluntly my question is

Is there $k$ large enough so that the set $\{x_1^k\pm x_2^k\pm x_3^k\pm x_4^k\pm x_5^k\}$ has zero density?

Answer by Boris Bukh for Is a sequence of the following type uniformly distributed modulo 1?

2011-03-31T17:23:02Z

$H_n$ is a asymptotic to $\log n+\gamma+O(1/n)$. This means that the values of $x_n$ for $e^k \leq n\leq e^{k+1/2}$ all fall into the same interval of length about $1/2$. The sequence is not equidistributed (the proportion of $x_n$ in that interval for $n\leq e^k$ and for $n\leq e^{k+1/2}$ differ much).

Answer by Boris Bukh for Advances and difficulties in effective version of Thue-Roth-Siegel Theorem

2011-03-18T22:07:34Z

There has been progress towards effective Roth's theorem. Notably, Fel'dman was first to prove an effective power saving over Liouville's bound.

In the nutshell the source of ineffectivity comes from the following kind of argument. One obtains a sequence of positive real numbers $x_1,x_2,\dotsc,$ with the property that the product of any two distinct $x$'s is at most $1$. It immediately follows that the sequence is bounded, but of course this information does not yield any actual bound. In the Thue's proofs, one argues that no two rational approximation can be very good simultaneously, which is where such a sequence of $x$'s arises.

In my opinion, a good introduction to effective methods in transcendental number theory is in the notes by Waldschmidt.

Answer by Boris Bukh for Shifts of multiplicative subgroup of a field

2011-02-24T08:10:27Z

In fields of prime order, factoring the difference of squares shows that the number of solutions to $x^2=y^2+c$ is what you expect it to be, from which it follows the intersection $H\cap (H+c)$ has size about what you expect. For triple intersections such as $H\cap (H+1)\cap (H+2)$, one there is an elementary argument for certain values of $p$, but not others (in this example, for $p=3,7\pmod 8$). In general you will need estimate the character sum $$\sum_x \chi(x(x+c_1)(x+c_2)\dotsb(x+c_m))$$ where $\chi$ is the Legendre symbol modulo $p$. This can be estimated by invoking Riemann hypothesis for curves.

By the way, if $H$ were a small subgroup of $ F* $ (of size $n^{1-\epsilon}$), then the sum-product estimates show that the intersection $|H\cap (H+c)|$ can never be large. See for example, this paper for a related problem of estimating the product of $H$ and $H+c$.

The following is wrong since (H+c) is not closed under multiplication:

One can get the result for the intersection by using Ruzsa's triangle inequality. Namely, $$|H(H+c)|\leq \frac{|H(H\cap (H+c))||(H+c)(H\cap (H+c))|}{|(H\cap (H+c))|}\leq \frac{|H|^2}{|(H\cap (H+c))|}$$.

Angle of a regular simplex

2011-01-31T09:36:34Z

I find the following question embarrassing, but I have not been able to either resolve it, or to find a reference.

What is the vertex angle of a regular $n$-simplex?

Background: For a vertex $v$ in a convex polyhedron $P$, the vertex angle at $v$ is the proportion of the volume that $P$ occupies in a small ball around $v$. In symbols, $$\angle v=\lim_{\varepsilon\to 0} \frac{|B(v,\varepsilon)\cap P|}{|B(v,\varepsilon)|}.$$ Up to normalization, this definition agrees with the familiar definition of the angles in the plane, or the solid angle in $3$-space.

Is there a free action on a given variety?

2010-11-02T10:16:26Z

Given a variety $V$, and a prime $p$ I want to decide if there is a free action of $\mathbb{Z}/p\mathbb{Z}$ on $V$, and to find the generator of an action if it exists. Is there a known algorithm to do it? (Assume $V$ is affine over $\mathbb{C}$, and we have a basis for the ideal of $V$.)

Answer by Boris Bukh for Does $SL_3(R)$ embed in $SL_2(R)$?

2010-11-26T11:17:50Z

Define a sequence of groups $G_i$ and associated group rings $R_i=\mathbb{Q}[G_i]$. To start put $G_0=\mathbb{Q}$. Then define $G_{i+1}=SL_3(R_i)$. The group $SL_3(R_i)$ is a subgroup of $SL_2(R_{i+1})$ because $G_{i+1}$ is a subgroup of $SL_2(R_{i+1})$ (as the group of certain diagonal matrices). Similarly, $G_i$ is a subgroup of $G_{i+1}$, and hence $R_i$ is a subring of $R_{i+1}$. Then $R=\bigcup_i R_i$ is the ring you want.

Answer by Boris Bukh for How To Present Mathematics To Non-Mathematicians?

2010-11-24T11:31:09Z

Mathematics is about the reasoning that can be made precise. The different branches of mathematics reason about different objects: numbers, shapes (rigid or stretchy), games, arrangements and relations, and other things for which the words do not exist in the everyday language. There are some branches of mathematics exploring the reasoning itself. Pretty much any set of rules of reasoning one can normally think of is equally powerful (we say equiconsistent). The large cardinals is a name of for various rules that are stronger.

To explore reasoning about different things, give a puzzle to the class. Many people like them, and do not think of these as maths. I would consider "hats" puzzles, or some topological puzzle (e.g. is this picture an unknot? are there two antipodal points on the surface of the Earth with the same temperature? etc). There are good puzzles books to get ideas from, such as those by Martin Gardner and Raymond Smullyan.

Answer by Boris Bukh for What is the shortest route to Roth's theorem?

2010-11-23T08:04:29Z

The most direct argument I know is the original argument of Szemerédi. It is background-free: no regularity lemma, no Fourier analysis. It is also very intuitive. There is a sketch by Ernie Croot at http://people.math.gatech.edu/~ecroot/szemeredi.pdf

Answer by Boris Bukh for Examples of sequences whose asymptotics can't be described by elementary functions

2010-11-08T11:26:07Z

Davenport–Schinzel sequences are related to complexity of arrangements of various geometric shapes (e.g. envelopes of line segments). Their asymptotics is described in terms of the inverse Ackermann function.

Answer by Boris Bukh for Most memorable titles

2010-10-31T16:11:56Z

An application of Poincaré's recurrence theorem to academic administration by Kenneth Meyer is a title that is hard to resist looking into.

Answer by Boris Bukh for Detecting whether directed cycle is clockwise or counterclockwise

2010-10-29T10:03:00Z

The orientation of a triangle (clockwise/counterclockwise) is the sign of the determinant $\begin{bmatrix} 1&x_1&y_1\\ 1&x_2&y_2\\ 1&x_3&y_3 \end{bmatrix}$, where $(x_1,y_1), (x_2,y_2), (x_3,y_3)$ are the Cartesian coordinates of the three vertices of the triangle.

Answer by Boris Bukh for Are any good strategies known for Erdos-Turan conjecture on additive bases of order two?

2010-10-28T19:20:43Z

It is fair to say that no one has a clue. There are two current ideas for "attack":

1) Erdős-Fuchs theorem which asserts that it is not the case that $r$ is nearly constant

2) The argument of Erdős that if $r(n)\leq 1$ for all $n$ (such a $B$ is called Sidon set), then $\liminf |B\cap \{1,\dotsc,n\}|/\sqrt{n/\log n}<100$

The proofs of both results can be found in the lovely book by Halberstam and Roth. Sandor's result is similar to Erdős-Fuchs, but puts a clever twist on it, which permits him to prove a result as strong as his. The argument of Erdős has been successfully extended to Sidon set of even order (that means that all sums of $2m$ terms are distinct). It might sound trivial since if $B$ is a Sidon set of order $2m$, then $m$-fold sumset of $B$ with itself is almost a Sidon set, but does need to do work to get around this ``almost''. It is an open problem whether there is an extension to Sidon sets of odd order.

Answer by Boris Bukh for Awfully sophisticated proof for simple facts

2010-10-17T15:41:06Z

There are infinitely many primes because $\zeta(3)=\prod_p \frac{1}{1-p^{-3}}$ is irrational.

Comment by Boris Bukh

2013-05-12T12:59:15Z

This question is off-topic for the website (it is not research-level). See FAQ for a list of better places to ask.

Comment by Boris Bukh

2013-05-10T14:16:35Z

First, this question is off-topic for this website (it is not research-level). See FAQ. Second, you can find a solution (for r=2) in the book "Probabilistic method" by Alon and Spencer, which I would recommend as the best introduction to the subject.

Comment by Boris Bukh

2013-04-30T14:51:00Z

Well, Joseph O'Rourke wrote a book on art gallery theorems. :-)

Comment by Boris Bukh

2013-04-29T14:58:15Z

How about using the estimate for $\lambda_k$ that you obtained, when estimating the second $\max$? Currently, for estimates that $\max$ you bound $\lambda_k$ by $1$. It is the bootstrapping method popularized by Münchausen :-)

Comment by Boris Bukh

2013-03-31T02:27:10Z

What is the exact statement of the problem you want to solve. How is it different than Gauss' problem?

Comment by Boris Bukh

2013-03-29T21:28:57Z

I am sorry, but I remain unconvinced. We see the loops, but how do we write from knowing the loops the relations? The edges are not labelled with the names of generators. So, we do not know that two "parallel-looking" edges correspond to the same generator.

Comment by Boris Bukh

2013-03-29T20:49:04Z

For the original question, isn't it conceivable that an infinite graph has symmetry group $G$, but for every $d$ there is a group $G_d$ and a set of generators such that the Cayley graph looks like $G$ in a neighborhood of size $d$, but these groups $G_d$ have nothing whatsoever to do with the original $G$?

Comment by Boris Bukh

2013-03-27T17:41:15Z

Look up Frankl--Wilson, and Ray--Chaudhury--Wilson theorems.

Comment by Boris Bukh

2013-03-24T19:44:29Z

This question would be more appropriate at math.stackexchange.com See FAQ.

Comment by Boris Bukh

2013-03-22T00:49:39Z

It is already known to be false. Each 2-tuple is in an essentially unique s-AP.

Comment by Boris Bukh

2013-03-19T15:07:19Z

Theorem 8.13 from the book that you linked to seems to answer the question. In your case $n=ck$ and $r=k$, which gives $t=1$ and so $|\mathcal{F}|\leq k+n$. Hence there are no "non-trivial" families.

Comment by Boris Bukh

2013-03-19T13:34:13Z

Union-free family is a different beast entirely! A family is a k-union-free if union of k set is not equal to a set in a family. You ask about containment, not equality. What are you really interested in?

Comment by Boris Bukh

2013-03-06T15:55:28Z

Math PhD is not for you if you do it for career uplifting. It will be a waste of five years of your life.

Comment by Boris Bukh

2013-02-27T16:37:42Z

No answer in the literature? Where did you search? It is a classic problem.

Comment by Boris Bukh

2013-02-27T15:37:40Z

Please provide the motivation, and explain what you tried. See mathoverflow.net/howtoask