Zak Transforms on Binary Fields

We introduce analogues of the Zak Transform on binary fields, and show that they are bounded linear operators on L^p for p=1 and 2. We also show that positivity of Zak transforms can be used to decide whether orthonormal systems generated by multiplying characters of F by a weight function are complete or not.     

Fast and Exact Simulation of Large Gaussian Lattice Systems in ℝ2: Exploring the Limits

The circulant embedding technique allows for the fast and exact simulation of stationary and intrinsically stationary Gaussian random fields. The method uses periodic embeddings and relies on the fast Fourier transform. However, exact simulations require that the periodic embedding is nonnegative definite, which is frequently not the case for two-dimensional simulations. This work considers a suggestion by Michael Stein, who proposed nonnegative definite periodic embeddings based on suitably modified, compactly supported covariance functions. Theoretical support is given to this proposal, and software for its implementation is provided. The method yields exact simulations of planar Gaussian lattice systems with 10⁶ and more lattice points for wide classes of processes, including those with powered exponential, Matérn, and Cauchy covariances.     

A variant of the Johnson-Lindenstrauss lemma for circulant matrices

We continue our study of the Johnson-Lindenstrauss lemma and its connection to circulant matrices started in Hinrichs and Vybíral (in press) [7]. We reduce the bound on k from k=Ω(ε−2log³n) proven there to k=Ω(ε−2log²n). Our technique differs essentially from the one used in Hinrichs and Vybíral (in press) [7]. We employ the discrete Fourier transform and singular value decomposition to deal with the dependency caused by the circulant structure.     

Stability of travelling wave solutions to a semilinear hyperbolic system with relaxation

We study a semilinear hyperbolic system with relaxation and investigate the asymptotic stability of travelling wave solutions with shock profile. It is shown that the travelling wave solution is asymptotically stable, provided the initial disturbance is suitably small. Moreover, we show that the time convergence rate is polynomially (resp. exponentially) fast as t→∞ if the initial disturbance decays polynomially (resp. exponentially) for x→∞. Our proofs are based on the space–time weighted energy method. Copyright © 2008 John Wiley & Sons, Ltd.     

Two observations regarding embedding subsets of Euclidean spaces in normed spaces

This paper contains two results concerning linear embeddings of subsets of Euclidean space in low-dimensional normed spaces. The first is an improvement of the known dependence on ? in Dvoretzky's theorem from order of ?² to order of ? (except for log factors). The second is a joint generalization of (Milman's version of) Dvoretzky's theorem and (a recent generalization by Klartag and Mendelson of) the Johnson-Lindenstrauss Lemma.     

Finite semigroups with slowly growing pn-sequences

The p _n -sequence of a semigroup S is said to be polynomially bounded, if there exist a positive constant c and a positive integer r such that the inequality p _n (S) ≤cn ^r holds for all n≥ 1. In this paper, we fully describe all finite semigroups having polynomially bounded p _n -sequences. First we give a characterization in terms of identities satisfied by these semigroups. In the sequel, this result will allow an insight into the structure of such semigroups. We are going to deal with certain ideals and the construction of ideal extension of semigroups. In addition, we supply an effective procedure for deciding whether a finite semigroup has polynomially bounded p _n -sequence and give some examples. Received March 5, 1999; accepted in final form November 1, 1999.     

Exponential decay of non‐linear wave equation with a viscoelastic boundary condition

We study in this paper the global existence and exponential decay of solutions of the non‐linear unidimensional wave equation with a viscoelastic boundary condition. We prove that the dissipation induced by the memory effect is strong enough to secure global estimates, which allow us to show existence of global smooth solution for small initial data. We also prove that the solution decays exponentially provided the resolvent kernel of the relaxation function, k decays exponentially. When k decays polynomially, the solution decays polynomially and with the same rate. Copyright © 2000 John Wiley & Sons, Ltd.     

Nonuniqueness for a bounded, differentiable complete orthonormal system inL 2[0, 1]

The argument of Müsegian and Ovsepjan is adapted to produce a complete orthonormal system on [0, 1] of uniformly bounded functions, differentiable on [0, 1], andC ^∞ on [0, 1], for which the analogue of Cantor's uniqueness theorem is false. We also construct a complete orthonormal system ofC ^∞ functions which vanish to infinite order at both endpoints.     

On a problem of littlewood

The theorem on the tending to zero of coefficients of a trigonometric series is proved when theL ¹-norms of partial sums of this series are bounded. It is shown that the analog of Helson's theorem does not hold for orthogonal series with respect to the bounded orthonormal system. Two facts are given that are similar to Weis' theorem on the existence of a trigonometric series which is not a Fourier series and whoseL ¹-norms of partial sums are bounded.     

