On nearly regular co-critical graphs

A graph G is called (K₃, K₃)-co-critical if the edges of G can be coloured with two colours without getting a monochromatic triangle, but adding any new edge to the graph, this kind of ‘good’ colouring is impossible. In this short note we construct (K₃, K₃)-co-critical graphs of maximal degree O(n^3/4).     

Consequences of an algorithm for bridged graphs

Chepoi showed that every breadth first search of a bridged graph produces a cop-win ordering of the graph. We note here that Chepoi's proof gives a simple proof of the theorem that G is bridged if and only if G is cop-win and has no induced cycle of length four or five, and that this characterization together with Chepoi's proof reduces the time complexity of bridged graph recognition. Specifically, we show that bridged graph recognition is equivalent to (C₄,C₅)-free graph recognition, and reduce the best known time complexity from O(n⁴) to O(n^3.376).     

On the fourth power moment of Fourier coefficients of cusp form

Let a(n)be the Fourier coefficients of a holomorphic cusp form of weightκ=2n≥12 for the full modular group and A(x)=∑_(n≤x)a(n).In this paper,we establish an asymptotic formula of the fourth power moment of A(x)and prove that ∫T1A~4(x)dx=3/(64κπ~4)s_4;2()T~(2κ)+O(T~(2κ-δ_4+ε))with δ_4=1/8,which improves the previous result.     

Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs

We investigate the complexity of several domination problems on the complements of bounded tolerance graphs and the complements of trapezoid graphs. We describe an O(n² log⁵ n) time and O(n²) space algorithm to solve the domination problem on the complement of a bounded tolerance graph, given a square embedding of that graph. We also prove that domination, connected domination and total domination are all NP-complete on co-trapezoid graphs.     

Recognizing graphs without asteroidal triples

We consider the problem of recognizing AT-free graphs. Although there is a simple O(n³) algorithm, no faster method for solving this problem had been known. Here we give three different algorithms which have a better time complexity for graphs which are sparse or have a sparse complement; in particular we give algorithms which recognize AT-free graphs in , , and O(n^2.82+nm). In addition we give a new characterization of graphs with bounded asteroidal number by the help of the knotting graph, a combinatorial structure which was introduced by Gallai for considering comparability graphs.     

Dynamic motion planning in low obstacle density environments

A fundamental task for an autonomous robot is to plan its own motions. Exact approaches to the solution of this motion planning problem suffer from high worst-case running times. The weak and realistic low obstacle density (L.O.D.) assumption results in linear complexity in the number of obstacles of the free space (Van der Stappen et al., 1997). In this paper we address the dynamic version of the motion planning problem in which a robot moves among polygonal obstacles which move along polylines. The obstacles are assumed to move along constant complexity polylines, and to respect the low density property at any given time. We will show that in this situation a cell decomposition of the free space of size O(n²(n) log² n) can be computed in O(n²(n) log² n) time. The dynamic motion planning problem is then solved in O(n²(n) log³ n) time. We also show that these results are close to optimal.     

Unavoidable doubly connected large graphs

A connected graph is doubly connected if its complement is also connected. The following Ramsey-type theorem is proved in this paper. There exists a function h(n), defined on the set of integers exceeding three, such that every doubly connected graph on at least h(n) vertices must contain, as an induced subgraph, a doubly connected graph, which is either one of the following graphs or the complement of one of the following graphs:

(1) P_n, a path on n vertices;

(2) K_1,n^s, the graph obtained from K_1,n by subdividing an edge once;

(3) K_2,ne, the graph obtained from K_2,n by deleting an edge;

(4) K_2,n⁺, the graph obtained from K_2,n by adding an edge between the two degree-n vertices x₁ and x₂, and a pendent edge at each x_i.

Two applications of this result are also discussed in the paper.     

Full quadrature sums for pth powers of polynomials with Freud weights

In this paper, we provide a solution of the quadrature sum problem of R. Askey for a class of Freud weights. Let r> 0, b (− ∞, 2]. We establish a full quadrature sum estimate

