From discrete flow of Beckner to continuous flow of Janson in complex hypercontractivity

We show how Beckner's montonicity result on Hamming cube easily implies the monotonicity of a flow introduced by Janson in Hausdorff–Young inequality     

L_1-norm packings from function fields

In this paper,we study some packings in a cube,namely,how to pack n points in a cube so as to maximize the minimal distance.The distance is induced by the L_1-norm which is analogous to the Hamming distance in coding theory.Two constructions with reasonable parameters are obtained,by using some results from a function field including divisor class group,narrow ray class group,and so on.We also present some asymptotic results of the two packings.     

The distance approach to approximate combinatorial counting

We develop general methods to obtain fast (polynomial time) estimates of the cardinality of a combinatorially defined set via solving some randomly generated optimization problems on the set. Examples include enumeration of perfect matchings in a graph, linearly independent subsets of a set of vectors and colored spanning subgraphs of a graph. Geometrically, we estimate the cardinality of a subset of the Boolean cube via the average distance from a point in the cube to the subset with respect to some distance function. We derive asymptotically sharp cardinality bounds in the case of the Hamming distance and show that for small subsets a suitably defined “randomized” Hamming distance allows one to get tighter estimates of the cardinality. Submitted: June 2000, Revised version: January 2001.     

Linear Programming Bounds for Codes via a Covering Argument

We recover the first linear programming bound of McEliece, Rodemich, Rumsey, and Welch for binary error-correcting codes and designs via a covering argument. It is possible to show, interpreting the following notions appropriately, that if a code has a large distance, then its dual has a small covering radius and, therefore, is large. This implies the original code to be small. We also point out that this bound is a natural isoperimetric constant of the Hamming cube, related to its Faber–Krahn minima. While our approach belongs to the general framework of Delsarte’s linear programming method, its main technical ingredient is Fourier duality for the Hamming cube. In particular, we do not deal directly with Delsarte’s linear program or orthogonal polynomial theory. This research was partially supported by ISF grant 039-7682.     

<Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>-norm packings from function fields

In this paper, we study some packings in a cube, namely, how to pack n points in a cube so as to maximize the minimal distance. The distance is induced by the L₁-norm which is analogous to the Hamming distance in coding theory. Two constructions with reasonable parameters are obtained, by using some results from a function field including divisor class group, narrow ray class group, and so on. We also present some asymptotic results of the two packings.     

Self-improvement of Poincaré Type Inequalities Associated with Approximations of the Identity and Semigroups

The purpose of this paper is to present a general method that allows us to study self-improving properties of generalized Poincaré inequalities. When measuring the oscillation in a given cube, we replace the average by an approximation of the identity or a semigroup scaled to that cube and whose kernel decays fast enough. We apply the method to obtain self-improvement in the scale of Lebesgue spaces of Poincaré type inequalities. In particular, we propose some expanded Poincaré estimates that take into account the lack of localization of the approximation of the identity or the semigroup. As a consequence of this method we are able to obtain global pseudo-Poincaré inequalities.     

Perfect binary codes of infinite length

A subset C of infinite-dimensional binary cube is called a perfect binary code with distance 3 if all balls of radius 1 (in the Hamming metric) with centers in C are pairwise disjoint and their union cover this binary cube. Similarly, we can define a perfect binary code in zero layer, consisting of all vectors of infinite-dimensional binary cube having finite supports. In this article we prove that the cardinality of all cosets of perfect binary codes in zero layer is the cardinality of the continuum. Moreover, the cardinality of all cosets of perfect binary codes in the whole binary cube is equal to the cardinality of the hypercontinuum.     

Toric cubes

A toric cube is a subset of the standard cube defined by binomial inequalities. These basic semialgebraic sets are precisely the images of standard cubes under monomial maps. We study toric cubes from the perspective of topological combinatorics. Explicit decompositions as CW-complexes are constructed. Their open cells are interiors of toric cubes and their boundaries are subcomplexes. The motivating example of a toric cube is the edge-product space in phylogenetics, and our work generalizes results known for that space.     

