Nearly bipartite graphs with large chromatic number

P. Erdős and A. Hajnal asked the following question. Does there exist a constant ε>0 with the following property: If every subgraphH of a graphG can be made bipartite by the omission of at most ε|H| edges where |H| denotes the number of vertices ofH thenx(H) ≦ 3. The aim of this note is to give a negative answer to this question and consider the analogous problem for hypergraphs. The first was done also by L. Lovász who used a different construction.     

Almost Euclidean subspaces of ℓ 1 N VIA expander codes

We give an explicit (in particular, deterministic polynomial time) construction of subspaces X⊆ℝ ^N of dimension (1−o(1))N such that for every x∈X,

Uniformly cross intersecting families

Let A and B denote two families of subsets of an n-element set. The pair (A,B) is said to be ℓ-cross-intersecting iff |A∩B|=ℓ for all A∈ A and B∈B. Denote by P _e (n) the maximum value of |A||B| over all such pairs. The best known upper bound on P _e (n) is Θ(2 ⁿ ), by Frankl and R?dl. For a lower bound, Ahlswede, Cai and Zhang showed, for all n ≥ 2ℓ, a simple construction of an ℓ-cross-intersecting pair (A,B) with |A||B| = $ \left( {{*{20}c} {2\ell } \\ \ell \\ } \right) $ \left( {\begin{array}{*{20}c} {2\ell } \\ \ell \\ \end{array} } \right) 2 ^n−2ℓ = Θ(2 ⁿ /$ \sqrt \ell $ \sqrt \ell ), and conjectured that this is best possible. Consequently, Sgall asked whether or not P _e (n) decreases with ℓ.     

Another Look at the Erdős–Hajnal–Pósa Results on Partitioning Edges of the Rado Graph

Dedicated to the memory of Paul Erdős Erdős, Hajnal and Pósa exhibited in [1] a partition (U,D) of the edges of the Rado graph which is a counterexample to . They also obtained that if every vertex of a graph has either in or in the complement of finite degree then . We will characterize all graphs so that . Received October 29, 1999 RID="†" ID="†" Supported by NSERC of Canada Grant #691325.     

Convergence rates of the LIL for random fields in Hilbert spaces

Considering the positive d-dimensional lattice point Z ₊ ^d (d ≥ 2) with partial ordering ≤, let {X _k: k ∈ Z ₊ ^d } be i.i.d. random variables taking values in a real separable Hilbert space (H, ‖ · ‖) with mean zero and covariance operator Σ, and set $ S_n = \sum\limits_{k \leqslant n} {X_k } $ S_n = \sum\limits_{k \leqslant n} {X_k } , n ∈ Z ₊ ^d . Let σ _i ², i ≥ 1, be the eigenvalues of Σ arranged in the non-increasing order and taking into account the multiplicities. Let l be the dimension of the corresponding eigenspace, and denote the largest eigenvalue of Σ by σ ². Let logx = ln(x ∨ e), x ≥ 0. This paper studies the convergence rates for $ \sum\limits_n {\frac{{\left( {\log \log \left| n \right|} \right)^b }} {{\left| n \right|\log \left| n \right|}}} P\left( {\left\| {S_n } \right\| \geqslant \sigma \varepsilon \sqrt {2\left| n \right|\log \log \left| n \right|} } \right) $ \sum\limits_n {\frac{{\left( {\log \log \left| n \right|} \right)^b }} {{\left| n \right|\log \left| n \right|}}} P\left( {\left\| {S_n } \right\| \geqslant \sigma \varepsilon \sqrt {2\left| n \right|\log \log \left| n \right|} } \right) . We show that when l ≥ 2 and b > −l/2, E[‖X‖²(log ‖X‖) ^d−2(log log ‖X‖) ^b+4] < ∞ implies $ \begin{gathered} \mathop {\lim }\limits_{\varepsilon \searrow \sqrt {d - 1} } (\varepsilon ^2 - d + 1)^{b + l/2} \sum\limits_n {\frac{{\left( {\log \log \left| n \right|} \right)^b }} {{\left| n \right|\log \left| n \right|}}P\left( {\left\| {S_n } \right\| \geqslant \sigma \varepsilon \sqrt 2 \left| n \right|\log \log \left| n \right|} \right)} \hfill \\ = \frac{{K(\Sigma )(d - 1)^{\frac{{l - 2}} {2}} \Gamma (b + l/2)}} {{\Gamma (l/2)(d - 1)!}} \hfill \\ \end{gathered} $ \begin{gathered} \mathop {\lim }\limits_{\varepsilon \searrow \sqrt {d - 1} } (\varepsilon ^2 - d + 1)^{b + l/2} \sum\limits_n {\frac{{\left( {\log \log \left| n \right|} \right)^b }} {{\left| n \right|\log \left| n \right|}}P\left( {\left\| {S_n } \right\| \geqslant \sigma \varepsilon \sqrt 2 \left| n \right|\log \log \left| n \right|} \right)} \hfill \\ = \frac{{K(\Sigma )(d - 1)^{\frac{{l - 2}} {2}} \Gamma (b + l/2)}} {{\Gamma (l/2)(d - 1)!}} \hfill \\ \end{gathered} , where Γ(·) is the Gamma function and $ \prod\limits_{i = l + 1}^\infty {((\sigma ^2 - \sigma _i^2 )/\sigma ^2 )^{ - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}} } $ \prod\limits_{i = l + 1}^\infty {((\sigma ^2 - \sigma _i^2 )/\sigma ^2 )^{ - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}} } .     