1 p < ∞, for every polynomial P of degree at most n + rn^1/3, where W² is a Freud weight such as exp(−¦x¦), > 1, λ_jn are the Christoffel numbers, x_jn are the zeros of the orthonormal polynomials for the weight W², and C is independent of n and P. We also prove a generalisation, and that such an estimate is not possible for polynomials P of degree M = m(n) if m(n) = n + ξ_nn^1/3, where ξ_n → ∞ as n → ∞. Previous estimates could sum only over those x_jn with ¦x_jn¦ σx_1n, some fixed 0 < σ < 1.     

On embedding an outer-planar graph in a point set

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog³n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n²) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.     

Enumeration of irreducible binary words

Overlap free words over two letters are called irreducible binary words. Let d(n) denote the number of irreducible binary words of length n. In this paper we show that there are positive constants C₁ and C₂ such that C₁n^1.155<d(n)<C₂n^1.587 holds for all n>0.     

The existence of Schröder designs with equal-sized holes

A holey Schröder design of type h₁^n₁h₂^n₂ … h_k^n_k (HSD(h₁^n₁h₂^n₂ … h_k^n_k)) is equivalent to a frame idempotent Schröder quasigroup (FISQ(h₁^n₁h₂^n₂ … h_k^n_k)) of order n with n_i missing subquasigroups (holes) of order h_i, (1 i k), which are disjoint and spanning, that is, Σ_{1 i k} n_ih_i = n. In this paper, it is shown that an HSD(hⁿ) exists if and only if h²n(n − 1) 0 (mod 4) with expceptions (h, n) ε {{(1,5),(1,9),(2,4)}} and the possible exception of (h, n) = (6,4).     

Finite p-groups All of Whose Minimal Nonabelian Subgroups are Nonmetacyclic of Order p3

Assume p is an odd prime. We investigate finite p-groups all of whose minimal nonabelian subgroups are of order p³. Let P₁-groups denote the p-groups all of whose minimal nonabelian subgroups are nonmetacyclic of order p³. In this paper, the P₁-groups are classified, and as a by-product, we prove the Hughes' conjecture is true for the P₁-groups.     

On parallel rectilinear obstacle- avoiding paths

We give improved space and processor complexities for the problem of computing, in parallel, a data structure that supports queries about shortest rectilinear obstacle-avoiding paths in the plane, where the obstacles are disjoint rectangles. That is, a query specifies any source and destination in the plane, and the data structure enables efficient processing of the query. We now can build the data structure with O(n²/log n) CREW PRAM processors, as opposed to the previous O(n²), and with O(n²) space, as opposed to the previous O(n²(log n)²). The time complexity remains unchanged, at O((log n)²). As before, the data structure we compute enables a query to be processed in O(log n) time, by one processor for obtaining a path length, or by O(k/log n) processors for retrieving a shortest path itself, where k is the number of segments on that path. The new ideas that made our improvement possible include a new partitioning scheme of the recursion tree, which is used to schedule the computations performed on that tree. Since a number of other related shortest paths problems are solved using this technique as a subroutine our improvement translates into a similar improvement in the complexities of these problems as well.     

Coloring permutation graphs in parallel

A coloring of a graph G is an assignment of colors to its vertices so that no two adjacent vertices have the same color. We study the problem of coloring permutation graphs using certain properties of the lattice representation of a permutation and relationships between permutations, directed acyclic graphs and rooted trees having specific key properties. We propose an efficient parallel algorithm which colors an n-node permutation graph in O(log² n) time using O(n²/log n) processors on the CREW PRAM model. Specifically, given a permutation π we construct a tree T^*[π], which we call coloring-permutation tree, using certain combinatorial properties of π. We show that the problem of coloring a permutation graph is equivalent to finding vertex levels in the coloring-permutation tree.     

A new infinite series of regular uniformly geodetic code graphs

