Some Characterizations of Finite Hermitian Veroneseans

We characterize the finite Veronesean of all Hermitian varieties of PG(n,q²) as the unique representation of PG(n,q²) in PG(d,q), d n(n+2), where points and lines of PG(n,q²) are represented by points and ovoids of solids, respectively, of PG(d,q), with the only condition that the point set of PG(d,q) corresponding to the point set of PG(n,q²) generates PG(d,q). Using this result for n=2, we show that is characterized by the following properties: (1) ; (2) each hyperplane of PG(8,q) meets in q²+1, q³+1 or q³+q²+1 points; (3) each solid of PG(8,q) having at least q+3 points in common with shares exactly q²+1 points with it.51E24     

Finite codimensional linear isometries on spaces of differentiable and Lipschitz functions

We characterize finite codimensional linear isometries on two spaces, C ⁽ⁿ⁾[0; 1] and Lip [0; 1], where C ⁽ⁿ⁾[0; 1] is the Banach space of n-times continuously differentiable functions on [0; 1] and Lip [0; 1] is the Banach space of Lipschitz continuous functions on [0; 1]. We will see they are exactly surjective isometries. Also, we show that C ⁽ⁿ⁾[0; 1] and Lip [0; 1] admit neither isometric shifts nor backward shifts.     

Frame Self-orthogonal Mendelsohn Triple Systems

A Mendelsohn triple system of order ν, MTS(ν) for short, is a pair (X, B) where X is a ν-set (of points) and B is a collection of cyclic triples on X such that every ordered pair of distinct points from X appears in exactly one cyclic triple of B. The cyclic triple (a, b, c) contains the ordered pairs (a, b), (b, c) and (c, a). An MTS(ν) corresponds to an idempotent semisymmetric Latin square (quasigroup) of order ν. An MTS(ν) is called frame self-orthogonal, FSOMTS for short, if its associated semisymmetric Latin square is frame self-orthogonal. It is known that an FSOMTS(1 ⁿ ) exists for all n≡1 (mod 3) except n=10 and for all n≥15, n≡0 (mod 3) with possible exception that n=18. In this paper, it is shown that (i) an FSOMTS(2 ⁿ ) exists if and only if n≡0,1 (mod 3) and n>5 with possible exceptions n∈{9, 27, 33, 39}; (ii) an FSOMTS(3 ⁿ ) exists if and only if n≥4, with possible exceptions that n∈{6, 14, 18, 19}. *Research supported by NSFC 10371002 *Partially supported by National Science Foundation under Grant CCR-0098093     

The Isoperimetric Problem in Spherical Cylinders

The classical isoperimetric problem for volumes is solved in × ⁿ (1). Minimizers are shown to be invariant under the group O(n) acting standardly on ⁿ , via a symmetrization argument, and are then classified. Solutions are found among two (one-parameter) families: balls and sections of the form [a, b] × ⁿ . It is shown that the minimizers may be of both types. For n= 2, it is shown that the transition between the two families occurs exactly once. Some results for general n are also presented.     

A generalization of Fermat's little theorem

Fermat's Little Theorem states that if p is a prime number and gcd (x,p) = 1, then x^p?1 ≡ 1 (modp) If the requirement that gcd (x,p) = 1 is dropped, we can say x^p ≡ x(modp)for any integer x. Euler generalized Fermat's Theorem in the following way: if gcd (x,n) = 1 then x^φ(n) ≡ 1(modn), where φ is the Euler phi-function. It is clear that Euler's result cannot be extended to all integers x in the same way Fermat's Theorem can; that is, the congruence x^φ(n)+1 ≡ x(modn)is not always valid. In this note we show exactly when the congruence x^φ(n)+1 ≡ x(modn) is valid.     

H-designs with the properties of resolvability or (1, 2)-resolvability

An H-design is said to be (1, α)-resolvable, if its block set can be partitioned into α-parallel classes, each of which contains every point of the design exactly α times. When α = 1, a (1, α)-resolvable H-design of type g ⁿ is simply called a resolvable H-design and denoted by RH(g ⁿ ), for which the general existence problem has been determined leaving mainly the case of g ≡ 0 (mod 12) open. When α = 2, a (1, 2)-RH(1 ⁿ ) is usually called a (1, 2)-resolvable Steiner quadruple system of order n, for which the existence problem is far from complete. In this paper, we consider these two outstanding problems. First, we prove that an RH(12 ⁿ ) exists for all n ≥ 4 with a small number of possible exceptions. Next, we give a near complete solution to the existence problem of (1, 2)-resolvable H-designs with group size 2. As a consequence, we obtain a near complete solution to the above two open problems.     

Cubature over the sphere in Sobolev spaces of arbitrary order