Probabilistic constructions of B 2[g] sequences

We use the probabilistic method to prove that for any positive integer g there exists an infinite B2[g] sequence A = {ak} such that ak ≤ k^2＋1/g（log k）^1/g＋0（1） as k→∞. The exponent 2＋1/g improves the previous one, 2 ＋ 2/g, obtained by Erdos and Renyi in 1960. We obtain a similar result for B2 [g] sequences of squares.     

Mangoes and Blueberries

Dedicated to the memory of Paul Erdős We prove the following conjecture of Erdős and Hajnal: For every integer k there is an f(k) such that if for a graph G, every subgraph H of G has a stable set containing vertices, then G contains a set X of at most f(k) vertices such that G−X is bipartite. This conjecture was related to me by Paul Erdős at a conference held in Annecy during July of 1996. I regret not being able to share the answer with him. Received: August 20, 1997     

On weighted spaces of holomorphic functions of several variables

We generalize the results of [11] and [12] for the unit ball $ \mathbb{B}_d $ \mathbb{B}_d of ℂ ^d . In particular, we show that under the weight condition (B) the weighted H ^∞-space on $ \mathbb{B}_d $ \mathbb{B}_d is isomorphic to ℓ^∞ and thus complemented in the corresponding weighted L ^∞-space. We construct concrete, generalized Bergman projections accordingly. We also consider the case where the domain is the entire space ℂ ^d . In addition, we show that for the polydisc $ \mathbb{D}^d $ \mathbb{D}^d ^d , the weighted H ^∞-space is never isomorphic to ℓ^∞.     

Limitations to Fréchet’s metric embedding method

Fréchet’s classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Fréchet embedding is Bourgain's embedding [4]. The authors have recently shown [2] that for every ε>0, anyn-point metric space contains a subset of size at leastn ^1−ε which embeds into ℓ₂ with distortion . The embedding used in [2] is non-Fréchet, and the purpose of this note is to show that this is not coincidental. Specifically, for every ε>0, we construct arbitrarily largen-point metric spaces, such that the distortion of any Fréchet embedding into ℓ_p on subsets of size at leastn ^1/2+ε is Ω((logn)^1/p ). Supported in part by a grant from the Israeli National Science Foundation. Supported in part by a grant from the Israeli National Science Foundation. Supported in part by the Landau Center.     

Discrete Kakeya-type problems and small bases

A subset U of a group G is called k-universal if U contains a translate of every k-element subset of G. We give several nearly optimal constructions of small k-universal sets, and use them to resolve an old question of Erdős and Newman on bases for sets of integers, and to obtain several extensions for other groups.     

A Ramsey-Sperner theorem

Letn≥k≥1 be integers and letf(n, k) be the smallest integer for which the following holds: If ℱ is a family of subsets of ann-setX with |ℱ|<f(n,k) then for everyk-coloring ofX there existA B ∈ ℱ,A∈B, A⊂B such thatB-A is monochromatic. Here it is proven that for a fixedk there exist constantsc _k andd _k such that and ask→∞. The proofs of both the lower and the upper bounds use probabilistic methods.     

Congruence formulae modulo powers of 2 for class numbers of cyclic quartic fields

Let K = $ k(\sqrt \theta ) $ k(\sqrt \theta ) be a real cyclic quartic field, k be its quadratic subfield and $ \tilde K = k(\sqrt { - \theta } ) $ \tilde K = k(\sqrt { - \theta } ) be the corresponding imaginary quartic field. Denote the class numbers of K, k and $ \tilde K $ \tilde K by h _K , h _k and {417-3} respectively. Here congruences modulo powers of 2 for h ⁻ = h _K /h _K and $ \tilde h^ - = h_{\tilde K} /h_k $ \tilde h^ - = h_{\tilde K} /h_k are obtained via studying the p-adic L-functions of the fields.     

Joint asymptotic distribution of exceedances point process and partial sum of stationary Gaussian sequence

