More Efficient Algorithm for Ordered Tree Inclusion

Given two ordered trees and , the tree inclusion problem is to determine whether it is possible to obtain from by deleting nodes. Recently, this problem has been recognized as an important primitive in query processing for structured text databases. In this paper we present anO(|leaves()| ||) time andO(|leaves()|min(depth(), |leaves()|)) space algorithm for ordered tree inclusion, by means of a sophisticated bottom-up-matching strategy. Our algorithm improves the previous best one (Kilpeläinen, 1992, Ph.D. thesis, Dept. Computer Science, Univ. Helsinki) that requiresO(|| ||) time andO(||min(depth(), |leaves()|)) space.     

An endpoint space–time estimate for the Schrödinger equation

We obtain endpoint estimates for the Schrödinger operator f→eitΔf in with initial data f in the homogeneous Sobolev space . The exponents and regularity index satisfy and . For n=2 we prove the estimates in the range q>16/5, and for n?3 in the range q>2+4/(n+1).     

Second order, multi-point problems with variable coefficients

In this paper, we consider the eigenvalue problem consisting of the equation where and λ∈R, together with the multi-point boundary conditions where m^±?1 are integers, and, for i=1,…,m^±, , , with , . We show that if the coefficients are sufficiently small (depending on r), then the spectral properties of this problem are similar to those of the usual separated problem, but if the coefficients are not sufficiently small, then these standard spectral properties need not hold. The spectral properties of such multi-point problems have been obtained before for the constant coefficient case (r≡1), but the variable coefficient case has not been considered previously (apart from the existence of ‘principal’ eigenvalues).Some nonlinear multi-point problems are also considered. We obtain a (partial) Rabinowitz-type result on global bifurcation from the eigenvalues, and various nonresonance conditions for the existence of general solutions and also of nodal solutions—these results rely on the spectral properties of the linear problem.     

Higher order log-concavity in Euler’s difference table

For 0≤k≤n, let be the entries in Euler’s difference table and let . Dumont and Randrianarivony showed equals the number of permutations on [n] whose fixed points are contained in {1,2,…,k}. Rakotondrajao found a combinatorial interpretation of the number in terms of k-fixed-points-permutations of [n]. We show that for any n≥1, the sequence is essentially 2-log-concave and reverse ultra log-concave.     

On the irrationality of factorial series III

In this paper we derive some irrationality and linear independence results for series of the form where is either a non-negative integer sequence with υ_n = o(log n/log log n) or a non-decreasing integer sequence with .     

Normalizers of non-split Cartan subgroups, modular curves, and the class number one problem

Let be the open non-cuspidal locus of the modular curve associated to the normalizer of a non-split Cartan subgroup of level n. As Serre pointed out, an imaginary quadratic field of class number one gives rise to an integral point on for suitably chosen n. In this note, we give a genus formula for the modular curves and we give three new solutions to the class number one problem using the modular curves for n=16,20,21. These are the only such modular curves of genus ?2 that had not yet been exploited.     

Random induced subgraphs of Cayley graphs induced by transpositions

In this paper we study random induced subgraphs of Cayley graphs of the symmetric group induced by an arbitrary minimal generating set of transpositions. A random induced subgraph of this Cayley graph is obtained by selecting permutations with independent probability, λ_n. Our main result is that for any minimal generating set of transpositions, for probabilities where and δ>0, a random induced subgraph has a.s. a unique largest component of size . Here x(?_n) is the survival probability of a Poisson branching process with parameter λ=1+?_n.     

A Representation of Projection Lattices and Their States in Euclidean Space

We propose a representationr : ∪ Ω → ^ν, where is the collection of closed subspaces of ann-dimensional real, complex, or quaternionic Hilbert space , or equivalently, the projection lattice of this Hilbert space, where Ω is the set of all states ω : → [0, 1]. The value that ω ∈ Ω takes ina ∈ is given by the scalar product of the representative points (r(a) andr(ω)). The representationr(a ∨ b) of the join of two orthogonal elementsa, b ∈ is equal tor(a) + r(b). The convex closure of the representation of Σ, the set of atoms of , is equal to the representation of Ω.     

A new characterization of projections of quadrics in finite projective spaces of even characteristic

We will classify, up to linear representations, all geometries fully embedded in an affine space with the property that for every antiflag {p,L} of the geometry there are either 0, α, or q lines through p intersecting L. An example of such a geometry with α=2 is the following well known geometry . Let Q_n+1 be a nonsingular quadric in a finite projective space , n≥3, q even. We project Q_n+1 from a point r∉Q_n+1, distinct from its nucleus if n+1 is even, on a hyperplane not through r. This yields a partial linear space whose points are the points p of , such that the line 〈p,r〉 is a secant to Q_n+1, and whose lines are the lines of which contain q such points. This geometry is fully embedded in an affine subspace of and satisfies the antiflag property mentioned. As a result of our classification theorem we will give a new characterization theorem of this geometry.     

On the complexity of submodular function minimisation on diamonds

Let (L;?,?) be a finite lattice and let n be a positive integer. A function f:Lⁿ→R is said to be submodular if for all . In this article we study submodular functions when L is a diamond. Given oracle access to f we are interested in finding such that as efficiently as possible. We establish

