The Analytic Polynomial-Time Hierarchy

Motivated by results on interactive proof systems we investigate an ?-?hierarchy over P using word quantifiers as well as two types of set quantifiers. This hierarchy, which extends the (arithmetic) polynomial-time hierarchy, is called the analytic polynomial-time hierarchy. It is shown that every class of this hierarchy coincides with one of the following Classes: ∑, Π (k?0), PSPACE, ∑ or Π (k?1). This improves previous results by Orponen [6] and allows interesting comparisons with the above mentioned results on inter-active proof systems.     

Function Spaces with Exponential Weights II

This paper is a continuation of [8]. We study weighted function spaces of type B and F on the Euclidean space Rⁿ, where u is a weight function of at most exponential growth. In particular, u(χ (±|χ|) is an admissible weight. We deal with atomic decompositions of these spaces. Furthermore, we prove that the spaces B and F are isomorphic to the corresponding unweighted spaces B and F.     

Entropy Numbers in Weighted Function Spaces and Eigenvalue Distributions of Some Degenerate Pseudodifferential Operators II

This paper is the continuation of [17]. We investigate mapping and spectral properties of pseudodifferential operators of type Ψ with χ χ ? ? and 0 ≤ γ ≤ 1 in the weighted function spaces B (?ⁿ, w(x)) and F (?ⁿ, w(x)) treated in [17]. Furthermore, we study the distribution of eigenvalues and the behaviour of corresponding root spaces for degenerate pseudodifferential operators preferably of type b₂(x) b(x, D) b₁(x), where b₁(x) and b₂(x) are appropriate functions and b(x, D) ? Ψ. Finally, on the basis of the Birman-Schwinger principle, we deal with the “negative spectrum” (bound states) of related symmetric operators in L₂.     

Hardy-Littlewood Maximal Operator,Singular Integral Operators and the Riesz Potentials on Generalized Morrey Spaces

Any continuous linear operator T: L^p → L^q has a natural vector-valued extension T: L^p(l) → L^q(l) which is automatically continuous. Relations between the norms of these operators in the cases of p = q and r = 2 were considered by Marcinkiewicz -Zygmund [28], Herz [14] and Krivine [19] - [21]. In this paper we study systematically these relations and given some applications. It turns out that some known results can be proved in a simple way as a consequence of these developments.     

The circular chromatic number of the Mycielskian of G

In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph μ(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals χ(G) + 1. Chang, Huang, and Zhu [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear] have investigated circular chromatic numbers of Mycielskians for several classes of graphs. In this article, we study circular chromatic numbers of Mycielskians for another class of graphs G. The main result is that χ_c(μ(G)) = χ(μ(G)), which settles a problem raised in [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear, and X. Zhu, to appear]. As χ_c(G) = and χ(G) = , consequently, there exist graphs G such that χ_c(G) is as close to χ(G) − 1 as you want, but χ_c(μ(G)) = χ(μ(G)). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 63–71, 1999     

Subgraphs smaller than the girth

For graphs A, B, let () denote the number of subsets of nodes of A for which the induced subgraph is B. If G and H both have girth > k, and if () = () for every k-node tree T, then for every k-node forest F, () = (). Say the spread of a tree is the number of nodes in a longest path. If G is regular of degree d, on n nodes, with girth > k, and if F is a forest of total spread ≤k, then the value of () depends only on n and d.     

On the Lorentz-Marcinkiewicz Operator Ideal

This article deals with the LORENTZ-MARCINKIEWICZ operator ideal ?? generated by an additive s-function and the LORENTZ-MARCINKIEWICZ sequence space λ^q(φ). We give eigenvalue distributions for operators belonging to ?? (E, E) and we show the interpolation properties of ??-ideals. Furthermore, we study certain SCHAUDER bases in ?? (H, K), H and K Hilbert spaces.     

On the density of 2‐colorable 3‐graphs in which any four points span at most two edges

Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)$. We improve the previously best known lower and upper bounds of 0.25682 and 3/10?ε, respectively, by showing that This implies the following new upper bound for the Turán density of K In order to establish these results we use a combination of the properties of computer‐generated extremal 3‐graphs for small n and an argument based on “super‐saturation”. Our computer results determine the exact values of ex(n, K) for n≤19 and ex₂(n, K) for n≤17, as well as the sets of extremal 3‐graphs for those n. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 105–114, 2010     

Über die Radon-Transformation kreissymmetrischer Funktionen und ihre Beziehung zur Sommerfeldschen Theorie der Hankelfunktionen

For the Radon transform of functions with circular symmetry an inversion formula is proved in a new and elementary way. The inversion formula combined with Fourier theory is applied to Sommer-feld's integral for H, yielding a representation of products which generalizes Nicholson's integral for |H| ².     

ANALYTIC COMPLETENESS THEOREM FOR ABSOLUTELY CONTINUOUS BIPROBABILITY MODELS

Hoover [2] proved a completeness theorem for the logic L(∫)??. The aim of this paper is to prove a similar completeness theorem with respect to product measurable biprobability models for a logic L(∫₁, ∫₂) with two integral operators. We prove: If T is a ∑₁ definable theory on ?? (a countable admissible set and ω ∈) and consistent with the axioms of L(∫₁, ∫₂), then there is an analytic absolutely continuous biprobability model in which every sentence in T is satified.     

On invariant measures of extensions of Markov transition functions

By using the LITTLEWOOD matrices A_2n we generalize CLARKSON' S inequalities, or equivalently, we determine the norms ‖A_2n: l(L_P) → l(L_P)‖ completely. The result is compared with the norms ‖A_2n: l → l‖, which are calculated implicitly in PIETSCH [6].     

Resonance phenomena for a class of partial differential equations of higher order in cylindrical waveguides

We consider a domain Ω in ?ⁿ of the form Ω = ?^l × Ω′ with bounded Ω′ ? ?^n?l. In Ω we study the Dirichlet initial and boundary value problem for the equation ? u + [(? ? ?… ? ?)^m + (? ? ?… ? ?)^m]u = fe^?iωt. We show that resonances can occur if 2m ≥ l. In particular, the amplitude of u may increase like t^α (α rational, 0<α<1) or like in t as t∞∞. Furthermore, we prove that the limiting amplitude principle holds in the remaining cases.     

Recursive Structures and Ershov's Hierarchy

Ash and Nerode [2] gave natural definability conditions under which a relation is intrinsically r. e. Here we generalize this to arbitrary levels in Ershov's hierarchy of Δ sets, giving conditions under which a relation is intrinsically α-r. e. Mathematics Subject Classification: 03C57, 03D55.     

Global attractors for 2‐D wave equations with displacement‐dependent damping

In this paper the long‐time behaviour of the solutions of 2‐D wave equation with a damping coefficient depending on the displacement is studied. It is shown that the semigroup generated by this equation possesses a global attractor in H(Ω) × L₂(Ω) and H²(Ω)∩H(Ω) × H(Ω). Copyright © 2009 John Wiley & Sons, Ltd.     

A quantitative compactness estimate for scalar conservation laws

In the case of a scalar conservation law with convex flux in space dimension one, P. D. Lax proved [Comm. Pure and Appl. Math. 7 (1954)] that the semigroup defining the entropy solution is compact in L for each positive time. The present note gives an estimate of the ?‐entropy in L of the set of entropy solutions at time t > 0 whose initial data run through a bounded set in L¹. © 2005 Wiley Periodicals, Inc.     

Entropy Numbers in Weighted Function Spaces and Eigenvalue Distributions of Some Degenerate Pseudodifferential Operators I

In this paper we study weighted function spaces of type B(?ⁿ, Q(x)) and F(?ⁿ, Q(x)), where Q(x) is a weight function of at most polynomial growth. Of special interest are the weight functions Q(x) = (1 + |x|²)^α/2 with α ? ?. The main result deals with estimates for the entropy numbers of compact embeddings between spaces of this type.     

The determining number of a Cartesian product

A set S of vertices is a determining set for a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G, denoted Det(G), is the size of a smallest determining set. This paper begins by proving that if G=G□?□G is the prime factor decomposition of a connected graph then Det(G)=max{Det(G)}. It then provides upper and lower bounds for the determining number of a Cartesian power of a prime connected graph. Further, this paper shows that Det(Q_n)=?log₂n?+1 which matches the lower bound, and that Det(K)=?log₃(2n+1)?+1 which for all n is within one of the upper bound. The paper concludes by proving that if H is prime and connected, Det(Hⁿ)=Θ(logn). © 2009 Wiley Periodicals, Inc. J Graph Theory     

ITERATIONS OF SATISFACTION CLASSES AND MODELS OF PEANO ARITHMETIC

We consider iterations of satisfaction classes and apply them to construct expansions of models of Peano arithmetic to models of A|Δ+∑-AC. 1991 MSC: 03F35, 03C62.     

Regularity - Properties of the Solution of the Homogeneous Wave Equation

The aim of this paper is to prove regularity-properties for solutions of the wave equation in B with p < 1. Up to now no such result is known. For p ≥ 1 a large amount of work has been done, cf. for instance [9], [7], [8], [10]. The results in this paper for p> 1 are not optimal, which can be seen comparing them with [9]. Whether or not our results are optimal for p ≤ 1 is open.