Let {X _i } _i=1^∞ be a standardized stationary Gaussian sequence with covariance function r(n) = EX ₁ X _n+1, S _n = Σ _i=1 ⁿ X _i , and $\bar X_n = \tfrac{{S_n }} {n} $\bar X_n = \tfrac{{S_n }} {n} . And let N _n be the point process formed by the exceedances of random level $(\tfrac{x} {{\sqrt {2\log n} }} + \sqrt {2\log n} - \tfrac{{\log (4\pi \log n)}} {{2\sqrt {2\log n} }})\sqrt {1 - r(n)} + \bar X_n $(\tfrac{x} {{\sqrt {2\log n} }} + \sqrt {2\log n} - \tfrac{{\log (4\pi \log n)}} {{2\sqrt {2\log n} }})\sqrt {1 - r(n)} + \bar X_n by X ₁,X ₂,…, X _n . Under some mild conditions, N _n and S _n are asymptotically independent, and N _n converges weakly to a Poisson process on (0,1].     

A generalization of Mathieu subspaces to modules of associative algebras

We first propose a generalization of the notion of Mathieu subspaces of associative algebras $ \mathcal{A} $ \mathcal{A} , which was introduced recently in [Zhao W., Generalizations of the image conjecture and the Mathieu conjecture, J. Pure Appl. Algebra, 2010, 214(7), 1200–1216] and [Zhao W., Mathieu subspaces of associative algebras], to $ \mathcal{A} $ \mathcal{A} -modules $ \mathcal{M} $ \mathcal{M} . The newly introduced notion in a certain sense also generalizes the notion of submodules. Related with this new notion, we also introduce the sets σ(N) and τ(N) of stable elements and quasi-stable elements, respectively, for all R-subspaces N of $ \mathcal{A} $ \mathcal{A} -modules $ \mathcal{M} $ \mathcal{M} , where R is the base ring of $ \mathcal{A} $ \mathcal{A} . We then prove some general properties of the sets σ(N) and τ(N). Furthermore, examples from certain modules of the quasi-stable algebras [Zhao W., Mathieu subspaces of associative algebras], matrix algebras over fields and polynomial algebras are also studied.     

On rigidity of Clifford torus in a unit sphere

We extend the scalar curvature pinching theorems due to Peng-Terng, Wei-Xu and Suh-Yang. Let M be an n-dimensional compact minimal hypersurface in S n+1 satisfying Sf 4 f_3~2 ≤ 1/n S~3 , where S is the squared norm of the second fundamental form of M, and f_k =sum λ_i~k from i and λ_i (1 ≤ i ≤ n) are the principal curvatures of M. We prove that there exists a positive constant δ(n)(≥ n/2) depending only on n such that if n ≤ S ≤ n + δ(n), then S ≡ n, i.e., M is one of the Clifford torus S~k ((k/n)~1/2 ) ×S~...     

Parallel packing and covering of an equilateral triangle with sequences of squares

An equilateral triangle T _e of sides 1 can be parallel covered with any sequence of squares whose total area is not smaller than 1:5. Moreover, any sequence of squares whose total area does not exceed $ \frac{3} {4}(2 - \sqrt 3 ) $ \frac{3} {4}(2 - \sqrt 3 ) (2 − √3) can be parallel packed into T _e .     

Σ-definability of uncountable models of <Emphasis Type="Italic">c</Emphasis>-simple theories

We show that each c-simple theory with an additional discreteness condition has an uncountable model Σ-definable in ℍ$ \mathbb{H} $ \mathbb{H} ($ \mathbb{L} $ \mathbb{L} ), where $ \mathbb{L} $ \mathbb{L} is a dense linear order. From this we establish the same for all c-simple theories of finite signature that are submodel complete.     

On completely multiplicative functions whose values are roots of unity

Summary We prove that if a complex valued completely multiplicative function F and a positive integer ℓ≦5 satisfy the condition F(N) = U_ℓ, where U_ℓ is the set of all ℓ-th roots of unity, then {F(n+1) F(n) ∣ nε N} = U_ℓ.     

Ramsey-type Theorems with Forbidden Subgraphs

Dedicated to the memory of Paul Erdős   A graph is called H-free if it contains no induced copy of H. We discuss the following question raised by Erdős and Hajnal. Is it true that for every graph H, there exists an such that any H-free graph with n vertices contains either a complete or an empty subgraph of size at least ? We answer this question in the affirmative for a special class of graphs, and give an equivalent reformulation for tournaments. In order to prove the equivalence, we establish several Ramsey type results for tournaments. Received August 22, 1999 RID="*" ID="*" Supported by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. RID="†" ID="†" Supported by NSF grant CR-9732101, PSC-CUNY Research Award 663472, and OTKA-T-020914. RID="‡" ID="‡" Supported by TKI grant Stochastics@TUB, and OTKA-T-026203.