• • 

  a min–max theorem, which states that the minimum of the submodular function is equal to the maximum of a certain function defined over a certain polyhedron; and

• • 

  a good characterisation of the minimisation problem, i.e., we show that given an oracle for computing a submodular f:Ln→Z and an integer m such that , there is a proof of this fact which can be verified in time polynomial in n and ; and

• • 

  a pseudopolynomial-time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular f:Ln→Z one can find in time bounded by a polynomial in n and .

     

Modulation spaces, Wiener amalgam spaces, and Brownian motions

We study the local-in-time regularity of the Brownian motion with respect to localized variants of modulation spaces and Wiener amalgam spaces . We show that the periodic Brownian motion belongs locally in time to and for (s−1)q<−1, and the condition on the indices is optimal. Moreover, with the Wiener measure μ on T, we show that and form abstract Wiener spaces for the same range of indices, yielding large deviation estimates. We also establish the endpoint regularity of the periodic Brownian motion with respect to a Besov-type space . Specifically, we prove that the Brownian motion belongs to for (s−1)p=−1, and it obeys a large deviation estimate. Finally, we revisit the regularity of Brownian motion on usual local Besov spaces , and indicate the endpoint large deviation estimates.     

Pósa-condition and nowhere-zero 3-flows

Let G be a simple graph on n vertices and π(G)=(d₁,d₂,…,d_n) be the degree sequence of G, where n≥3 and d₁≤d₂≤?≤d_n. The classical Pósa’s theorem states that if d_m≥m+1 for and d_m+1≥m+1 for n being odd and , then G is Hamiltonian, which implies that G admits a nowhere-zero 4-flow. In this paper, we further show that if G satisfies the Pósa-condition that d_m≥m+1 for and d_m+1≥m+1 for n being odd and , then G has no nowhere-zero 3-flow if and only if G is one of seven completely described graphs.     

The non-existence of some perfect codes over non-prime power alphabets

Let denote the number of times the prime number p appears in the prime factorization of the integer q. The following result is proved: If there is a perfect 1-error correcting code of length n over an alphabet with q symbols then, for every prime number .This condition is stronger than both the packing condition and the necessary condition given by the Lloyd theorem, as it for example excludes the existence of a perfect code with the parameters (n,q,e)=(19,6,1).     

Unconditional constants and polynomial inequalities

If P is a polynomial on R^m of degree at most n, given by , and P_n(R^m) is the space of such polynomials, then we define the polynomial |P| by . Now if is a convex set, we define the norm on P_n(R^m), and then we investigate the inequality providing sharp estimates on for some specific spaces of polynomials. These ’s happen to be the unconditional constants of the canonical bases of the considered spaces.     

Indecomposable and noncrossed product division algebras over function fields of smooth p-adic curves

We construct indecomposable and noncrossed product division algebras over function fields of connected smooth curves X over Zp. This is done by defining an index preserving morphism which splits , where is the completion of K(X) at the special fiber, and using it to lift indecomposable and noncrossed product division algebras over .     

Edge choosability and total choosability of planar graphs with no 3-cycles adjacent 4-cycles

Two cycles are said to be adjacent if they share a common edge. Let G be a planar graph without triangles adjacent 4-cycles. We prove that if Δ(G)≥6, and and if Δ(G)≥8, where and denote the list edge chromatic number and list total chromatic number of G, respectively.     

On a conjecture of Shanks

The conjecture in question concerns the function ?n related to the distribution of the zeroes of the Riemann zeta-function, γn, over the Gram points gn. It is the purpose of this article to show that for any α>0 the sum and this was conjectured, on numerical evidence, by Shanks (1961) [7] to be true for .     

Forbidden configurations and repeated induction

For a given k×? matrix F, we say a matrix A has no configurationF if no k×? submatrix of A is a row and column permutation of F. We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. We define as the maximum number of columns in an m-rowed simple matrix which has no configuration F. A fundamental result of Sauer, Perles and Shelah, and Vapnik and Chervonenkis determines exactly, where K_k denotes the k×2^k simple matrix. We extend this in several ways. For two matrices G,H on the same number of rows, let [G∣H] denote the concatenation of G and H. Our first two sets of results are exact bounds that find some matrices B,C where and . Our final result provides asymptotic boundary cases; namely matrices F for which is O(m^p) yet for any choice of column α not in F, we have is Ω(m^p+1). This is evidence for a conjecture of Anstee and Sali. The proof techniques in this paper are dominated by repeated use of the standard induction employed in forbidden configurations. Analysis of base cases tends to dominate the arguments. For a k-rowed (0,1)-matrix F, we also consider a function which is the minimum number of columns in an m-rowed simple matrix for which each k-set of rows contains F as a configuration.     

A pattern sequence approach to Stern’s sequence

Suppose that w∈1{0,1}^∗ and let a_w(n) be the number of occurrences of the word w in the binary expansion of n. Let {s(n)}_n?0 denote the Stern sequence, defined by s(0)=0, s(1)=1, and for n?1, In this note, we show that where denotes the complement of w (obtained by sending 0?1 and 1?0) and [w]₂ denotes the integer specified by the word w∈{0,1}^∗ interpreted in base 2.