The Hardness of 3-Uniform Hypergraph Coloring

We prove that coloring a 3-uniform 2-colorable hypergraph with c colors is NP-hard for any constant c. The best known algorithm [20] colors such a graph using O(n^1/5) colors. Our result immediately implies that for any constants k ≥ 3 and c₂ > c₁ > 1, coloring a k-uniform c₁-colorable hypergraph with c₂ colors is NP-hard; the case k = 2, however, remains wide open. This is the first hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number of colors. For k ≥ 4 such a result has been shown by [14], who also discussed the inherent difference between the k = 3 case and k ≥ 4. Our proof presents a new connection between the Long-Code and the Kneser graph, and relies on the high chromatic numbers of the Kneser graph [19,22] and the Schrijver graph [26]. We prove a certain maximization variant of the Kneser conjecture, namely that any coloring of the Kneser graph by fewer colors than its chromatic number, has ‘many’ non-monochromatic edges. * Research supported by NSF grant CCR-9987845. † Supported by an Alon Fellowship and by NSF grant CCR-9987845. ‡ Work supported in part by NSF grants CCF-9988526 and DMS 9729992, and the State of New Jersery.     

Growth and recurrence of stationary random walks

 Let (X _n ,n≥1) be a real-valued ergodic stationary stochastic process, and let (Y _n =X ₁ +…+X _n ,n≥1) be the associated random walk. We prove the following: if the sequence of distributions of the random variables Y _n /n,n≥1, is uniformly tight (or, more generally, does not have the zero measure as a vague limit point), then there exists a real number c such that the random walk (Y _n −nc,n≥1) is recurrent. If this sequence of distributions converges to a probability measure ρ on ℝ (or, more generally, has a nonzero limit ρ in the vague topology), then (Y _n −nc,n≥1) is recurrent for ρ−a.e.cℝ. Received: 24 September 2001 / Revised version: 1 August 2002 / Published online: 24 October 2002 The first author was partially supported by the FWF research project P14379-MAT. Mathematics Subject Classification (2000): 37A20, 37A50, 60G10, 60G50 Key words or phrases: Recurrent stationary random walks – Recurrent cocycles     

The spectral radius of matrix continuous refinement operators

A simple analytic formula for the spectral radius of matrix continuous refinement operators is established. On the space L₂^m(\mathbb R^s)L_2^m({{\mathbb R}}^s), m ≥ 1 and s ≥ 1, their spectral radius is equal to the maximal eigenvalue in magnitude of a number matrix, obtained from the dilation matrix M and the matrix function c defining the corresponding refinement operator. A similar representation is valid for the continuous refinement operators considered on spaces L _p for p ∈ [1, ∞ ), p ≠ 2. However, additional restrictions on the kernel c are imposed in this case.     

Asymptotic stability of solitons of the gKdV equations with general nonlinearity

We consider the generalized Korteweg-de Vries equation (gKdV)

Limiting angles of Γ-martingales

Suppose that M is a complete, simply connected Riemannian manifold of non-positive sectional curvature with dimension m≥ 3 and that, outside a fixed compact set, the sectional curvatures are bounded above by −c ₁/{r ² ln r} and below by −c ₂ r ², where c ₁ and c ₂ are two positive constants and r is the geodesic distance from a fixed point. We show that, when κ≥ 1 satisfies certain conditions, the angular part of a κ-quasi-conformal Γ-martingale on M tends to a limit as time tends to infinity and the closure of the support of the distribution of this limit is the entire sphere at infinity. This improves both a result of Le for Brownian motion and also results concerning the non-existence of κ-quasi-conformal harmonic maps from certain types of Riemannian manifolds into M. Received: 19 September 1997     

Hadwiger Number and the Cartesian Product of Graphs

