Resolvable and near-resolvable decompositions ofDK v into oriented 4-cycles

Summary A resolvableX-decomposition ofDK _v (the complete symmetric digraph onv vertices) is a partition of the arcs ofDK _v into isomorphic factors where each factor is a vertex-disjoint union of copies ofX and spans all vertices ofDK _v . There are four orientations ofC ₄ (the 4-cycle), only one of which has been considered: Bennett and Zhang, Aequationes Math.40 (1990), 248–260. We give necessary and sufficient conditions onv for resolvableX-decomposition ofDK _v , whereX is any one of the other three orientations ofC ₄. A near-resolvableX-decomposition ofDK _v is as above except that each factor spans all but one vertex ofDK _v . Again, one orientation ofC ₄ has been dealt with by Bennett and Zhang, and we provide necessary and sufficient conditions onv for the remaining three cases. The construction techniques used are both direct (for small values ofv) and recursive.The author thanks Simon Fraser University for its support during her graduate studies when the research for this paper was undertaken.The author acknowledges the Natural Sciences and Engineering Research Council of Canada for financial support under grant A-7829.     

A short zero-one law proof of a result of Abian

Summary In this note a new and very short zero-one law proof of the following theorem of Abian is presented. The subset of the unit interval [0, 1) consisting of those real numbers whose Hamel expansions do not use a given basis element of a prescribed Hamel basis, has outer Lebesgue measure one and inner measure zero.Let {a, b, c, ...} be a Hamel basis for the real numbers. LetA be the subset of the unit interval [0, 1) consisting of those real numbers whose Hamel expansions do not use the basis elementa. Sierpinski [4, p. 108] has shown thatA is nonmeasurable in the sense of Lebesgue. Abian [1] has improved Sierpinski's result by showing thatm* (A), the outer measure ofA, is one and thatm _* (A), the inner measure ofA, is zero. In this note a very short proof, using a zero-one law, of Abian's result will be presented.The following zero-one law is an immediate consequence of the Lebesgue Density Theorem [2, p. 290].     

The asymmetric leader election algorithm: Number of survivors near the end of the game

The following classical asymmetric leader election algorithm has obtained quite a bit of attention lately. Starting with n players, each one throws a coin, and the k of them which have each thrown a head (with probability q) go on, and the leader will be found amongst them, using the same strategy. Should nobody advance, the party will repeat the procedure. One of the most interesting parameter here is the number J (n) of rounds until a leader has been identified. In this paper we investigate, in the classical leader election algorithm, what happens near the end of the game, namely we fix an integer κ and we study the behaviour of the number of survivors L at level J (n) ? κ. In our asymptotic analysis (for n → ∞) we are focusing on the limiting distribution functions. We also investigate what happens, if the parameter p = 1 ? q gets small (p → 0) or large (p → 1). We use three e?cient tools: an urn model, a Mellin-Laplace technique for harmonic sums and some asymptotic distributions related to one of the extreme-value distributions: the Gumbel law. This study was motivated by a recent paper by Kalpathy, Mahmoud and Rosenkrantz, where they consider the number of survivors S_n,t, after t election rounds, in a broad class of fair leader election algorithms starting with n candidates.     

On the number of paths and cycles for almost all graphs and digraphs

In this paper it is deduced the number ofs-paths (s-cycles) havingk edges in common with a fixeds-path (s-cycle) of the complete graphK _n (orK* _n for directed graphs). It is also proved that the number of the common edges of twos-path (s-cycles) randomly chosen from the set ofs-paths (s-cycles) ofK _n (respectivelyK* _n ), are random variables, distributed asymptotically in accordance with the Poisson law whenever s/n exists, thus extending a result by Baróti. Some estimations of the numbers of paths and cycles for almost all graphs and digraphs are made by applying Chebyshev’s inequality.     

Angle orders,regular n-gon orders and the crossing number

A finite poset P(X,<) on a set X={ x ₁,...,x _m} is an angle order (regular n-gon order) if the elements of P(X,<) can be mapped into a family of angular regions on the plane (a family of regular polygons with n sides and having parallel sides) such that x _ij if and only if the angular region (regular n-gon) for x _i is contained in the region (regular n-gon) for x _j. In this paper we prove that there are partial orders of dimension 6 with 64 elements which are not angle orders. The smallest partial order previously known not to be an angle order has 198 elements and has dimension 7. We also prove that partial orders of dimension 3 are representable using equilateral triangles with the same orientation. This results does not generalizes to higher dimensions. We will prove that there is a partial order of dimension 4 with 14 elements which is not a regular n-gon order regardless of the value of n. Finally, we prove that partial orders of dimension 3 are regular n-gon orders for n3.This research was supported by the Natural Sciences and Engineering Research Council of Canada, grant numbers A0977 and A2415.     

