Search

We show that there exists an absolute constant $c > 0$, such that, for any finite set $A$ of quaternions, \[ \max\{|A+A, |AA| \} \gtrsim |A|^{4/3 + c}. \] This generalizes a sum-product bound for real numbers proved by Konyagin and Shkredov., Appeared in SIAM J. Discrete Math. This version corrects some errors from the previous version, and clarifies the analysis

We show that, apart from some obvious exceptions, the number of trinomials vanishing at given complex numbers is bounded by an absolute constant. When the numbers are algebraic, we also bound effectively the degrees and the heights of these trinomials., Inaccuracies corrected following the referee's suggestions

We show that there exists an absolute constant A such that for each k ≥ 2 and every coloring of the edges of the complete k -uniform hypergraph on A r vertices with r colors, r ≥ r k , one of the color classes contains a loose path of length three.

Following a result of D.~Bylik and M.T.~Lacey from 2008 it is known that there exists an absolute constant $��>0$ such that the (unnormalized) $L^{\infty}$-norm of the three-dimensional discrepancy function, i.e, the (unnormalized) star discrepancy $D^{\ast}_N$, is bounded from below by $D_{N}^{\ast}\geq c (\log N)^{1+��}$, for all $N\in\mathbb{N}$ sufficiently large, where $c>0$ is some constant independent of $N$. This paper builds upon their methods to verify that the above result holds with $��, 15 pages, 1 figure; includes minor corrections as well as an additional brief section on the littlewood-paley inequalities

We study the problem of cops and robbers on the grid where the robber is allowed to move faster than the cops. It is well known that two cops are necessary and sufficient to catch the robber on any finite grid when the robber has unit speed. Here, we prove that if the speed of the robber exceeds a sufficiently large absolute constant, then the number of cops needed to catch the robber on an n × n grid is exp ⁡ ( Ω ( log ⁡ n / log ⁡ log ⁡ n ) ) .

The paper deals with an extremal problem concerning colorings of hypergraphs with bounded edge degrees. Consider the family of b-simple hypergraphs, in which any two edges do not share more than b common vertices. We prove that for n ≥ n 0 ( b ) , any n-uniform b-simple hypergraph with the maximum edge degree at most c n r n − b is r-colorable, where c > 0 is an absolute constant.

InźSharir and Solomon (2015), Sharir and Solomon showed that the number of incidences between m distinct points and n distinct lines in R 4 is (1) O ź m 2 ź 5 n 4 ź 5 + m 1 ź 2 n 1 ź 2 q 1 ź 4 + m 2 ź 3 n 1 ź 3 s 1 ź 3 + m + n , provided that no 2-flat contains more than s lines, and no hyperplane or quadric contains more than q lines, where the O ź hides a multiplicative factor of 2 c log m for some absolute constant c .In this paper we prove that, for integers m , n satisfying n 9 ź 8 < m < n 3 ź 2 , there exist m points and n lines on the quadratic hypersurface in R 4 { ( x 1 , x 2 , x 3 , x 4 ) ź R 4 ź x 1 = x 2 2 + x 3 2 - x 4 2 } , such that (i) at most s = O ( 1 ) lines lie on any 2-flat, (ii) at most q = O ( n ź m 1 ź 3 ) lines lie on any hyperplane, and (iii) the number of incidences between the points and the lines is ź ( m 2 ź 3 n 1 ź 2 ) , which is asymptotically larger than the upper bound inź(1), when n 9 ź 8 < m < n 3 ź 2 . This shows that the assumption that no quadric contains more than q lines (in the above mentioned theorem of Sharir and Solomon (2015)) is necessary in this regime of m and n .By a suitable projection from this quadratic hypersurface onto R 3 , we obtain m points and n lines in R 3 , with at most s = O ( 1 ) lines on a common plane, such that the number of incidences between the m points and the n lines is ź ( m 2 ź 3 n 1 ź 2 ) . It remains an interesting question to determine if this bound is also tight in general.

For y ≥ x 4/5 L 8B+151 (where L = log(xq) and B is an absolute constant), a nontrivial estimate is obtained for short cubic exponential sums over primes of the form S 3(α; x, y) = ∑ x−y