New results on rectilinear crossing numbers and plane embeddings

We show that if a graph has maximum degree d and crossing number k, its rectilinear crossing number is at most O(dk²). Hence for graphs of bounded degree, the crossing number and the rectilinear crossing number are bounded as functions of one another. We also obtain a generalization of Tutte's theorem on convex embeddings of 3-connected plane graphs. © 1929 John Wiley & Sons, Inc.     

DAG‐Width and Circumference of Digraphs

We prove that every digraph of circumference l has DAG‐width at most l. This is best possible and solves a recent conjecture from S. Kintali (ArXiv:1401.2662v1 [math.CO], January 2014).¹ As a consequence of this result we deduce that the k‐linkage problem is polynomially solvable for every fixed k in the class of digraphs with bounded circumference. This answers a question posed in J. Bang‐Jensen, F. Havet, and A. K. Maia (Theor Comput Sci 562 (2014), 283–303). We also prove that the weak k‐linkage problem (where we ask for arc‐disjoint paths) is polynomially solvable for every fixed k in the class of digraphs with circumference 2 as well as for digraphs with a bounded number of disjoint cycles each of length at least 3. The case of bounded circumference digraphs is still open. Finally, we prove that the minimum spanning strong subdigraph problem is NP‐hard on digraphs of DAG‐width at most 5.     

On the rank of mixed 0,1 polyhedra

For a polytope in the [0,1] ⁿ cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n ²logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables. Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001     

An Independence Result on Weak Second Order Bounded Arithmetic

We show that length initial submodels of S¹₂ can be extended to a model of weak second order arithmetic. As a corollary we show that the theory of length induction for polynomially bounded second order existential formulae cannot define the function division.     

Recognizing graphic matroids

There is no polynomially bounded algorithm to test if a matroid (presented by an “independence oracle”) is binary. However, there is one to test graphicness. Finding this extends work of previous authors, who have given algorithms to test binary matroids for graphicness. Our main tool is a new result that ifM′ is the polygon matroid of a graphG, andM is a different matroid onE(G) with the same rank, then there is a vertex ofG whose star is not a cocircuit ofM.     

New regular embeddings of n‐cubes Qn

We investigate highly symmetrical embeddings of the n‐dimensional cube Q_n into orientable compact surfaces which we call regular embeddings of Q_n. We derive some general results and construct some new families of regular embeddings of Q_n. In particular, for n = 1, 2,3(mod 4), we classify the regular embeddings of Q_n which can be expressed as balanced Cayley maps. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 297–312, 2004     

Proper holomorphic embeddings of finitely connected planar domains into ℂ n

In this paper we consider proper holomorphic embeddings of finitely connected planar domains into ? ⁿ that approximate given proper embeddings on smooth curves. As a side result we obtain a tool for approximating a $\mathcal{C}^{\infty}$ diffeomorphism on a polynomially convex set in ? ⁿ by an automorphism of ? ⁿ that satisfies some additional properties along a real embedded curve.     

On the asymptotic existence of complex Hadamard matrices

Let N = N(q) be the number of nonzero digits in the binary expansion of the odd integer q. A construction method is presented which produces, among other results, a block circulant complex Hadamard matrix of order 2^αq, where α ≥ 2N - 1. This improves a recent result of Craigen regarding the asymptotic existence of Hadamard matrices. We also present a method that gives complex orthogonal designs of order 2^α+1q from complex orthogonal designs of order 2^α. We also demonstrate the existence of a block circulant complex Hadamard matrix of order 2^βq, where © 1997 John Wiley & Sons, Inc. J Combin Designs 5:319–327, 1997     

Viscoelastic boundary stabilization for a transmission problem in elasticity

We consider an anisotropic body which is constituted of twodifferent types of materials supporting a memory boundary conditionand we show that its energy decays uniformly as time goes toinfinity with the same rate as the relaxation function g, thatis, the energy decays exponentially when g decays exponentially,and polynomially when g decays polynomially.     

Approximate fixed-rank closures of covering problems

Consider a 0/1 integer program min{c^Tx :Ax≥b, x ∈ {0,1}ⁿ} where A is nonnegative. We show that if the number of minimal covers of Ax≥b is polynomially bounded, then for any ε>0 and any fixed q, there is a polynomially large lift-and-project relaxation whose value is at least (1−ε) times the value of the rank ≤q relaxation. A special case of this result is that given by set-covering problems, or, generally, problems where the coefficients in A and b are bounded. This research was partially funded by NSF awards ITR:CCR-0213848 and DMI-0200221 formerly: Set covering problems and Chvátal-Gomory cuts     

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.