Partition of a directed bipartite graph into two directed cycles

Let D = (V₁, V₂; A) be a directed bipartite graph with |V₁| = |V₂| = n 2. Suppose that d_D(x) + d_D(y) 3n + 1 for all x ε V₁ and y ε V₂. Then D contains two vertex-disjoint directed cycles of lengths 2n₁ and 2n₂, respectively, for any positive integer partition n = n₁ + n₂. Moreover, the condition is sharp for even n and nearly sharp for odd n.     

Stability of Periodic Orbits and Return Trajectories of Continuous Multi-valued Maps on Intervals

Let I be a compact interval of real axis R, and(I, H) be the metric space of all nonempty closed subintervals of I with the Hausdorff metric H and f : I → I be a continuous multi-valued map. Assume that Pn =(x_0, x_1,..., xn) is a return tra jectory of f and that p ∈ [min Pn, max Pn] with p ∈ f(p). In this paper, we show that if there exist k(≥ 1) centripetal point pairs of f(relative to p)in {(x_i; x_i+1) : 0 ≤ i ≤ n-1} and n = sk + r(0 ≤ r ≤ k-1), then f has an R-periodic orbit, where R = s + 1 if s is even, and R = s if s is odd and r = 0, and R = s + 2 if s is odd and r 0. Besides,we also study stability of periodic orbits of continuous multi-valued maps from I to I.     

Decay of correlations for Fibonacci unimodal interval maps

We consider a class of generalized Fibonacci unimodal maps for which the central return times {s_n} satisfy that s_n = s_(n-1) +ks_(n-2) for some k ≥ 1. We show that such a unimodal map admits a unique absolutely continuous invariant probability with exactly stretched exponential decay of correlations if its critical order lies in(1, k+1).     

Shelah's pcf theory and its applications

This is a survey paper giving a self-contained account of Shelah's theory of the pcf function pcf(a)={cf(Πa/D, <_D):D is an ultrafilter on a}, where a is a set of regular cardinals such that |a|a). We also give several applications of the theory to cardinal arithmetic, the existence of Jonsson algebras, and partition calculus.     

An extremal problem on potentially Kr,s-graphic sequences

