Efficient partition trees

We prove a theorem on partitioning point sets inE ^d (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space,O(n logn) deterministic preprocessing time, andO(n ^1?1/d (logn) ^O(1)) query time. WithO(nlogn) preprocessing time, where δ is an arbitrary positive constant, a more complicated data structure yields query timeO(n ^1?1/d (log logn) ^O(1)). This attains the lower bounds due to Chazelle [C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelleet al. [CSW]. The partition result implies that, forr ^d≤n ^1?δ, a (1/r)-approximation of sizeO(r ^d) with respect to simplices for ann-point set inE ^d can be computed inO(n logr) deterministic time. A (1/r)-cutting of sizeO(r ^d) for a collection ofn hyperplanes inE ^d can be computed inO(n logr) deterministic time, provided thatr≤n ^1/(2d?1).     

Revlex-initial 0/1-polytopes

We introduce revlex-initial 0/1-polytopes as the convex hulls of reverse-lexicographically initial subsets of 0/1-vectors. These polytopes are special knapsack-polytopes. It turns out that they have remarkable extremal properties. In particular, we use these polytopes in order to prove that the minimum numbers g_nfac(d,n) of facets and the minimum average degree g_avdeg(d,n) of the graph of a d-dimensional 0/1-polytope with n vertices satisfy g_nfac(d,n)?3d and g_avdeg(d,n)?d+4. We furthermore show that, despite the sparsity of their graphs, revlex-initial 0/1-polytopes satisfy a conjecture due to Mihail and Vazirani, claiming that the graphs of 0/1-polytopes have edge-expansion at least one.     

Results of Hurwitz type for three squares

We prove a large number of results in which the generating function of r₃(n), where r₃(n) is the number of representations of n as a sum of three squares, is, when n is restricted to an arithmetic sequence, a simple infinite product. We also conjecture a large number of further results of the same sort.     

On the Bateman-Horn Conjecture

Let r be a positive integer and f₁,…,f_r be distinct polynomials in Z[X]. If f₁(n),…,f_r(n) are all prime for infinitely many n, then it is necessary that the polynomials f_i are irreducible in Z[X], have positive leading coefficients, and no prime p divides all values of the product f₁(n)···f_r(n), as n runs over Z. Assuming these necessary conditions, Bateman and Horn (Math. Comput.16 (1962), 363-367) proposed a conjectural asymptotic estimate on the number of positive integers n?x such that f₁(n),…,f_r(n) are all primes. In the present paper, we apply the Hardy-Littlewood circle method to study the Bateman-Horn conjecture when r?2. We consider the Bateman-Horn conjecture for the polynomials in any partition {f₁,…,f_s}, {f_s+1,…,f_r} with a linear change of variables. Our main result is as follows: If the Bateman-Horn conjecture on such a partition and change of variables holds true with some conjectural error terms, then the Bateman-Horn conjecture for f₁,…,f_r is equivalent to a plausible error term conjecture for the minor arcs in the circle method.     

The existence of matrices with prescribed characteristic and permanental polynomials

Let d(λ) and p(λ) be monic polynomials of degree n?2 with coefficients in F, an algebraically closed field or the field of all real numbers. Necessary and sufficient conditions for the existence of an n-square matrix A over F such that det(λI?A)=d(λ) and per(λI?A=p(λ) are given in terms of the coefficients of d(λ) and p(λ).     

Tensor-Structured Preconditioners and Approximate Inverse of Elliptic Operators in ℝ d

In the present paper we analyze a class of tensor-structured preconditioners for the multidimensional second-order elliptic operators in ? ^d , d≥2. For equations in a bounded domain, the construction is based on the rank-R tensor-product approximation of the elliptic resolvent ? _R ≈(??λ I)^?1, where ? is the sum of univariate elliptic operators. We prove the explicit estimate on the tensor rank R that ensures the spectral equivalence. For equations in an unbounded domain, one can utilize the tensor-structured approximation of Green’s kernel for the shifted Laplacian in ? ^d , which is well developed in the case of nonoscillatory potentials. For the oscillating kernels e ^{?i κ‖x‖}/‖x‖, x∈? ^d , κ∈?₊, we give constructive proof of the rank-O(κ) separable approximation. This leads to the tensor representation for the discretized 3D Helmholtz kernel on an n×n×n grid that requires only O(κ?|log?ε|²? n) reals for storage. Such representations can be applied to both the 3D volume and boundary calculations with sublinear cost O(n ²), even in the case κ=O(n). Numerical illustrations demonstrate the efficiency of low tensor-rank approximation for Green’s kernels e ^?λ‖x‖/‖x‖, x∈?³, in the case of Newton (λ=0), Yukawa (λ∈?₊), and Helmholtz (λ=i κ,?κ∈?₊) potentials, as well as for the kernel functions 1/‖x‖ and 1/‖x‖ ^d?2, x∈? ^d , in higher dimensions d>3. We present numerical results on the iterative calculation of the minimal eigenvalue for the d-dimensional finite difference Laplacian by the power method with the rank truncation and based on the approximate inverse ? _R ≈(?Δ)^?1, with 3≤d≤50.     

On likelihood ratio ordering of parallel systems with exponential components

Let T(λ₁,...,λ _n ) be the lifetime of a parallel system consisting of exponential components with hazard rates λ₁,...,λ _n , respectively. For systems with only two components, Dykstra et. al. (1997) showed that if (λ₁, λ₂) majorizes (γ₁, γ₂), then, T(λ₁, λ₂) is larger than T(γ₁, γ₂) in likelihood ratio order. In this paper, we extend this theorem to general parallel systems. We introduce a new partial order, the so-called d-larger order, and show that if (λ₁,...,λ _n ) is d-larger than (γ₁,...,γ _n ), then T(λ₁,...,λ _n ) is larger than T(γ₁,...,γ _n ) in likelihood ratio order.     

Extremal results for odd cycles in sparse pseudorandom graphs

We consider extremal problems for subgraphs of pseudorandom graphs. For graphs F and Г the generalized Turán density π _F (Г) denotes the relative density of a maximum subgraph of Г, which contains no copy of F. Extending classical Turán type results for odd cycles, we show that π _F (Г)=1/2 provided F is an odd cycle and Г is a sufficiently pseudorandom graph. In particular, for (n,d,λ)-graphs Г, i.e., n-vertex, d-regular graphs with all non-trivial eigenvalues in the interval [?λ,λ], our result holds for odd cycles of length ?, provided $$\lambda ^{\ell - 2} \ll \frac{{d^{\ell - 1} }} {n}\log (n)^{ - (\ell - 2)(\ell - 3)} .$$ Up to the polylog-factor this verifies a conjecture of Krivelevich, Lee, and Sudakov. For triangles the condition is best possible and was proven previously by Sudakov, Szabó, and Vu, who addressed the case when F is a complete graph. A construction of Alon and Kahale (based on an earlier construction of Alon for triangle-free (n,d;λ)-graphs) shows that our assumption on Г is best possible up to the polylog-factor for every odd ?≥5.     

On the chromatic numbers of spheres in ℝ n

Let χ(S _r ^n?1 )) be the minimum number of colours needed to colour the points of a sphere S _r ^n?1 of radius $r \geqslant \tfrac{1} {2}$ in ? ⁿ so that any two points at the distance 1 apart receive different colours. In 1981 P. Erd?s conjectured that χ(S _r ^n?1 )→∞ for all $r \geqslant \tfrac{1} {2}$ . This conjecture was proved in 1983 by L. Lovász who showed in [11] that χ(S _r ^n?1 ) ≥ n. In the same paper, Lovász claimed that if $r < \sqrt {\frac{n} {{2n + 2}}}$ , then χ(S _r ^n?1 ) ≤ n+1, and he conjectured that χ(S _r ^n?1 ) grows exponentially, provided $r \geqslant \sqrt {\frac{n} {{2n + 2}}}$ . In this paper, we show that Lovász’ claim is wrong and his conjecture is true: actually we prove that the quantity χ(S _r ^n?1 ) grows exponentially for any $r > \tfrac{1} {2}$ .     

The error term in Nevanlinna’s inequality

An upper bound is given for the error termS(r, |a _j |,f) in Nevanlinna’s inequality. For given positive increasing functions p and $ with ∫ ₁ ^∞ dr/p(r) = ∫ ₁ ^∞ dr/r ?(r) = ∞, setP(r) = ∫ ₁ ^r dt/p,Ψ(r) = ∫ ₁ ^r dt/t ?(t) We prove that $$S(r, \left\{ {a_j } \right\}, f) \leqslant \log \frac{{T(r, f)\phi (T(r, f))}}{{p(r)}} + O(1)$$ holds, with a small exceptional set of r, for any finite set of points |a _j | in the extended plane and any meromorphic function f such thatΨ(T(r, f)) =O(P(r)). This improves the known results of A. Hinkkanen and Y. F. Wang. The sharpness of the estimate is also considered.     

Deflating quadratic matrix polynomials with structure preserving transformations

Given a pair of distinct eigenvalues (λ₁,λ₂) of an n×n quadratic matrix polynomial Q(λ) with nonsingular leading coefficient and their corresponding eigenvectors, we show how to transform Q(λ) into a quadratic of the form having the same eigenvalue s as Q(λ), with Q_d(λ) an (n-1)×(n-1) quadratic matrix polynomial and q(λ) a scalar quadratic polynomial with roots λ₁ and λ₂. This block diagonalization cannot be achieved by a similarity transformation applied directly to Q(λ) unless the eigenvectors corresponding to λ₁ and λ₂ are parallel. We identify conditions under which we can construct a family of 2n×2n elementary similarity transformations that (a) are rank-two modifications of the identity matrix, (b) act on linearizations of Q(λ), (c) preserve the block structure of a large class of block symmetric linearizations of Q(λ), thereby defining new quadratic matrix polynomials Q₁(λ) that have the same eigenvalue s as Q(λ), (d) yield quadratics Q₁(λ) with the property that their eigenvectors associated with λ₁ and λ₂ are parallel and hence can subsequently be deflated by a similarity applied directly to Q₁(λ). This is the first attempt at building elementary transformations that preserve the block structure of widely used linearizations and which have a specific action.     

Rings and semigroups with permutable zero products

We consider rings R, not necessarily with 1, for which there is a nontrivial permutation σ on n letters such that x₁?x_n=0 implies x_σ(1)?x_σ(n)=0 for all x₁,…,x_n∈R. We prove that this condition alone implies very strong permutability conditions for zero products with sufficiently many factors. To this end we study the infinite sequences of permutation groups P_n(R) consisting of those permutations σ on n letters for which the condition above is satisfied in R. We give the full characterization of such sequences both for rings and for semigroups with 0. This enables us to generalize some recent results by Cohn on reversible rings and by Lambek, Anderson and Camillo on rings and semigroups whose zero products commute. In particular, we prove that rings with permutable zero products satisfy the Köthe conjecture.     

Mono-multi bipartite Ramsey numbers, designs, and matrices

Eroh and Oellermann defined BRR(G₁,G₂) as the smallest N such that any edge coloring of the complete bipartite graph K_N,N contains either a monochromatic G₁ or a multicolored G₂. We restate the problem of determining BRR(K_1,λ,K_r,s) in matrix form and prove estimates and exact values for several choices of the parameters. Our general bound uses Füredi's result on fractional matchings of uniform hypergraphs and we show that it is sharp if certain block designs exist. We obtain two sharp results for the case r=s=2: we prove BRR(K_1,λ,K_2,2)=3λ-2 and that the smallest n for which any edge coloring of K_λ,n contains either a monochromatic K_1,λ or a multicolored K_2,2 is λ².     

Lower bounds for the clique and the chromatic numbers of a graph

G is any simple graph with m edges and n vertices where these vertices have vertex degrees d(1)≥d(2)≥?≥d(n), respectively. General algorithms for the exact calculation of χ(G), the chromatic number of G, are almost always of ‘branch and bound’ type; this type of algorithm requires an easily constructed lower bound for χ(G). In this paper it is shown that, for a number of such bounds (many of which are described here for the first time), the bound does not exceed cl(G) where cl(G) is the clique number of G.In 1972 Myers and Liu showed that cl(G)≥n?(n?2m?n). Here we show that cl(G)≥ n?[n?(2m?n)(1+c²_v)^{$\text{1}\text{2}$}], where c_v is the vertex degree coefficient of variation in G, that cl(G)≥ Bondy's constructive lower bound for χ(G), and that cl(G)≥n?(n?W(G)), where W(G) is the largest positive integer such that W(G)≤d(W(G)+1) [W(G)+1 is the Welsh and Powell upper bound for χ(G)]. It is also shown that cl(G)+$\text{1}\text{3}$>n?(n?L(G))≥n?(n?λ₁) and that χ(G)≥ n?(n?λ₁); λ₁ is the largest eigenvalue of A, the adjacency matrix of G, and L(G) is a newly defined single-valued function of G similar to W(G) in its construction from the vertex degree sequence of G [L(G)≥W(G)].Finally, a ‘greedy’ lower bound for cl(G) is constructed from A and it is shown that this lower bound is never less than Bondy's bound; thereafter, for 150 random graphs with varying numbers of vertices and edge densities, the values of lower bounds given in this paper are listed, thereby illustrating that this last greedily obtained lower bound is almost always better than each of the other bounds.     

Connected matroids with the smallest whitney numbers

In “The Slimmest Geometric Lattices” (Trans. Amer. Math. Soc.). Dowling and Wilson showed that if G is a combinatorial geometry of rank r(G) = n, and if _X(G) = Σμ(0, x)λ^{r ? r(x)} = Σ (?1)^{r ? k}W_kλ^k is the characteristic polynomial of G, then

$\text{w}{}_{\mathrm{k}}\text{?}\text{r}\text{k}\text{+n}\text{r?1}\text{k}$

Thus γ(G) ? 2^{r ? 1} (n+2), where γ(G) = Σw_k. In this paper we sharpen these lower bounds for connected geometries: If G is connected, r(G) ? 3, and n(G) ? 2 ((r, n) ≠ (4,3)), then

$\text{w}{}_{\mathrm{i}}\text{?}\text{r}\text{i}\text{+ n}\text{r}\text{i+1}\text{for i>1; w}{}_1\text{?r+n}\text{r}\text{2}\text{? 1;}$

|μ| ? (r? 1)n; and γ ? (2^{r ? 1} ? 1)(2n + 2). These bounds are all achieved for the parallel connection of an r-point circuit and an (n + 1)point line. If G is any series-parallel network, $\text{r(G) = r(}\text{G}\text{?}\text{) = 4}$, and $\text{n(G) = n(}\text{G}\text{?}\text{) = 3}$ then $\text{(w}{}_1\text{(G))}{}^4{}_{\mathrm{t-G}}\text{? (w}{}_1\text{(}\text{G}\text{?}\text{)) = (8, 20, 18, 7, 1)}$. Further, if β is the Crapo invariant,

$\text{β(G)=}\text{d}{}_{\mathrm{X}}\text{(G)}\text{dλ}\text{(1)}\text{,}$

then β(G) ? max(1, n ? r + 2). This lower bound is achieved by the parallel connection of a line and a maximal size series-parallel network.     

On the absolute continuity of Schrödinger operators with spherically symmetric,long-range potentials,II

Let H = ?Δ + V, where the potential V is spherically symmetric and can be decomposed as a sum of a short-range and a long-range term, V(r) = V_S(r) + V_L. Let λ = lim sup_r→∞V_L(r) < ∞ (we allow λ = ? ∞) and set λ⁺ = max(λ, 0). Assume that for some r₀, V_L(r) ?C^2k(r₀, ∞) and that there exists δ > 0 such that $\text{(}\text{d}\text{dr}\text{)}{}^{\mathrm{j}}\text{V}{}_{\mathrm{<mtext>L</mtext>}}\text{(r) · (λ}{}^{\mathrm{+}}\text{? V}{}_{\mathrm{<mtext>L</mtext>}}\text{(r) + 1)}{}^{\mathrm{?1}}\text{= O(r}{}^{\mathrm{?j\delta }}\text{), j = 1,…, 2k,}\text{as}\text{r → ∞}$. Assume further that $\text{∝}{}_1{}^{\mathrm{\infty }}\text{(}\text{dr}\text{¦ V}{}_{\mathrm{<mtext>L</mtext>}}\text{(r)¦}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{) = ∞}$ and that 2kδ > 1. It is shown that: (a) The restriction of H to C^∞(Rⁿ) is essentially self-adjoint, (b) The essential spectrum of H contains the closure of (λ, ∞). (c) The part of H over (λ, ∞) is absolutely continuous.     

A note on bideterminants for Schur superalgebras

Let S(m|n,r)_Z be a Z-form of a Schur superalgebra S(m|n,r) generated by elements ξ_i,j. We solve a problem of Muir and describe a Z-form of a simple S(m|n,r)-module D_λ,Q over the field Q of rational numbers, under the action of S(m|n,r)_Z. This Z-form is the Z-span of modified bideterminants [T_?:T_i] defined in this work. We also prove that each [T_?:T_i] is a Z-linear combination of modified bideterminants corresponding to (m|n)-semistandard tableaux T_i.     

Improvement on Brooks' chromatic bound for a class of graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and K_n+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K_1,3;K₅?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K₅?e can not be removed from the hypothesis. Moreover, for a graph G with none of K_1,3;K₅?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G).     

A bound for the number of tournaments with specified scores

Let $\text{T}$(R) denote the set of all tournaments with score vector R = (r₁, r₂,…, r_n). R. A. Brualdi and Li Qiao (“Proceedings of the Silver Jubilee Conference in Combinatorics at Waterloo,” in press) conjectured that if R is strong with r₁ ≤ r₂ ≤ … ≤ r_n, then |$\text{T}$(R)| ≥ 2^n?2 with equality if and only if R = (1, 1, 2,…, n ? 3, n ? 2, n ? 2). In this paper their conjecture is proved, and this result is used to establish a lower bound on the cardinality of $\text{T}$(R) for every R.     

On the supremum of some random Dirichlet polynomials

We study the average supremum of some random Dirichlet polynomials D _N (t) = Σ _n=1 ^N ? _n d(n)n ^?σ?it , where (? _n ) is a sequence of independent Rademacher random variables, the weights d(n) satisfy some reasonable conditions and 0 ≦ σ ≦ 1/2. We use an approach based on methods of stochastic processes, in particular the metric entropy method developed in [8].