Reductions of 3-connected graphs with minimum degree at least four

We show that if G is a 3-connected graph of minimum degree at least 4 and with |V (G)| ≥ 7 then one of the following is true: (1) G has an edge e such that G/e is a 3-connected graph of minimum degree at least 4; (2) G has two edges uv and xy with ux, vy, vx ∈ E(G) such that the graph G/uv/xy obtained by contraction of edges uv and xy in G is a 3-connected graph of minimum degree at least 4; (3) G has a vertex x with N(x) = {x₁, x₂, x₃, x₄} and x₁x₂, x₃x₄ ∈ E(G) such that the graph (G ? x)/x₁x₂/x₃x₄ obtained by contraction of edges x₁x₂ and x₃x₄ in G – x is a 3-connected graph of minimum degree at least 4.

Each of the three reductions is necessary: there exists an infinite family of 3- connected graphs of minimum degree not less than 4 such that only one of the three reductions may be performed for the members of the family and not the two other reductions.     

W v cycles in plane graphs

A cycle in a plane graphG is called aW _v cycle if it has a connected (or empty) intersection with each face of the graph. We show that if the minimum degree (G)3 thenG has aW _v cycle and the lengthw(G) of a longestW _v cycle is bounded by the number,f(G), of faces ofG. The classW of graphsG withw(G)=f(G) is completely characterized by an characterized by an inductive construction from two graphs, namelyK ₄ and a face merging of two copies ofK ₄ on one hand, and in terms involving Halin graphs and face merging on the other hand. Longest cycles in members ofW are investigated. The shortness coefficient ofW is proved to be between one-half and three-quarters inclusively.     

Steiner Numbers in Graphs

Abstract

The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence s_o(G),s₁ (G),…,8_p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized.     

Directional approximation of the jacobians in ROW-methods

In this paper a new technique for avoiding exact Jacobians in ROW methods is proposed. The Jacobiansf' _n are substituted by matricesA _n satisfying a directional consistency conditionA _n f _n =f' _n f _n +O(h). In contrast to generalW-methods this enables us to reduce the number of order conditions and we construct a 2-stage method of order 3 and families of imbedded 4-stage methods of order 4(3). The directional approximation of the Jacobians has been realized via rank-1 updating as known from quasi-Newton methods.     

Exponentially decaying boundary layers as limiting cases of families of algebraically decaying ones

The boundary value problem for the similar stream function f = f(η;λ) of the Cheng–Minkowycz free convection flow over a vertical plate with a power law temperature distribution T_w(x) = T_∞ + Ax^λ in a porous medium is revisited. It is shown that in the λ-range − 1/2 < λ < 0 , the well known exponentially decaying “first branch” solutions for the velocity and temperature fields are not some isolated solutions as one has believed until now, but limiting cases of families of algebraically decaying multiple solutions. For these multiple solutions well converging analytical series expressions are given. This result yields a bridging to the historical quarreling concerning the feasibility of exponentially and algebraically decaying boundary layers. Owing to a mathematical analogy, our results also hold for the similar boundary layer flows induced by continuous surfaces stretched in viscous fluids with power-law velocities u_w(x)∼ x^λ. (Received: June 7, 2005)     

A local limit theorem for random walks conditioned to stay positive

We consider a real random walk S_n=X₁+...+X_n attracted (without centering) to the normal law: this means that for a suitable norming sequence a_n we have the weak convergence S_n/a_n⇒ϕ(x)dx, ϕ(x) being the standard normal density. A local refinement of this convergence is provided by Gnedenko's and Stone's Local Limit Theorems, in the lattice and nonlattice case respectively. Now let denote the event (S₁>0,...,S_n>0) and let S_n⁺ denote the random variable S_n conditioned on : it is known that S_n⁺/a_n ↠ ϕ⁺(x) dx, where ϕ⁺(x):=x exp (−x²/2)1_(x≥0). What we establish in this paper is an equivalent of Gnedenko's and Stone's Local Limit Theorems for this weak convergence. We also consider the particular case when X₁ has an absolutely continuous law: in this case the uniform convergence of the density of S_n⁺/a_n towards ϕ⁺(x) holds under a standard additional hypothesis, in analogy to the classical case. We finally discuss an application of our main results to the asymptotic behavior of the joint renewal measure of the ladder variables process. Unlike the classical proofs of the LLT, we make no use of characteristic functions: our techniques are rather taken from the so–called Fluctuation Theory for random walks.     

Packing random intervals