We consider a variation of a classical Turán-type extremal problem (F. Chung, R. Graham, Erd s on Graphs: His Legacy of Unsolved Problems, AK Peters Ltd., Wellesley, 1998, Chapter 3) as follows: Determine the smallest even integer σ(K_r,s,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(K_r,s,n) is potentially K_r,s-graphic, where K_r,s is a r×s complete bipartite graph, i.e., π has a realization G containing K_r,s as its subgraph. In this paper, we first give sufficient conditions for a graphic sequence being potentially K_r,s-graphic, and then we determine σ(K_r,r,n) for r=3,4.     

Orientations with single source and sink

Let G be a graph and s, t a pair of vertices of it. Linear time algorithms are formulated for finding orientations D of G such that D has a unique source s and sink t or D has unique vertices s and t of in and outdegree zero, respectively. The variation which requires D to be additionally acyclic is also considered. Necessary and sufficient conditions for the existence of the orientations are described.     

The polytope of degree sequences of hypergraphs

Let D_n(r) denote the convex hull of degree sequences of simple r-uniform hypergraphs on the vertex set {1,2,…,n}. The polytope D_n(2) is a well-studied object. Its extreme points are the threshold sequences (i.e., degree sequences of threshold graphs) and its facets are given by the Erdös–Gallai inequalities. In this paper we study the polytopes D_n(r) and obtain some partial information. Our approach also yields new, simple proofs of some basic results on D_n(2). Our main results concern the extreme points and facets of D_n(r). We characterize adjacency of extreme points of D_n(r) and, in the case r=2, determine the distance between two given vertices in the graph of D_n(2). We give a characterization of when a linear inequality determines a facet of D_n(r) and use it to bound the sizes of the coefficients appearing in the facet defining inequalities; give a new short proof for the facets of D_n(2); find an explicit family of Erdös–Gallai type facets of D_n(r); and describe a simple lifting procedure that produces a facet of D_n+1(r) from one of D_n(r).     

Enumeration of cubic Cayley graphs on dihedral groups

Let p be an odd prime, and D_2p =<a, b|a^p = b² = 1, bab = a^-1 the dihedral group of order 2p. In this paper, we completely classify the cubic Cayley graphs on D_2p up to isomorphism by means of spectral method. By the way, we show that two cubic Cayley graphs on D_2p are isomorphic if and only if they are cospectral. Moreover, we obtain the number of isomorphic classes of cubic Cayley graphs on D_2p by using Gauss' celebrated law of quadratic reciprocity.     

Circular permutation graph family with applications

In a circular permutation diagram, there are two sets of terminals on two concentric circles: C_in and C_out. Given a permutation Π = [π₁, π₂, …, π_n], terminal i on C_in and terminal π_i on C_out are connected by a wire. The intersection graph G_c of a circular permutation diagram D_c is called a circular permutation graph of a permutation Π corresponding to the diagram D_c. The set of all circular permutation graphs of a permutation Π is called the circular permutation graph family of permutation Π. In this paper, we propose the following: (1) an O(V + E) time algorithm to check if a labeled graph G = (V, E) is a labeled circular permutation graph. (2) An O(n log n + nt) time algorithm to find a maximum independent set of a family, where n = Π and t is the cardinality of the output. (Number t in the worst case is O(n). However, if Π is uniformly distributed (and independent from i), its expected value is O(√n).) (3) An O(min(δV_clog logV_c,V_clogV_c) + E_c) time algorithm for finding a maximum independent set of a circular permutation diagram D_c, where δ is the minimum degree of vertices in the intersection graph G_c = (V_c,E_c) of D_c. (4) An O(n log log n) time algorithm for finding a maximum clique and the chromatic number of a circular permutation diagram, where n is the number of wires in the diagram.     

Aspects of semiorders within interval orders

Let s_k(n) be the largest integer such that every n-point interval order with no antichain of more than k points includes an s_k(n)-point semiorder. When k = 1, s₁(n) = n since all interval orders with no two-point antichains are chains. Given (c₁,...,c₅) = (1, 2, 3, 4), it is shown that s₂(n) = c_n for n 4, s₃(n) = c_n for n 5, and for all positive n, s₂ (n+4) =s₂(n)+3, s₃(n+5) = s₃(n)+3. Hence s₂ has a repeating pattern of length 4 [1, 2, 3, 3; 4, 5, 6, 6; 7, 8, 9, 9;...], and s₃ has a repeating pattern of length 5 [1, 2, 3, 3, 4; 4, 5, 6, 6, 7; 7, 8, 9, 9, 10;...].

Let s(n) be the largest integer such that every n-point interval order includes an s(n)-point semiorder. It was proved previously that for even n from 4 to 14, and that s(17) = 9. We prove here that s(15) = s(16) = 9, so that s begins 1, 2, 3, 3, 4, 4,..., 8, 8, 9, 9, 9. Since s(n)/n→0, s cannot have a repeating pattern.     

Length-bounded disjoint paths in planar graphs

The following problem is considered: given: an undirected planar graph G=(V,E) embedded in , distinct pairs of vertices {r₁,s₁},…,{r_k,s_k} of G adjacent to the unbounded face, positive integers b₁,…,b_k and a function ; find: pairwise vertex-disjoint paths P₁,…,P_k such that for each i=1,…,k, P_i is a r_i−s_i-path and the sum of the l-length of all edges in P_i is at most b_i. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2.     

Graph spectra

The k-spectrum s_k(G) of a graph G is the set of all positive integers that occur as the size of an induced k-vertex subgraph of G. In this paper we determine the minimum order and size of a graph G with s_k (G) = {0, 1, …,(₂^k)} and consider the more general question of describing those sets S {0,1, … ,(₂^k)} such that S = s_k(G) for some graph G.     

Scheduling starting times for an active redundant system with non-identical lifetimes

Here we examine an active redundant system with scheduled starting times of the units. We assume availability of n non-identical, non-repairable units for replacement or support. The original unit starts its operation at time s₁ = 0 and each one of the (n − 1) standbys starts its operation at scheduled time s_i (i = 2, …, n) and works in parallel with those already introduced and not failed before s_i. The system is up at times s_i (i = 2, …, n), if and only if, there is at least one unit in operation. Thus, the system has the possibility to work with up to n units, in parallel structure. Unit-lifetimes T_i (i = 1, …, n) are independent with cdf F_i, respectively. The system has to operate without inspection for a fixed period of time c and it stops functioning when all available units fail before c. The probability that the system is functioning for the required period of time c depends on the distribution of the unit-lifetimes and on the scheduling of the starting times s_i. The reliability of the system is evaluated via a recursive relation as a function of the starting times s_i (i = 2, …, n). Maximizing with respect to the starting times we get the optimal ones. Analytical results are presented for some special distributions and moderate values of n.     

Almost resolvable maximum packings of complete graphs with 5-cycles

Let X be the vertex set of K_nA k-cycle packing of K_n is a triple (X,C,L), where C is a collection of edge disjoint k-cycles of K_n and L is the collection of edges of K_n not belonging to any of the k-cycles in C. A k-cycle packing (X,C,L) is called resolvable if C can be partitioned into almost parallel classes. A resolvable maximum k-cycle packing of K_n, denoted by k-RMCP(n), is a resolvable k-cycle packing of K_n, (X,C,L), in which the number of almost parallel classes is as large as possible. Let D(n, k) denote the number of almost parallel classes in a k-RMCP(n). D(n, k) for k = 3, 4 has been decided. When n ≡ k (mod 2k) and k ≡ 1 (mod 2) or n ≡ 1 (mod 2k) and k ∈{6, 8, 10, 14}∪{m: 5≤m≤49, m ≡ 1 (mod 2)}, D(n, k) also has been decided with few possible exceptions. In this paper, we shall decide D(n, 5) for all values of n≥5.     

Competitive on-line coverage of grid environments by a mobile robot

We describe in this paper two on-line algorithms for covering planar areas by a square-shaped tool attached to a mobile robot. Let D be the tool size. The algorithms, called Spanning Tree Covering (STC) algorithms, incrementally subdivide the planar area into a grid of D-size cells, while following a spanning tree of a grid graph whose nodes are 2D-size cells. The two STC algorithms cover general planar grids. The first, Spiral-STC, employs uniform weights on the grid-graph edges and generates spiral-like covering patterns. The second, Scan-STC, assigns lower weights to edges aligned with a particular direction and generates scan-like covering patterns along this direction. Both algorithms cover any planar grid using a path whose length is at most (n+m)D, where n is the total number of D-size cells and mn is the number of boundary cells, defined as cells that share at least one point with the grid boundary. We also demonstrate that any on-line coverage algorithm generates a covering path whose length is at least (2−)l_opt in worst case, where l_opt is the length of the optimal off-line covering path. Since (n+m)D2l_opt, the bound is tight and the STC algorithms are worst-case optimal. Moreover, in practical environments mn, and the STC algorithms generate close-to-optimal covering paths in such environments.     

3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects

We present a new data structure for a set of n convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) vertical ray shooting—preprocess a set of n non-intersecting convex simply-shaped flat objects in 3-space, whose xy-projections are fat, for efficient vertical ray shooting queries, (ii) point enclosure—preprocess a set C of n convex simply-shaped fat objects in the plane, so that the k objects containing a query point p can be reported efficiently, (iii) bounded-size range searching— preprocess a set C of n convex fat polygons, so that the k objects intersecting a “not-too-large” query polygon can be reported efficiently, and (iv) bounded-size segment shooting—preprocess a set C as in (iii), so that the first object (if exists) hit by a “not-too-long” oriented query segment can be found efficiently. For the first three problems we construct data structures of size O(λ_s(n)log³n), where s is the maximum number of intersections between the boundaries of the (xy-projections) of any pair of objects, and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequences. The data structure for the fourth problem is of size O(λ_s(n)log²n). The query time in the first problem is O(log⁴n), the query time in the second and third problems is O(log³n + klog²n), and the query time in the fourth problem is O(log³n).

