Three‐query PCPs with perfect completeness over non‐Boolean domains

We study non‐Boolean PCPs that have perfect completeness and query three positions in the proof. For the case when the proof consists of values from a domain of size d for some integer constant d ≥ 2, we construct a nonadaptive PCP with perfect completeness and soundness d^?1 + d^?2 + ?, for any constant ? > 0, and an adaptive PCP with perfect completeness and soundness d^?1 + ?, for any constant ? > 0. The latter PCP can be converted into a nonadaptive PCP with perfect completeness and soundness d^?1 + ?, for any constant ? > 0, where four positions are read from the proof. These results match the best known constructions for the case d = 2 and our proofs also show that the particular predicates we use in our PCPs are nonapproximable beyond the random assignment threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Cutting dense point sets in half

A halving hyperplane of a set S of n points in R ^d contains d affinely independent points of S so that equally many of the points off the hyperplane lie in each of the two half-spaces. We prove bounds on the number of halving hyperplanes under the condition that the ratio of largest over smallest distance between any two points is at most , δ some constant. Such a set S is called dense. In d = 2 dimensions the number of halving lines for a dense set can be as much as , and it cannot exceed . The upper bound improves over the current best bound of which holds more generally without any density assumption. In d = 3 dimensions we show that is an upper bound on the number of halving planes for a dense set. The proof is based on a metric argument that can be extended to d≥ 4 dimensions, where it leads to as an upper bound for the number of halving hyperplanes. Received March 22, 1995, and in revised form January 15, 1996.     

Equilibrated error estimators for discontinuous Galerkin methods

We consider some diffusion problems in domains of ?^d, d = 2 or 3 approximated by a discontinuous Galerkin method with polynomials of any degree. We propose a new a posteriori error estimator based on H(div)‐conforming elements. It is shown that this estimator gives rise to an upper bound where the constant is one up to higher order terms. The lower bound is also established with a constant depending on the aspect ratio of the mesh, the dependence with respect to the coefficients being also traced. The reliability and efficiency of the proposed estimator is confirmed by some numerical tests. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

The acyclic edge chromatic number of a random d‐regular graph is d + 1

We prove the theorem from the title: the acyclic edge chromatic number of a random d‐regular graph is asymptotically almost surely equal to d + 1. This improves a result of Alon, Sudakov, and Zaks and presents further support for a conjecture that Δ(G) + 2 is the bound for the acyclic edge chromatic number of any graph G. It also represents an analog of a result of Robinson and the second author on edge chromatic number. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 69–74, 2005     

VC Dimensions of Principal Component Analysis

Motivated by statistical learning theoretic treatment of principal component analysis, we are concerned with the set of points in ℝ ^d that are within a certain distance from a k-dimensional affine subspace. We prove that the VC dimension of the class of such sets is within a constant factor of (k+1)(d−k+1), and then discuss the distribution of eigenvalues of a data covariance matrix by using our bounds of the VC dimensions and Vapnik’s statistical learning theory. In the course of the upper bound proof, we provide a simple proof of Warren’s bound of the number of sign sequences of real polynomials.     

Strengthened semidefinite programming bounds for codes

We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with O(n ⁷) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n ³), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle

We prove lower bounds of the form exp(n^{ε d}), ε_d > 0, on the length of proofs of an explicit sequence of tautologies, based on the Pigeonhole Principle, in proof systems using formulas of depth d, for any constant d. This is the largest lower bound for the strongest proof system, for which any superpolynomial lower bounds are known.     

New Maximal Numbers of Equilibria in Bimatrix Games

This paper presents a new lower bound of on the maximal number of Nash equilibria in d×d bimatrix games, a central concept in game theory. The proof uses an equivalent formulation of the problem in terms of pairs of polytopes with 2d facets in d -space. It refutes a recent conjecture that 2 ^d -1 is an upper bound, which was proved for d≤4. The first counterexample is a 6×6 game with 75 equilibria. The case d=5 remains open. The result carries the lower bound closer to the previously known upper bound of . Received July 23, 1997, and in revised form June 26, 1998.     

On the Helly Number for Hyperplane Transversals to Unit Balls

We prove two results about the Hadwiger problem of finding the Helly number for line transversals of disjoint unit disks in the plane, and about its higher-dimensional generalization to hyperplane transversals of unit balls in d -dimensional Euclidean space. These consist of (a) a proof of the fact that the Helly number remains 5 even for arbitrarily large sets of disjoint unit disks—thus correcting a 40-year-old error; and (b) a lower bound of d+3 on the Helly number for hyperplane transversals to suitably separated families of unit balls in R ^d . Received January 25, 1999, and in revised form July 7, 1999.     

Arrangements of oriented hyperplanes

An arrangement ofn oriented hyperplanes or half-spaces dividesE ^d into a certain number of convex cells. We study the numberc _k of cells which are covered by exactlyk half-spaces and derive an upper bound onc _k for givenn andd.     

Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs

Let ∑ = (V,E) be a finite, d‐regular bipartite graph. For any λ > 0 let π_λ be the probability measure on the independent sets of ∑ in which the set I is chosen with probability proportional to λ^|I| (π_λ is the hard‐core measure with activity λ on ∑). We study the Glauber dynamics, or single‐site update Markov chain, whose stationary distribution is π_λ. We show that when λ is large enough (as a function of d and the expansion of subsets of single‐parity of V) then the convergence to stationarity is exponentially slow in |V(∑)|. In particular, if ∑ is the d‐dimensional hypercube {0,1}^d we show that for values of λ tending to 0 as d grows, the convergence to stationarity is exponentially slow in the volume of the cube. The proof combines a conductance argument with combinatorial enumeration methods. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Some remarks on lengths of propositional proofs

We survey the best known lower bounds on symbols and lines in Frege and extended Frege proofs. We prove that in minimum length sequent calculus proofs, no formula is generated twice or used twice on any single branch of the proof. We prove that the number of distinct subformulas in a minimum length Frege proof is linearly bounded by the number of lines. Depthd Frege proofs ofm lines can be transformed into depthd proofs ofO(m ^d+1) symbols. We show that renaming Frege proof systems are p-equivalent to extended Frege systems. Some open problems in propositional proof length and in logical flow graphs are discussed. Supported in part by NSF grant DMS-9205181     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi.     

A Crank‐Nicolson Petrov‐Galerkin method with quadrature for semi‐linear parabolic problems

We propose and analyze an application of a fully discrete C² spline quadrature Petrov‐Galerkin method for spatial discretization of semi‐linear parabolic initial‐boundary value problems on rectangular domains. We prove second order in time and optimal order H¹ norm convergence in space for the extrapolated Crank‐Nicolson quadrature Petrov‐Galerkin scheme. We demonstrate numerically both L² and H¹ norm optimal order convergence of the scheme even if the nonlinear source term is not smooth. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005.     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi. Received 17 November 1997; in revised form 30 July 1998     

Vertex Degrees of Steiner Minimal Trees in ℓ p d and Other Smooth Minkowski Spaces

We find upper bounds for the degrees of vertices and Steiner points in Steiner Minimal Trees (SMTs) in the d -dimensional Banach spaces _p ^d independent of d . This is in contrast to Minimal Spanning Trees, where the maximum degree of vertices grows exponentially in d [19]. Our upper bounds follow from characterizations of singularities of SMTs due to Lawlor and Morgan [14], which we extend, and certain _p -inequalities. We derive a general upper bound of d+1 for the degree of vertices of an SMT in an arbitrary smooth d -dimensional Banach space (i.e. Minkowski space); the same upper bound for Steiner points having been found by Lawlor and Morgan. We obtain a second upper bound for the degrees of vertices in terms of 1 -summing norms. Received April 22, 1997, and in revised form October 1, 1997.     

Distribution of subgraphs of random regular graphs

We obtain the asymptotic distribution of the number of copies of a fixed subgraph H in a random d‐regular graph, provided H is strictly balanced and d = d(n) is chosen so that the expected number of copies of H tends to infinity (but not too quickly), and the expected number of copies sharing edges with two other copies is bounded. The proof of asymptotic normality of the distribution uses a method of factorial moments for variables with unbounded means that was recently derived by the authors. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Cutoff for General Spin Systems with Arbitrary Boundary Conditions

The cutoff phenomenon describes a sharp transition in the convergence of a Markov chain to equilibrium. In recent work, the authors established cutoff and its location for the stochastic Ising model on the d‐dimensional torus (?/n?)^d for any d ≥ ;1. The proof used the symmetric structure of the torus and monotonicity in an essential way. Here we enhance the framework and extend it to general geometries, boundary conditions, and external fields to derive a cutoff criterion that involves the growth rate of balls and the log‐Sobolev constant of the Glauber dynamics. In particular, we show there is cutoff for the stochastic Ising model on any sequence of bounded‐degree graphs with subexponential growth under arbitrary external fields provided the inverse log‐Sobolev constant is bounded. For lattices with homogenous boundary, such as all‐plus, we identify the cutoff location explicitly in terms of spectral gaps of infinite‐volume dynamics on half‐plane intersections. Analogous results establishing cutoff are obtained for nonmonotone spin systems at high temperatures, including the gas hard‐core model, the Potts model, the antiferromagnetic Potts model, and the coloring model. © 2014 Wiley Periodicals, Inc.     

Triangulated Spheres and Colored Cliques

   Abstract. In [1] a generalization of Hall's theorem was proved for families of hypergraphs. The proof used Sperner's lemma. In [5] Meshulam proved an extension of this result, using homology and the nerve theorem. In this paper we show how the triangulations method can be used to derive Meshulam's results. As in [1], the proof is based on results on extensions of triangulations from the sphere to the full ball. A typical result of this type is that any triangulation of the (d-1) -dimensional sphere S ^d-1 can be extended to a triangulation of the ball B ^d , by adding one point at a time, having degree at most 2d to its predecessors.     

Triangulated Spheres and Colored Cliques

Abstract. In [1] a generalization of Hall's theorem was proved for families of hypergraphs. The proof used Sperner's lemma. In [5] Meshulam proved an extension of this result, using homology and the nerve theorem. In this paper we show how the triangulations method can be used to derive Meshulam's results. As in [1], the proof is based on results on extensions of triangulations from the sphere to the full ball. A typical result of this type is that any triangulation of the (d-1) -dimensional sphere S ^d-1 can be extended to a triangulation of the ball B ^d , by adding one point at a time, having degree at most 2d to its predecessors.