This paper studies numerical integration (or cubature) over the unit sphere for functions in arbitrary Sobolev spaces H^s(S²), s>1. We discuss sequences of cubature rules, where (i) the rule Q_m(n) uses m(n) points and is assumed to integrate exactly all (spherical) polynomials of degree ≤n and (ii) the sequence (Q_m(n)) satisfies a certain local regularity property. This local regularity property is automatically satisfied if each Q_m(n) has positive weights. It is shown that for functions in the unit ball of the Sobolev space H^s(S²), s>1, the worst-case cubature error has the order of convergence O(n^-s), a result previously known only for the particular case . The crucial step in the extension to general s>1 is a novel representation of , where P_ℓ is the Legendre polynomial of degree ℓ, in which the dominant term is a polynomial of degree n, which is therefore integrated exactly by the rule Q_m(n). The order of convergence O(n^-s) is optimal for sequences (Q_m(n)) of cubature rules with properties (i) and (ii) if Q_m(n) uses m(n)=O(n²) points.     

Dimension Theory and Nonstable K1 of Quadratic Modules

Employing Bak's dimension theory, we investigate the nonstable quadratic K-group K _1,2n (A, ) = G _2n (A, )/E _2n (A, ), n 3, where G _2n (A, ) denotes the general quadratic group of rank n over a form ring (A, ) and E _2n (A, ) its elementary subgroup. Considering form rings as a category with dimension in the sense of Bak, we obtain a dimension filtration G _2n (A, ) G _2n ⁰(A, ) ; G _2n ¹(A, ) ... E _2n (A, ) of the general quadratic group G _2n (A, ) such that G _2n (A, )/G _2n ⁰(A, ) is Abelian, G _2n ⁰(A, ) G _2n ¹(A, ) ... is a descending central series, and G _2n ^d(A)(A, ) = E _2n (A, ) whenever d(A) = (Bass–Serre dimension of A) is finite. In particular K _1,2n (A, ) is solvable when d(A) < .     

(B n * GnSn) — Geometrien

A consequence of BENZ [3], [4] and ARTZY [2] is that the class of all (B ₂ ^* S₂)-geometries coinzides with the class of the chain geometries (K,K×K), K a commutative field. Therefore the tangency theorem holds in every (B ₂ ^* S₂)-geometry.In this paper we present a corresponding tangency theorem for (B ₃ ^* G₃S₃)-geometries and prove that up to isomorphisms the (B _n ^* G_nS_n)-geometries, n>1, are exactly the chain geometries (K,Kⁿ).     

Routing through a generalized switchbox

We present an algorithm for the routing problem for two-terminal nets in generalized switchboxes. A generalized switchbox is any subset R of the planar rectangular grid with no nontrivial holes, i.e., every finite face has exactly four incident vertices. A net is a pair of nodes of nonmaximal degree on the boundary of R. A solution is a set of edge-disjoint paths, one for each net. Our algorithm solves standard generalized switchbox routing problems in time O(n(log n)²) where n is the number of vertices of R, i.e., it either finds a solution or indicates that there is none. A problem is standard if deg(ν) + ter(ν) is even for all vertices ν where deg(ν) is the degree of ν and ter(ν) is the number of nets which have ν as a terminal. For nonstandard problems we can find a solution in time O(n(log n)² + |U|²) where U is the set of vertices ν with deg(ν) + ter(ν) is odd.     

The number of different distances determined by a set of points in the Euclidean plane

In 1946 P. Erdös posed the problem of determining the minimum numberd(n) of different distances determined by a set ofn points in the Euclidean plane. Erdös provedd(n) cn ^1/2 and conjectured thatd(n)cn/ logn. If true, this inequality is best possible as is shown by the lattice points in the plane. We showd(n)n ^4/5/(logn) ^c .The research of W. T. Trotter was supported in part by the National Science Foundation under DMS 8713994 and DMS 89-02481.     

Quasi sure version of a theorem of littlewood

Let (c _n) _nZ be a double-sided sequence of complex numbers; if, for quasi-all (i.e. in the Baire sense) choices of signs ( _n) _nZ , ( _n c _n) _nZ is a Fourier-Stieltjes sequence, then we prove that (c _n) _nZ l ² (Z); this extends a result of Littlewood and at the same time provides a very simple proof of this result.     

Dade's Invariant Conjecture for the Symplectic Group Sp4(2 n ) and the Special Unitary Group SU4(22n ) in Defining Characteristic

In this article, we verify Dade's projective invariant conjecture for the symplectic group Sp₄(2 ⁿ ) and the special unitary group SU₄(2²ⁿ ) in the defining characteristic, that is, in characteristic 2. Furthermore, we show that the Isaacs–Malle–Navarro version of the McKay conjecture holds for Sp₄(2 ⁿ ) and SU₄(2²ⁿ ) in the defining characteristic, that is, Sp₄(2 ⁿ ) and SU₄(2²ⁿ ) are good for the prime 2 in the sense of Isaacs, Malle, and Navarro.     