We also present a simple algorithm for computing a depth order for a set as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for , if exists, is a linear order of , such that, if K₁, K₂ and K₁ lies vertically above K₂, then K₁ precedes K₂.) Unlike the algorithm of Agarwal et al. (1995) that might output a false order when a depth order does not exist, the new algorithm is able to determine whether such an order exists, and it is often more efficient in practical situations than the former algorithm.     

“Drawings since hit tables in lotteries” and a new multivariate geometric distribution

In number lotteries people choose r numbers out of s. Weekly published “drawings since hit tables” indicate how many drawings have taken place since each of the s numbers was last selected as a winning number. Among many lotto players, they enhance the widespread belief that numbers should be “due” if they have not come up for a long time. Under the assumptions of independence of the drawings and equiprobability of all possible combinations, the random s-vectors Y_n, n 1, of entries in a drawings since hit table after n drawings form a Markov chain. The limit distribution of Y_n as n → ∞ is a new multivariate generalization of the geometric distribution. The determination of the distribution of the maximum entry in a drawings since hit table within the first n draws of a lottery seems to be an open problem.     

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.     

Computing simple paths among obstacles

Given a set X of points in the plane, two distinguished points s,tX, and a set Φ of obstacles represented by line segments, we wish to compute a simple polygonal path from s to t that uses only points in X as vertices and avoids the obstacles in Φ. We present two results: (1) we show that finding such simple paths among arbitrary obstacles is NP-complete, and (2) we give a polynomial-time algorithm that computes simple paths when the obstacles form a simple polygon P and X is inside P. Our algorithm runs in time O(m²n²), where m is the number of vertices of P and n is the number of points in X.