The Hadwiger number η(G) of a graph G is the largest integer n for which the complete graph K _n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, η(G) ≥ χ(G), where χ(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product of graphs. As the main result of this paper, we prove that for any two graphs G ₁ and G ₂ with η(G ₁) = h and η(G ₂) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following:

Hitting Simplices with Points in ℝ3

The so-called first selection lemma states the following: given any set P of n points in ℝ ^d , there exists a point in ℝ ^d contained in at least c _d n ^d+1−O(n ^d ) simplices spanned by P, where the constant c _d depends on d. We present improved bounds on the first selection lemma in ℝ³. In particular, we prove that c ₃≥0.00227, improving the previous best result of c ₃≥0.00162 by Wagner (On k-sets and applications. Ph.D. thesis, ETH Zurich, 2003). This makes progress, for the three-dimensional case, on the open problems of Bukh et al. (Stabbing simplices by points and flats. Discrete Comput. Geom., 2010) (where it is proven that c ₃≤1/4⁴≈0.00390) and Boros and Füredi (The number of triangles covering the center of an n-set. Geom. Dedic. 17(1):69–77, 1984) (where the two-dimensional case was settled).     

Tiling Transitive Tournaments and Their Blow-ups

Let TT _k denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT _k by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c ₂=1/2, c ₃=5/6 and c _k =1−2^{−k−log k} for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c _k n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c _k cannot be improved to less than 1−2^{−0.5k(1+o(1))}. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the set of discrete subgroups of bounded covolume in a semisimple group

In this noteG is a locally compact group which is the product of finitely many groups G_s(k_s)(s∈S), where k_s is a local field of characteristic zero and G_s an absolutely almost simplek _s-group, ofk _s-rank ≥1. We assume that the sum of the r_s is ≥2 and fix a Haar measure onG. Then, given a constantc > 0, it is shown that, up to conjugacy,G contains only finitely many irreducible discrete subgroupsL of covolume ≥c (4.2). This generalizes a theorem of H C Wang for real groups. His argument extends to the present case, once it is shown thatL is finitely presented (2.4) and locally rigid (3.2).     

The maximum size of a partial 3-spread in a finite vector space over <Emphasis Type="Italic">GF</Emphasis>(2)

Let n ≥ 3 be an integer, let V _n (2) denote the vector space of dimension n over GF(2), and let c be the least residue of n modulo 3. We prove that the maximum number of 3-dimensional subspaces in V _n (2) with pairwise intersection {0} is \frac2ⁿ-2^c7-c{\frac{2^n-2^c}{7}-c} for n ≥ 8 and c = 2. (The cases c = 0 and c = 1 have already been settled.) We then use our results to construct new optimal orthogonal arrays and (s, k, λ)-nets.     

Correlated equilibria of games with many players

Let G _m,n be the class of strategic games with n players, where each player has m≥2 pure strategies. We are interested in the structure of the set of correlated equilibria of games in G _m,n when n→∞. As the number of equilibrium constraints grows slower than the number of pure strategy profiles, it might be conjectured that the set of correlated equilibria becomes large. In this paper, we show that (1) the average relative measure of the set of correlated equilibria is smaller than 2⁻ⁿ; and (2) for each 1<c<m, the solution set contains c ⁿ correlated equilibria having disjoint supports with a probability going to 1 as n grows large. The proof of the second result hinges on the following inequality: Let c ₁, …, c _l be independent and symmetric random vectors in R ^k, l≥k. Then the probability that the convex hull of c ₁, …, c _l intersects R ^k ₊ is greater than or equal to . Received: December 1998/Final version: March 2000     

A distortion problem for the space ℓ ∞ c (ω 1)

The Banach space ℓ _∞ ^c (ω ₁) is the space of boundedω ₁-sequences of countable support. A pointwise-closed subspaceV≤ℓ _∞ ^c (ω ₁) will be calledunbounded if lcub;min(supp(υ)):υ ∈Vrcub; is unbounded inω ₁. It is shown that there are Lipshitz functionsf: Sph(ℓ _∞ ^c (ω ₁)) → ℝ which have large variation on the unit sphere of any unbounded subspace. This answers a question implicit in Partington [P 80].     

Bonds Intersecting Cycles In A Graph

Let G be a k-connected graph G having circumference c ≥ 2k. It is shown that for k ≥ 2, then there is a bond B which intersects every cycle of length c-k + 2 or greater.     

Beurling-Landau-type theorems for non-uniform sampling in shift invariant spline spaces

Under the appropriate definition of sampling density D_ϕ, a function f that belongs to a shift invariant space can be reconstructed in a stable way from its non-uniform samples only if D_ϕ≥1. This result is similar to Landau's result for the Paley-Wiener space B _1/2 . If the shift invariant space consists of polynomial splines, then we show that D_ϕ<1 is sufficient for the stable reconstruction of a function f from its samples, a result similar to Beurling's special case B _1/2 .     

An optimal bound on the tail distribution of the number of recurrences of an event in product spaces

 Let X ₁ ,X ₂ ,... be independent random variables and a a positive real number. For the sake of illustration, suppose A is the event that |X _i+1 +...+X _j |≥a for some integers 0≤i<j<∞. For each k≥2 we upper-bound the probability that A occurs k or more times, i.e. that A occurs on k or more disjoint intervals, in terms of P(A), the probability that A occurs at least once. More generally, let X=(X ₁ ,X ₂ ,...)Ω=Π _{j ≥1}Ω _j be a random element in a product probability space (Ω,ℬ,P=⊗ _{j ≥1} P _j ). We are interested in events AB that are (at most contable) unions of finite-dimensional cylinders. We term such sets sequentially searchable. Let L(A) denote the (random) number of disjoint intervals (i,j] such that the value of X _(i,j] =(X _i+1 ,...,X _j ) ensures that XA. By definition, for sequentially searchable A, P(A)≡P(L(A)≥1)=P(𝒩_{−ln (P(Ac))} ≥1), where 𝒩_γ denotes a Poisson random variable with some parameter γ>0. Without further assumptions we prove that, if 0<P(A)<1, then P(L(A)≥k)<P(𝒩_{−ln (P(Ac))} ≥k) for all integers k≥2. An application to sums of independent Banach space random elements in l ^∞ is given showing how to extend our theorem to situations having dependent components. Received: 8 June 2001 / Revised version: 30 October 2002 Published online: 15 April 2003 RID="*" ID="*" Supported by NSF Grant DMS-99-72417. RID="†" ID="†" Supported by the Swedish Research Council. Mathematics Subject Classification (2000): Primary 60E15, 60G50 Key words or phrases: Tail probability inequalities – Hoffmann-Jo rgensen inequality – Poisson bounds – Number of event recurrences – Number of entrance times – Product spaces     

Ideal einstein,conformally flat and semi-symmetric immersions

Recently, B. Y. Chen introduced a new intrinsic invariant of a manifold, and proved that everyn-dimensional submanifold of real space formsR ^m (ε) of constant sectional curvature ε satisfies a basic inequality δ(n ₁,…,n _k )≤c(n ₁,…,n _k )H ²+b(n ₁,…,n _k )ε, whereH is the mean curvature of the immersion, andc(n ₁,…,n _k ) andb(n ₁,…,n _k ) are constants depending only onn ₁,…,n _k ,n andk. The immersion is calledideal if it satisfies the equality case of the above inequality identically for somek-tuple (n ₁,…,n _k ). In this paper, we first prove that every ideal Einstein immersion satisfyingn≥n ₁+…+n _k +1 is totally geodesic, and that every ideal conformally flat immersion satisfyingn≥n ₁+…+n _k +2 andk≥2 is also totally geodesic. Secondly we completely classify all ideal semi-symmetric hypersurfaces in real space forms. The author was supported by the NSFC and RFDP.     

Koszul homology and syzygies of Veronese subalgebras

A graded K-algebra R has property N _p if it is generated in degree 1, has relations in degree 2 and the syzygies of order ≤ p on the relations are linear. The Green–Lazarsfeld index of R is the largest p such that it satisfies the property N _p . Our main results assert that (under a mild assumption on the base field) the cth Veronese subring of a polynomial ring has Green–Lazarsfeld index ≥ c + 1. The same conclusion also holds for an arbitrary standard graded algebra, provided c >> 0{c\gg 0}.     

Packing,covering and decomposing of a complete uniform hypergraph into delta-systems

Anh-uniform hypergraph generated by a set of edges {E ₁,...,E _c} is said to be a delta-system Δ(p,h,c) if there is ap-element setF such that ∇F|=p andE _i⌢E _j=F,∀i≠j. The main result of this paper says that givenp, h andc, there isn ₀ such that forn≥n ₀ the set of edges of a completeh-uniform hypergraphK _n ^h can be partitioned into subsets generating isomorphic delta-systems Δ(p, h, c) if and only if . This result is derived from a more general theorem in which the maximum number of delta-systems Δ(p, h, c) that can be packed intoK _n ^h and the minimum number of delta-systems Δ(p, h, c) that can cover the edges ofK _n ^h are determined for largen. Moreover, we prove a theorem on partitioning of the edge set ofK _n ^h into subsets generating small but not necessarily isomorphic delta-systems.     

Positive values of non-homogeneous indefinite quadratic forms of type (1, 4)

Let Г_r,n—r denote the infimum of all number Г > 0 such that for any real indefinite quadratic form inn variables of type (r, n—r), determinantD ≠ 0 and real numbers c₁; c₂,…, c_n, there exist integersx ₁,x₂,…,x_n satisfying 0 < Q(x₁+c₁,x₂ + c₂,…,x_n + c_n) ≤(Г|Z > |)^1/n. All the values of Г_r,n—r are known except for г_1,4. Earlier it was shown that 8 ≤Г_1,4 ≤16. Here we improve the upper bound to get Г_1,4 < 12.     

Unit Distances and Diameters in Euclidean Spaces

We show that the maximum number of unit distances or of diameters in a set of n points in d-dimensional Euclidean space is attained only by specific types of Lenz constructions, for all d≥4 and n sufficiently large depending on d. As a corollary, we determine the exact maximum number of unit distances for all even d≥6 and the exact maximum number of diameters for all d≥4 and all n sufficiently large depending on d. This material is based upon work supported by the South African National Research Foundation.