On-line coloringk-colorable graphs

We show that for anyk, there exists an on-line algorithm that will color anyk-colorable graph onn vertices withO(n ^1−1/k! ) colors. This improves the previous best upper bound ofO(nlog^(2k−3) n/log^(2k−4) n) due to Lovász, Saks, and Trotter. In the special casesk=3 andk=4 we obtain on-line algorithms that useO(n ^2/3log^1/3 n) andO(n ^5/6log^1/6 n) colors, respectively.     

Polar SAT and related graphs

We introduce polar SAT and show that a general SAT can be reduced to it in polynomial time. A set of clauses C is called polar if there exists a partition C^pCⁿ=C, called a polar partition, such that each clause in C^p involves only positive (i.e., non-complemented) variables, while each clause in Cⁿ contains only negative (i.e., complemented) variables. A polar set of clauses C=(C^p,Cⁿ) is called (p,n)-polar, where p1 and n1, if each clause in C^p (respectively, in Cⁿ) contains exactly p (respectively, exactly n) literals. We classify all (p,n)-polar SAT Problems according to their complexity. Specifically, a (p,n)-Polar SAT problem is NP-complete if either p>n2 or n>p2. Otherwise it can be solved in polynomial time. We introduce two new hereditary classes of graphs, namely polar satgraphs and polar (3,2)-satgraphs, and we characterize them in terms of forbidden induced subgraphs. Both characterization involve an infinite number of minimal forbidden induced subgraphs. As are result, we obtain two narrow hereditary subclasses of weakly chordal graphs where Independent Domination is an NP-complete problem.     

The endomorphism spectrum of an ordered set

Theendomorphism spectrum of an ordered setP, spec(P)={|f(P)|:f End(P)} andspectrum number, sp(P)=max(spec(P)\{|P|}) are introduced. It is shown that |P|>(1/2)n(n – 1) ^{n – 1} implies spec(P) = {1, 2, ...,n} and that if a projective plane of ordern exists, then there is an ordered setP of size 2n ²+2n+2 with spec(P)={1, 2, ..., 2n+2, 2n+4}. Lettingh(n)=max{|P|: sp(P)n}, it follows thatc ₁ n ²h(n)c ₂ n ⁿ⁺¹ for somec ₁ andc ₂. The lower bound disproves the conjecture thath(n)2n. It is shown that if |P| – 1 spec(P) thenP has a retract of size |P| – 1 but that for all there is a bipartite ordered set with spec(P) = {|P| – 2, |P| – 4, ...} which has no proper retract of size|P| – . The case of reflexive graphs is also treated.Partially supported by a grant from the NSERC.Partially supported by a grant from the NSERC.     

Induced subgraphs of prescribed size

A subgraph of a graph G is called trivial if it is either a clique or an independent set. Let q(G) denote the maximum number of vertices in a trivial subgraph of G. Motivated by an open problem of Erd?s and McKay we show that every graph G on n vertices for which q(G)≤ C log n contains an induced subgraph with exactly y edges, for every y between 0 and n^{δ (C)}. Our methods enable us also to show that under much weaker assumption, i.e., q(G) ≤ n/14, G still must contain an induced subgraph with exactly y edges, for every y between 0 and . © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 239–251, 2003     

On the Construction of Cosine Operator Functions and Semigroups on Function Spaces with Generator a(x)(d2dx2)+b(x)(d/dx)+c(x); Theory

In this paper we develop a method to solve exactly partial differential equations of the type ( ⁿ /t ⁿ )f(x,t)=(a(x)( ⁿ /x ⁿ )+b(x) (/x+c(x))f(x,t); n=1,2, with several boundary conditions, where f·,t) lies in a function space. The most powerful tool here is the theory of cosine operator functions and their connection to (holomorphic) semigroups. The method is that generally we are able to unify and generalize many theorems concerning problems in the theories of holomorphic semigroups, cosine operator functions, and approximation theory, especially these dealing with approximation by projections. These applications will be found in [14].     

On the Approximation of Quantile Processes by Kiefer Processes

We prove that the best possible almost sure rate of uniform approximation of a uniform quantile process by a normed Kiefer process is O(n ^–1/4(log n)^1/2× (log log n)^1/4).     

A shortness exponent for r-regular r-connected graphs

Let r≧ 3 be an integer. It is shown that there exists ε= ε(r), 0 < ε < 1, and an integer N = N(r) > 0 such that for all n ≧ N (if r is even) or for all even n ≧ N(if r is odd), there is an r-connected regular graph of valency r on exactly n vertices whose longest cycles have fewer than n^ε vertices.