Isoperimetry,logarithmic sobolev inequalities on the discrete cube,and margulis' graph connectivity theorem

We prove that the suitably defined surface area of a subsetA of the cube {0,1} ⁿ is bounded below by a certain explicit function of the size ofA. We establish a family of logarithmic Sobolev inequalities on the cube related to this isoperimetric result. We also give a quantitative version of Margulis' graph connectivity theorem.Work partially supported by the US-Israel Binational Science Foundation.     

None of the coronoid systems can be isometrically embedded into a hypercube

A graph that can be isometrically embedded into a hypercube is called a partial cube (or binary Hamming graph). Klavžar, Gutman and Mohar [S. Klavžar, I. Gutman, B. Mohar, Labeling of benzenoid systems which reflects the vertex-distance relations, J. Chem. Inf. Comput. Sci. 35 (1995) 590–593] showed that all benzenoid systems are partial cubes. In this article we show that none of the coronoid systems (benzenoid systems with “holes”) is a partial cube.     

Multivariate Jackson-type inequality for a new type neural network approximation

In this paper, we introduce a new type neural networks by superpositions of a sigmoidal function and study its approximation capability. We investigate the multivariate quantitative constructive approximation of real continuous multivariate functions on a cube by such type neural networks. This approximation is derived by establishing multivariate Jackson-type inequalities involving the multivariate modulus of smoothness of the target function. Our networks require no training in the traditional sense.     

Discrete isoperimetric and Poincaré-type inequalities

We study some discrete isoperimetric and Poincaré-type inequalities for product probability measures μ ⁿ on the discrete cube {0, 1} ⁿ and on the lattice Z ⁿ . In particular we prove sharp lower estimates for the product measures of boundaries of arbitrary sets in the discrete cube. More generally, we characterize those probability distributions μ on Z which satisfy these inequalities on Z ⁿ . The class of these distributions can be described by a certain class of monotone transforms of the two-sided exponential measure. A similar characterization of distributions on R which satisfy Poincaré inequalities on the class of convex functions is proved in terms of variances of suprema of linear processes. Received: 30 April 1997 / Revised version: 5 June 1998     

The multidimensional cube recurrence

We introduce a recurrence which we term the multidimensional cube recurrence, generalizing the octahedron recurrence studied by Propp, Fomin and Zelevinsky, Speyer, and Fock and Goncharov and the three-dimensional cube recurrence studied by Fomin and Zelevinsky, and Carroll and Speyer. The states of this recurrence are indexed by tilings of a polygon with rhombi, and the variables in the recurrence are indexed by vertices of these tilings. We travel from one state of the recurrence to another by performing elementary flips. We show that the values of the recurrence are independent of the order in which we perform the flips; this proof involves nontrivial combinatorial results about rhombus tilings which may be of independent interest. We then show that the multidimensional cube recurrence exhibits the Laurent phenomenon - any variable is given by a Laurent polynomial in the other variables. We recognize a special case of the multidimensional cube recurrence as giving explicit equations for the isotropic Grassmannians IG(n−1,2n). Finally, we describe a tropical version of the multidimensional cube recurrence and show that, like the tropical octahedron recurrence, it propagates certain linear inequalities.     

The subgaussian constant and concentration inequalities

We study concentration inequalities for Lipschitz functions on graphs by estimating the optimal constant in exponential moments of subgaussian type. This is illustrated on various graphs and related to various graph constants. We also settle, in the affirmative, a question of Talagrand on a deviation inequality for the discrete cube. Research supported in part by NSF Grant No. DMS-0405587 and by EPSRC Visiting Fellowship. Research supported in part by NSF Grant No. DMS-9803239, DMS-0100289. Research supported in part by NSF Grant No. DMS-0401239.     

Markov-Bernstein type inequalities of multivariate polynomials with positive coefficients and applications