Summary Letn random intervalsI ₁, ...,I _n be chosen by selecting endpoints independently from the uniform distribution on [0.1]. Apacking is a pairwise disjoint subset of the intervals; itswasted space is the Lebesgue measure of the points of [0,1] not covered by the packing. In any set of intervals the packing with least wasted space is computationally easy to find; but its expected wasted space in the random case is not obvious. We show that with high probability for largen, this best packing has wasted space . It turns out that if the endpoints 0 and 1 are identified, so that the problem is now one of packing random arcs in a unit-circumference circle, then optimal wasted space is reduced toO(1/n). Interestingly, there is a striking difference between thesizes of the best packings: about logn intervals in the unit interval case, but usually only one or two arcs in the circle case.     

Light paths with an odd number of vertices in large polyhedral maps

LetP _k be a path onk vertices. In this paper we prove that (1) every polyhedral map on the torus and the Klein bottle contains a pathP _k such that each of its vertices has degree 6k–2 ifk is odd,k3, (2) every large polyhedral map on any compact 2-manifoldM with Euler characteristic (M)<0 contains a pathP _k such that each of its vertices has degree 6k – 2 ifk is odd,k3, (3) moreover, these bounds are attained. Fork=1 ork even,k2, the bound is 6k which has been proved in our previous paper.     

On well-quasi-ordering-finite graphs by immersion

It has been conjectured by Nash-Williams that the class of all graphs is well-quasi-ordered under the quasi-order ≦ defined by immersion. Two partial results are proved which support this conjecture. (i) The class of finite simple graphsG with K _2,3 is well-quasi-ordered by ≦, (ii) it is shown that a class of finite graphs is well-quasi-ordered by ≦ provided that the blocks of its members satisfy certain restrictive conditions. (In particular, this second result implies that ≦ is a well-quasi-order on the class of graphs for which each block is either complete or a cycle.)     

ON 3-CHOOSABILITY OF PLANE GRAPHS WITHOUT 6-,7- AND 9-CYCLES

The choice number of a graph G,denoted by X1(G),is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper,it is showed that X1 (G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 7- and 9-cycles.     

Bivariate hermite interpolation and applications to Algebraic Geometry

Summary We try to solve the bivariate interpolation problem (1.3) for polynomials (1.1), whereS is a lower set of lattice points, and for theq-th interpolation knot,A _q is the set of orders of derivatives that appear in (1.3). The number of coefficients |S| is equal to the number of equations |A _q |. If this is possible for all knots in general position, the problem is almost always solvable (=a.a.s.). We seek to determine whether (1.3) is a.a.s. An algorithm is given which often gives a positive answer to this. It can be applied to the solution of a problem of Hirschowitz in Algebraic Geometry. We prove that for Hermite conditions (1.3) (when allA _q are lower triangles of orderp) andP is of total degreen, (1.3) is a.a.s. for allp=1, 2, 3 and alln, except for the two casesp=1,n=2 andp=1,n=4.Dedicated to R. S. Varga on the occasion of his sixtieth birthdayThis work has been partly supported by the Texas ARP and the Deutsche Forschungsgemeinschaft     

Applications of the zero–one law to problems connected with Cauchy's functional equation

Summary Marek Kuczma's book, entitled An Introduction To The Theory Of Functional Equations And Inequalities, mentions a certain setV ₀ in several places and presents references as to where this set is discussed in the literature. The main result of this paper is a proof of the fact that the setA _M (V ₀)={xV ₀ f(x)>M} is saturated non-measurable for each additive discontinuous functionf and each real numberM. Other results aboutV ₀ are also presented. Connections between measure and category are stressed. The main tool in our proofs is a certain so-called zero–one law and its topological analogue. In addition it is shown that the zero–one law is equivalent to Smital's lemma.     

含有快速增长非线性恢复力的梁方程的行波解

Abstract. On studying traveling waves on a nonlinearly suspended bridge,the following partial differential equation has been considered:     

The formal theory of Hopf algebras Part II: The case of Hopf algebras

Abstract

The category Hopf_R of Hopf algebras over a commutative unital ring R is analyzed with respect to its categorical properties. The main results are: (1) For every ring R the category Hopf_R is locally presentable, it is coreflective in the category of bialgebras over R, over every R-algebra there exists a cofree Hopf algebra. (2) If, in addition, R is absoluty flat, then Hopf_R is reflective in the category of bialgebras as well, and there exists a free Hopf algebra over every R-coalgebra. Similar results are obtained for relevant subcategories of Hopf_R. Moreover it is shown that, for every commutative unital ring R, the so-called “dual algebra functor” has a left adjoint and that, more generally, universal measuring coalgebras exist.     

The Typical Growth of the kth Excess in a Random Integer Partition

 For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η _k are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood of . Received February 6, 2001; in revised form February 25, 2002 Published online August 5, 2002