Partly on the basis of heuristic arguments from physics, it has been suggested that the performance of certain types of algorithms on random $k$-SAT formulas is linked to phase transitions that affect the geometry of the set of satisfying assignments. But, beyond intuition, there has been scant rigorous evidence that “practical” algorithms are affected by these phase transitions. In this paper we prove that Walksat, a popular randomized satisfiability algorithm, fails on random $k$-SAT formulas not very far above clause/variable density, where the set of satisfying assignments shatters into tiny, well-separated clusters. Specifically, we prove that Walksat is ineffective with high probability (w.h.p.) if $m/n>c2^k\ln^2k/k$, where $m$ is the number of clauses, $n$ is the number of variables, and $c>0$ is an absolute constant. By comparison, Walksat is known to find satisfying assignments in linear time w.h.p. if $m/n 0$ [A. Coja-Oghlan and A. Frieze, SIAM J. Comput., 43 (2...

Let \({\mathcal {L}}\) be the set of integers n which can be written as $$ n=p_1^3 + p_2^3+p_3^3+p_4^3. $$ Using the circle method and sieves, we prove that \({\sum_{N 0}\) is an absolute constant.

The paper deals with an extremal problem concerning colorings of hypergraphs with bounded edge degrees. Consider the family of b -simple hypergraphs, in which any two edges do not share more than b common vertices. We prove that for n ⩾ n 0 ( b ) , any n -uniform b -simple hypergraph with the maximum edge degree at most c ⋅ n r n − b is r -colorable, where c > 0 is an absolute constant. We also establish some applications of the main result.

We show that the number of incidences between m distinct points and n distinct lines in $${\mathbb {R}}^4$$R4 is $$O(2^{c\sqrt{\log m}} (m^{2/5}n^{4/5}+m) + m^{1/2}n^{1/2}q^{1/4} + m^{2/3}n^{1/3}s^{1/3} + n)$$O(2clogm(m2/5n4/5+m)+m1/2n1/2q1/4+m2/3n1/3s1/3+n), for a suitable absolute constant c, provided that no 2-plane contains more than s input lines, and no hyperplane or quadric contains more than q lines. The bound holds without the factor $$2^{c\sqrt{\log m}}$$2clogm when $$m \le n^{6/7}$$m≤n6/7 or $$m \ge n^{5/3}$$mźn5/3. Except for the factor $$2^{c\sqrt{\log m}}$$2clogm, the bound is tight in the worst case.

Let W p r be the Sobolev class consisting of 2π-periodic functions f such that ‖f (r)‖ p ≤ 1. We consider the relative widths d n (W p r , MW p r , L p ), which characterize the best approximation of the class W p r in the space L p by linear subspaces for which (in contrast to Kolmogorov widths) it is additionally required that the approximating functions g should lie in MW p r , i.e., ‖g (r)‖ p ≤ M. We establish estimates for the relative widths in the cases of p = 1 and p = ∞; it follows from these estimates that for almost optimal (with error at most Cn −r , where C is an absolute constant) approximations of the class W p r by linear 2n-dimensional spaces, the norms of the rth derivatives of some approximating functions are not less than cln min(n, r) for large n and r.

The well-known extremal problem on hypergraph colorings is studied. We investigate whether it is possible to color a hypergraph with a fixed number of colors equitably, i.e., so that, on the one hand, no edge is monochromatic and, on the other hand, the cardinalities of the color classes are almost the same. It is proved that if H = (V,E) is a simple hypergraph in which the least cardinality of an edge equals k, |V| = n, r|n, and $$\sum\limits_{e \in E} {{r^{1 - \left| e \right|}}} \leqslant c\sqrt k ,$$ where c > 0 is an absolute constant, then there exists an equitable r-coloring of H.

Let P be a set of points and L a set of lines in F p 2 , with | P | , | L | ? N and N < p . We show that P and L generate no more than C N 3 2 - 1 806 + o ( 1 ) incidences for some absolute constant C . This improves on the previously best-known bound of C N 3 2 - 1 10 , 678 .

It is proved that there exists an absolute constant c > 0 such that for every natural number k, every non-bipartite 2-connected graph with average degree at least ck contains k cycles with consecutive odd lengths. This implies the existence of the absolute constant d > 0 that every non-bipartite 2-connected graph with minimum degree at least dk contains cycles of all lengths modulo k, thus providing an answer (in a strong form) to a question of Thomassen. Both results are sharp up to the constant factors., 7 pages

We consider the random regular k-nae- sat problem with n variables, each appearing in exactly d clauses. For all k exceeding an absolute constant $${{\it k}_0}$$ , we establish explicitly the satisfiability threshold $${{{d_\star} \equiv {d_\star(k)}}}$$ . We prove that for $${{d < d_\star}}$$ the problem is satisfiable with high probability, while for $${{d > d_\star}}$$ the problem is unsatisfiable with high probability. If the threshold $${{d_\star}}$$ lands exactly on an integer, we show that the problem is satisfiable with probability bounded away from both zero and one. This is the first result to locate the exact satisfiability threshold in a random constraint satisfaction problem exhibiting the condensation phenomenon identified by Krzakala et al. [Proc Natl Acad Sci 104(25):10318–10323, 2007]. Our proof verifies the one-step replica symmetry breaking formalism for this model. We expect our methods to be applicable to a broad range of random constraint satisfaction problems and combinatorial problems on random graphs.

The work deals with combinatorial problems concerning colorings of non-uniform hypergraphs. Let H = ( V , E ) be a hypergraph with minimum edge-cardinality n . We show that if H is a simple hypergraph (i.e.?every two distinct edges have at most one common vertex) and ? e ? E r 1 - | e | ≤ c n , for some absolute constant c 0 , then H is r -colorable. We also obtain a stronger result for triangle-free simple hypergraphs by proving that if H is a simple triangle-free hypergraph and ? e ? E r 1 - | e | ≤ c ? n , for some absolute constant c 0 , then H is r -colorable.

The paper is devoted to the combinatorial problem concerning equitable colorings of non-uniform simple hypergraphs. Let H = ( V , E ) be a hypergraph, a coloring with r colors of its vertex set V is called equitable if it is proper (i.e. none of the edges is monochromatic) and the cardinalities of the color classes differ by at most one. We show that if H is a simple hypergraph with minimum edge-cardinality n and ∑ e ∈ E r 1 − | e | ≥ c n , for some absolute constant c > 0 , then H has an equitable r-coloring.

The paper deals with extremal problems concerning colorings of hypergraphs. By using a random recoloring algorithm we show that any n-uniform simple hypergraph H with maximum edge degree at most Δ ( H ) ≤ c ⋅ n r n − 1 , is r-colorable, where c > 0 is an absolute constant. As an application of our proof technique we establish a new lower bound for the Van der Waerden number W ( n , r ) .

Furedi conjectured that the Boolean lattice 2 n ] can be partitioned into ( n ? n / 2 ? ) chains such that the size of any two differs in at most one. In this paper, we prove that there is an absolute constant α ? 0.8482 with the following property: for every ? 0 , if n is sufficiently large, the Boolean lattice 2 n ] has a chain partition into ( n ? n / 2 ? ) chains, each of them of size between ( α - ? ) n and O ( n / ? ) .We deduce this result by looking at the more general setup of unimodal normalized matching posets. We prove that a unimodal normalized matching poset P of width w has a chain partition into w chains, each of size at most 2 | P | w + 5 , and it has a chain partition into w chains, where each chain has size at least | P | 2 w - 1 2 .

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most C|VG|. In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph Gn,p, which improves upon existing results showing that asymptotically almost surely the cop number of Gn,p is Onlogn provided that pni¾?2+elogn for some e>0. We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion-type properties. This will also be used in a separate paper on random d-regular graphs, where we show that the conjecture holds asymptotically almost surely when d=dni¾?3. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396-421, 2016

We provide a new quantitative version of Helly's theorem: there exists an absolute constant $$\alpha >1$$ź>1 with the following property. If $$\{P_i: i\in I\}$${Pi:iźI} is a finite family of convex bodies in $${\mathbb {R}}^n$$Rn with $${\mathrm{int}} (\bigcap _{i\in I}P_i )\ne \emptyset $$int(źiźIPi)źź, then there exist $$z\in {\mathbb {R}}^n$$zźRn, $$s\leqslant \alpha n$$sźźn and $$i_1,\ldots i_s\in I$$i1,źisźI such that $$\begin{aligned} z+P_{i_1}\cap \cdots \cap P_{i_s}\subseteq cn^{3/2}\Big (z+\bigcap _{i\in I}P_i\Big ), \end{aligned}$$z+Pi1źźźPis⊆cn3/2(z+źiźIPi),where $$c>0$$c>0 is an absolute constant. This directly gives a version of the "quantitative" diameter theorem of Barany, Katchalski and Pach, with a polynomial dependence on the dimension. In the symmetric case the bound $$O(n^{3/2})$$O(n3/2) can be improved to $$O(\sqrt{n})$$O(n).

Siegel’s Lemma is concerned with finding a “small” nontrivial integer solution of a large system of homogeneous linear equations with integer coefficients, where the number of variables substantially exceeds the number of equations (for example, n equations and N variables with N ≥ 2n), and “small” means small in the maximum norm. Siegel’s Lemma is a clever application of the Pigeonhole Principle, and it is a pure existence argument. The basically combinatorial Siegel’s Lemma is a key tool in transcendental number theory and diophantine approximation. David Masser (a leading expert in transcendental number theory) asked the question whether or not the Siegel’s Lemma is best possible. Here we prove that the so-called “Third Version of Siegel’s Lemma” is best possible apart from an absolute constant factor. In other words, we show that no other argument can beat the Pigeonhole Principle proof of Siegel’s Lemma (apart from an absolute constant factor). To prove this, we combine a concentration inequality (i.e., Fourier analysis) with combinatorics.

We derived an asymptotic formula for the number of pairs of integers which are mutually squares. Earlier results dealt with pairs of integers subject to the restriction that they are both odd, co-prime and squrefree. Here we remove all these restrictions and prove (similar to the best known one with restrictions) that the number of such pair of integers upto a large real X is asymptotic to \(\frac{{c{X^2}}}{{\log X}}\) with an absolute constant c which we give explicitly. Our error term is also compatible to the best known one.

We prove that the uniform probability measure μ on every ( n − k ) -dimensional projection of the n-dimensional unit cube verifies the variance conjecture with an absolute constant C Var μ | x | 2 ≤ C sup θ ∈ S n − 1 ⁡ E μ 〈 x , θ 〉 2 E μ | x | 2 , provided that 1 ≤ k ≤ n . We also prove that if 1 ≤ k ≤ n 2 3 ( log ⁡ n ) − 1 3 , the conjecture is true for the family of uniform probabilities on its projections on random ( n − k ) -dimensional subspaces.

We prove that there exists an absolute constant C so that $$\displaystyle{ \mu (K)\ \leq \ C\sqrt{p}\max _{\xi \in S^{n-1}}\mu (K \cap \xi ^{\perp })\ \vert K\vert ^{1/n} }$$ for any p > 2, any \(n \in \mathbb{N},\) any convex body K that is the unit ball of an n-dimensional subspace of L p , and any measure μ with non-negative even continuous density in \(\mathbb{R}^{n}.\) Here ξ ⊥ is the central hyperplane perpendicular to a unit vector ξ ∈ Sn−1, and | K | stands for volume.

Suppose that an infinite set $${\fancyscript{A}}$$ occupies at most $${\frac{1}{2}(p+1)}$$ residue classes modulo p, for every sufficiently large prime p. The squares, or more generally the integer values of any quadratic, are an example of such a set. By the large sieve inequality the number of elements of $${\fancyscript{A}}$$ that are at most X is $${O(X^{1/2})}$$ , and the quadratic examples show that this is sharp. The simplest form of the inverse large sieve problem asks whether they are the only examples. We prove a variety of results and formulate various conjectures in connection with this problem, including several improvements of the large sieve bound when the residue classes occupied by $${\fancyscript{A}}$$ have some additive structure. Unfortunately we cannot solve the problem itself.

The interrelation between signs and permutations in maximum inequalities is studied in this paper. The relationship is based on a lemma that reduces a rearrangement problem to a problem of choosing signs. It helps simplify proofs and find new facts and general settings. The following inequality is one of the main results of the paper: Let $x_1,\ldots , x_n$, $\sum_{k=1}^n x_k =0,$ be a collection of elements of a normed space $X$. Then for any collection of signs $\theta = (\theta_1 , \ldots , \theta_n)$ and any $t>0$, $ {\bf P} \{\pi : \max_{1\le k \le n}\Vert\sum_1^k x_{\pi (i)}\Vert > t\} \le C{\bf P}\{\pi : \max_{1\le k \le n}\Vert \sum_1^k x_{\pi (i)}\theta_i\Vert> \frac {t}{C}\}, $ where $\pi\in \Pi_n ,$ $\Pi_n$ is the group of all permutations of $\{1,\ldots ,n\}$, $P$ is the uniform distribution on it, and $C$ is an absolute constant. The inequality is unimprovable (the inverse inequality also holds with some other constant); it generalizes well-known results due to Garsia; Maurey, and Pisier; Kas...

We show that there is an absolute constant $c \leq 156$ such that in every finite family ${\cal F}$ of pseudodiscs in the plane one can find a member $D \in {\cal F}$ such that among all of the pseudodiscs in ${\cal F}$ intersecting $D$ there are at most $c$ pairwise disjoint sets.

We prove that for any symmetric n -dimensional normed space E and any e > 0 , E contains a ( 1 + e ) -Euclidean subspace of dimension at least c ln n / ln ( 1 / e ) , where c is an absolute constant. The proof is based on a concentration property of order statistics of random vectors with i.i.d. coordinates.

For various k-uniform hypergraphs F, we give tight lower bounds on the number of copies of F in a k-uniform hypergraph with a prescribed number of vertices and edges. These are the first such results for hypergraphs, and extend earlier theorems of various authors who proved that there is one copy of F. A sample result is the following: Furedi-Simonovits [11] and independently Keevash-Sudakov [16] settled an old conjecture of Sos [29] by proving that the maximum number of triples in an n vertex triple system (for n sufficiently large) that contains no copy of the Fano plane is p(n)=( 2 ?n/2? )?n/2?+( 2 ?n/2? ?n/2?). We prove that there is an absolute constant c such that if n is sufficiently large and 1 ≤ q ≤ cn 2, then every n vertex triple system with p(n)+q edges contains at least $6q\left( {\left( {_4^{\left\lfloor {n/2} \right\rfloor } } \right) + \left( {\left\lceil {n/2} \right\rceil - 3} \right)\left( {_3^{\left\lfloor {n/2} \right\rfloor } } \right)} \right)$ copies of the Fano plane. This is sharp for q≤n/2---2. Our proofs use the recently proved hypergraph removal lemma and stability results for the corresponding Turan problem.

Let P be a set of n blue points in the plane, not all on a line. Let R be a set of m red points such that P ∩ R = ∅ and every line determined by P contains a point from R. We provide an answer to an old problem by Grunbaum and Motzkin [9] and independently by Erdős and Purdy [6] who asked how large must m be in terms of n in such a case? More specifically, both [9] and [6] were looking for the best absolute constant c such that m ≥ cn. We provide an answer to this problem and show that m ≥ (n−1)/3.

The paper deals with extremal problems concerning colorings of hypergraphs. By using a random recoloring algorithm we show that any $n$-uniform simple (i.e. every two distinct edges share at most one vertex) hypergraph $H$ with maximum edge degree at most \[ ��(H)\leq c\cdot nr^{n-1}, \] is $r$-colorable, where $c>0$ is an absolute constant. %We prove also that similar result holds for $b$-simple hypergraphs. As an application of our proof technique we establish a new lower bound for Van der Waerden number $W(n,r)$, the minimum $N$ such that in any $r$-coloring of the set $\{1,...,N\}$ there exists a monochromatic arithmetic progression of length $n$. We show that \[ W(n,r)>c\cdot r^{n-1}, \] for some absolute constant $c>0$., 16 pages

Let s≥2 be an integer. Denote by f1(s) the least integer so that every integer l>f1(s) is the sum of s distinct primes. Erdős proved that f1(s)

We prove two results concerning solvability of a linear equation in sets of integers. In particular, it is shown that for every k∈ℕ, there is a noninvariant linear equation in k variables such that if A⫅{1,…,N} has no solution to the equation then \(|A|\leqq 2^{-ck/{(\log k)}^{2}}N\), for some absolute constant c>0, provided that N is large enough.

A subgraph of a hypergraph H is even if all its degrees are positive even integers, and b-bounded if it has maximum degree at most b. Let fb(n) denote the maximum number of edges in a linearn-vertex 3-uniform hypergraph which does not contain a b-bounded even subgraph. In this paper, we show that if b ≥ 12, then for some absolute constant B, thus establishing fb(n) up to polylogarithmic factors. This leaves open the interesting case b = 2, which is the case of 2-regular subgraphs. We are able to show for some constants c, C > 0 that We conjecture that f2(n) = n1 + o(1) as n → ∞.

Let G=G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant @D. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set C of size @s(n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring @f such that @f(v)@?L(v) for all v@?V(G). In particular, we show that if g is odd and @s(n)=@w(n^1^/^(^2^g^-^2^)), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n->~. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n>=g, there is a graph H=H(n,g) with bounded maximum degree and girth g, such that if @s(n)=o(n^1^/^(^2^g^-^2^)), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n->~. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size @s(n), exhibits a sharp threshold at @s(n)=2n.

Fon-Der-Flaass (1988) presented a general construction that converts an arbitrary \(\vec C_4 \)-free oriented graph Γ into a Turan (3, 4)-graph. He observed that all Turan-Brown-Kostochka examples result from his construction, and proved the lower bound \(\tfrac{4} {9} \) (1 − o(1)) on the edge density of any Turan (3, 4)-graph obtainable in this way. In this paper we establish the optimal bound \(\tfrac{3} {7} \) (1 − o(1)) on the edge density of any Turan (3, 4)-graph resulting from the Fon-Der-Flaass construction under any of the following assumptions on the undirected graph G underlying the oriented graph Γ: (i) G is complete multipartite; (ii) the edge density of G is not less than \(\tfrac{2} {3} - \varepsilon \) for some absolute constant e > 0. We are also able to improve Fon-Der-Flaass’s bound to \(\tfrac{7} {{16}} \) (1 − o(1)) without any extra assumptions on Γ.

Let @S be a polyhedral surface in R^3 with n edges. Let L be the length of the longest edge in @S, @d be the minimum value of the geodesic distance from a vertex to an edge that is not incident to the vertex, and @q be the measure of the smallest face angle in @S. We prove that @S can be triangulated into at most CLn/(@d@q) planar and rectilinear acute triangles, where C is an absolute constant.

Let ℳ denote the maximal function along the polynomial curve (γ1t,…,γdtd): $$\mathcal{M}(f)(x)=\sup_{r>0}\frac{1}{2r}\int_{|t|\leq r}|f(x_1-\gamma_1t,\ldots,x_d-\gamma_dt^d)|\,dt.$$ We show that the L2 norm of this operator grows at most logarithmically with the parameter d: $$\Vert \mathcal{M}f\Vert _{L^2(\mathbb{R}^d)}\leq c\log d\Vert f\Vert _{L^2(\mathbb{R}^d)},$$ where c>0 is an absolute constant. The proof depends on the explicit construction of a “parabolic” semigroup of operators which is a mixture of stable semigroups.

Let [math] and [math] be finite subsets of positive real numbers. Solymosi gave the sum-product estimate [math] , where [math] is the ceiling function. We use a variant of his argument to give the bound ¶ max ( | A + B | , | A ⋅ B | ) ≥ ( 4 ⌈ log | A | ⌉ ⌈ log | B | ⌉ ) − 1 ∕ 3 | A | 2 ∕ 3 | B | 2 ∕ 3 . ¶ (This isn’t quite a generalization since the logarithmic losses are worse here than in Solymosi’s bound.) ¶ Suppose that [math] is a finite subset of real numbers. We show that there exists an [math] such that [math] for some absolute constant [math] .

We prove that there exists an absolute constant c > 0 such that for any finite set A ⊆ ℤ with |A| ≥ 2 and any positive integer m 0 satisfying |(A + b) \ A| ≤ m; equivalently, there are at most m positive integers possessing |A| −m (or more) representations as a difference of two elements of A.

Let $G$ be a graph with $n$ vertices and independence number $\alpha$. Hadwiger's conjecture implies that $G$ contains a clique minor of order at least $n/\alpha$. In 1982, Duchet and Meyniel proved that this bound holds within a factor 2. Our main result gives the first improvement on their bound by an absolute constant factor. We show that $G$ contains a clique minor of order larger than $.504n/\alpha$. We also prove related results giving lower bounds on the order of the largest clique minor.

We bound the hereditary discrepancy of a hypergraph $\mathcal{H}$ in two colors in terms of its hereditary discrepancy in $c$ colors. We show that $\mathrm{herdisc}(\mathcal{H},2)\leq Kc$ $\mathrm{herdisc}(\mathcal{H},c)$, where $K$ is some absolute constant. This bound is sharp apart from the absolute constant.

Let EN=(e1,e2,…,eN) be a binary sequence with ei∈{+1,−1}. For 2≤k≤N, the correlation measure of order k of the sequence is defined by Mauduit and Sárközy as Ck(EN)=maxM,d1,…,dk|∑n=1Men+d1en+d2…en+dk| where the maximum is taken over all M≥1 and 0≤d10 such that C2k(EN)≥c2kN for all EN for all large enough N. thus answering a question of Cassaigne, Mauduit, and Sárközy (in stronger form than an earlier result of Kohayakawa, Mauduit, Moreira, and Rödl). We prove a lower bound on the even correlation measures C2k(EM[1:L]) when L>k(2k−1)M and use it to provide an alternate proof of this result. The constant c2k in our proof is better than that of Alon, Kohayakawa, Mauduit, Moreira, and Rödl for k=1, but poorer for all k≥2.We study C3(EN) via C3(EM[1:L]). This allows us to strengthen a recent result of Gyarmati which relates C3(EN) and C2(EN). We prove that given any κ>0 there is an associated c>0 (depending only on κ) such that, for all sufficiently large N, if C2(EN)≤κN2/3 we have C3(EN)≥cN. This also answers a question of Gyarmati.Finally, the study of C3(EM[1:L]) allows us to verify a conjecture of Mauduit. We prove that there is an absolute constant c>0 such that C2(EN)C3(EN)≥cN for all EN for all large enough N.

Gerards and Seymour (see [10], p. 115) conjectured that if a graph has no odd complete minor of order l, then it is (l − 1)-colourable. This is an analogue of the well-known conjecture of Hadwiger, and in fact, this would immediately imply Hadwiger's conjecture. The current best-known bound for the chromatic number of graphs with no odd complete minor of order l is $O(l \sqrt{\log l})$ by the recent result by Geelen, Gerards, Reed, Seymour and Vetta [8], and by Kawarabayashi [12] later, independently. But it seems very hard to improve this bound since this would also improve the current best-known bound for the chromatic number of graphs with no complete minor of order l.Motivated by this problem, in this note we show that there exists an absolute constant f(k) such that any graph G with no odd complete minor of order k admits a vertex partition V1, . . ., V496k such that each component in the subgraph induced on Vi (i ≥ 1) has at most f(k) vertices. When f(k) = 1, this is a colouring of G. Hence this is a relaxation of colouring in a sense, and this is the first result in this direction for the odd Hadwiger's conjecture.Our proof is based on a recent decomposition theorem due to Geelen, Gerards, Reed, Seymour and Vetta [8], together with a connectivity result that forces a huge complete bipartite minor in large graphs by Böhme, Kawarabayashi, Maharry and Mohar [3].

Rogers [A note on coverings, Matematika 4 (1957) 1–6] proved, for a given closed convex body C in n-dimensional Euclidean space Rn, the existence of a covering for Rn by translates of C with density cnlnn for an absolute constant c. A few years later, Erdős and Rogers [Covering space with convex bodies, Acta Arith. 7 (1962) 281–285] obtained the existence of such a covering having not only low-density cnlnn but also low multiplicity c′nlnn for an absolute constant c′. In this paper, we give a simple proof of Erdős and Rogers’ theorem using the Lovász Local Lemma. Furthermore, we apply the result to the chromatic number of the unit-distance graph under ℓp-norm.

For a prime p, a subset S of Z p is a sumset if S = A + A for some A ⊂ Z p . Let f ( p ) denote the maximum integer so that every subset S ⊂ Z p of size at least p − f ( p ) is a sumset. The question of determining or estimating f ( p ) was raised by Green. He showed that for all sufficiently large p, f ( p ) ⩾ 1 9 log 2 p and proved, with Gowers, that f ( p ) c p 2 / 3 log 1 / 3 p for some absolute constant c. Here we improve these estimates, showing that there are two absolute positive constants c 1 , c 2 so that for all sufficiently large p, c 1 p log p ⩽ f ( p ) c 2 p 2 / 3 log 1 / 3 p . The proofs combine probabilistic arguments with spectral techniques.