The Cauchy’s formula of entire functions f:C^k→C is used to establish Markov-Bernstein type inequalities of multivariate polynomials with positive coeffeicients on the k-dimensional simplex T_k⊂R^k and on the cube [0,1]^k. The main results generalize and improve those of G.G. Lorentz, etc. Some applications of these inequalities are also considered in polynomial constrained approximation.     

Poincaré type inequalities on the discrete cube and in the CAR algebra

We prove L ^p Poincaré inequalities with suitable dimension free constants for functions on the discrete cube {?1, 1} ⁿ . As well known, such inequalities for p an even integer allow to recover an exponential inequality hence the concentration phenomenon first obtained by Bobkov and Götze. We also get inequalities between the L ^p norms of $ \left\vert \nabla f\right\vert We prove L ^p Poincaré inequalities with suitable dimension free constants for functions on the discrete cube {−1, 1} ⁿ . As well known, such inequalities for p an even integer allow to recover an exponential inequality hence the concentration phenomenon first obtained by Bobkov and G?tze. We also get inequalities between the L ^p norms of and moreover L ^p spaces may be replaced by more general ones. Similar results hold true, replacing functions on the cube by matrices in the *-algebra spanned by n fermions and the L ^p norm by the Schatten norm C _p .     

Discrete length-volume inequalities and lower volume bounds in metric spaces

A theorem of W. Derrick ensures that the volume of any Riemannian cube \(([0,1]^n,g)\) is bounded below by the product of the distances between opposite codimension-1 faces. In this paper, we establish a discrete analog of Derrick’s inequality for weighted open covers of the cube \([0,1]^n\), which is motivated by a question about lower volume bounds in metric spaces. Our main theorem generalizes a previous result of the author in Kinneberg (J Differ Geom 100(2):349–388, 2015) which gave a combinatorial version of Derrick’s inequality and was used in the analysis of boundaries of hyperbolic groups. As an application, we answer a question of Y. Burago and V. Zalgaller about length-volume inequalities for pseudometrics on the unit cube.     

Incoherent majorities: The McGarvey problem in judgement aggregation

Judgement aggregation is a model of social choice where the space of social alternatives is the set of consistent truth-valuations (‘judgements’) on a family of logically interconnected propositions. It is well known that propositionwise majority voting can yield logically inconsistent judgements. We show that, for a variety of spaces, propositionwise majority voting can yield any possible judgement. By considering the geometry of sub-polytopes of the Hamming cube, we also estimate the number of voters required to achieve all possible judgements. These results generalize the classic results of McGarvey (1953) [13] and Stearns (1959) [22].     

On logarithmic Sobolev inequalities for continuous time random walks on graphs

We establish modified logarithmic Sobolev inequalities for the path distributions of some continuous time random walks on graphs, including the simple examples of the discrete cube and the lattice ZZ ^d . Our approach is based on the Malliavin calculus on Poisson spaces developed by J. Picard and stochastic calculus. The inequalities we prove are well adapted to describe the tail behaviour of various functionals such as the graph distance in this setting. Received: 6 April 1998 / Revised version: 15 March 1999 / Published on line: 14 February 2000     

Modifications of the Gehring lemma appearing in the study of parabolic initial-boundary-value problems

Some modifications of the Gehring lemma are required in the study of solutions to parabolic initialboundary-value problems, The Gehring lemma assert that if a function satisfies the reverse Hölder inequalitites in a cube, then the integrability degree of this function in Q increases in this cube. Earlier, the author formulated some generalizations of the Gehring lemma and used them in the study of parabolic quasilinear systems with controlled nonlinearity orders. In this paper, the proof of these generalizations are given. On the basis of the modification of the Gehring lemma proposed by the author, the theorem on the reverse Hölder inequalities is formulated in a form convenient for obtaining L^p-estimates for the derivatives of solutions to parabolic problems. An application of this theorem is also demonstrated. Bibliography: 19 titles.