We construct vertex-transitive graphs Γ, regular of valency k=n²+n+1 on vertices, with integral spectrum, possessing a distinguished complete matching such that contracting the edges of this matching yields the Johnson graph J(2n, n) (of valency n²). These graphs are uniformly geodetic in the sense of Cook and Pryce (1983) (F-geodetic in the sense of Ceccharini and Sappa (1986)), i.e., the number of geodesics between any two vertices only depends on their distance (and equals 4 when this distance is two). They are counterexamples to Theorem 3.15.1 of [1], and we show that there are no other counterexamples.     

On the extreme eigenvalues of hermitian (block) toeplitz matrices

We are concerned with the behavior of the minimum (maximum) eigenvalue λ₀⁽ⁿ⁾ (λ_n⁽ⁿ⁾) of an (n + 1) × (n + 1) Hermitian Toeplitz matrix T_n(ƒ) where ƒ is an integrable real-valued function. Kac, Murdoch, and Szegö, Widom, Parter, and R. H. Chan obtained that λ₀⁽ⁿ⁾ — min ƒ = O(1/n^2k) in the case where ƒ C^2k, at least locally, and ƒ — inf ƒ has a zero of order 2k. We obtain the same result under the second hypothesis alone. Moreover we develop a new tool in order to estimate the extreme eigenvalues of the mentioned matrices, proving that the rate of convergence of λ₀⁽ⁿ⁾ to inf ƒ depends only on the order ρ (not necessarily even or integer or finite) of the zero of ƒ — inf ƒ. With the help of this tool, we derive an absolute lower bound for the minimal eigenvalues of Toeplitz matrices generated by nonnegative L¹ functions and also an upper bound for the associated Euclidean condition numbers. Finally, these results are extended to the case of Hermitian block Toeplitz matrices with Toeplitz blocks generated by a bivariate integrable function ƒ.     

Large 2P3-free graphs with bounded degree

Let ex^* (D;H) be the maximum number of edges in a connected graph with maximum degree D and no induced subgraph H; this is finite if and only if H is a disjoint union of paths. If the largest component of such an H has order m, then ex^*(D; H) = O(D²ex^*(D; P_m)). Constructively, ex^*(D;qP_m) = Θ(gD²ex^*(D;P_m)) if q>1 and m> 2(Θ(gD²) if m = 2). For H = 2P₃ (and D 8), the maximum number of edges is if D is even and

Full-size image

if D is odd, achieved by a unique extremal graph.     

First passage time for some stationary processes

For a 1-dependent stationary sequence {X_n} we first show that if u satisfies p₁=p₁(u)=P(X₁>u)0.025 and n>3 is such that 88np₁³1, then

P{max(X₁,…,X_n)u}=ν·μⁿ+O{p₁³(88n(1+124np₁³)+561)}, n>3,

where

ν=1−p₂+2p₃−3p₄+p₁²+6p₂²−6p₁p₂,μ=(1+p₁−p₂+p₃−p₄+2p₁²+3p₂²−5p₁p₂)⁻¹

with

p_k=p_k(u)=P{min(X₁,…,X_k)>u}, k1

and

|O(x)||x|.

From this result we deduce, for a stationary T-dependent process with a.s. continuous path {Y_s}, a similar, in terms of P{max_0skTY_s<u}, k=1,2 formula for P{max_0stY_su}, t>3T and apply this formula to the process Y_s=W(s+1)−W(s), s0, where {W(s)} is the Wiener process. We then obtain numerical estimations of the above probabilities.     

L2-approximation of real-valued functions with interpolatory constraints

We construct the polynomial p_m,n^* of degree m which interpolates a given real-valued function f L²[a, b] at pre-assigned n distinct nodes and is the best approximant to f in the L₂-sense over all polynomials of degree m with the same interpolatory character. It is shown that the L₂-error p_m,n^* − f → 0 as m → ∞ if f C[a, b].     

Minimal enclosing parallelepiped in 3D

We investigate the problem of finding a minimal volume parallelepiped enclosing a given set of n three-dimensional points. We give two mathematical properties of these parallelepipeds, from which we derive two algorithms of theoretical complexity O(n⁶). Experiments show that in practice our quickest algorithm runs in O(n²) (at least for n10⁵). We also present our application in structural biology.