General Lower Bounds for the Minor Crossing Number of Graphs

There are three general lower bound techniques for the crossing numbers of graphs: the Crossing Lemma, the bisection method and the embedding method. In this contribution, we present their adaptations to the minor crossing number. Using the adapted bounds, we improve on the known bounds on the minor crossing number of hypercubes. We also point out relations of the minor crossing number to string graphs and establish a lower bound for the standard crossing number in terms of Randič index.     

Random sequential bisection and its associated binary tree

Summary Random sequential bisection is a process to divide a given interval into two, four, eight, ... parts at random. Each division point is uniformly distributed on the interval and conditionally independent of the others. To study the asymptotic behavior of the lengths of subintervals in random seqential bisection, the associated binary tree is introduced. The number of internal or external nodes of the tree is asymptotically normal. The levels of the lowest and the highest external nodes are bounded with probability one or with probability increasing to one as the number of nodes increases to infinity. The associated binary tree is closely related to random binary tree which arises in computer algorithms, such as binary search tree and quicksort, and one-dimensional packing or the parking problem.     

A near equitable 2-person cake cutting algorithm

Let the cake be represented by the unit interval of reals, with two players having possibly different valuations. We propose a finite algorithm that produces contiguous pieces for both players such that their values differ by at most ?, where ??>?0 is a given small number. Players are not required to reveal their complete value functions, they only have to announce the bisection points of a sequence of intervals. If both utility functions are everywhere positive then the algorithm converges to the unique equitable point.     

Families of paths in the plane that connect all point pairs

A mesh is a family of paths in the plane connecting every pair of points. A crossing point of a mesh is a point which is an interior point to more than one path. A simple crossing point is an interior point of exactly two paths. We give an example of a mesh with only simple crossing points. We characterize subsets of the plane that can be the set of crossing points of a mesh. Our emphasis is on constructive methods.     

Defining continuity of real functions of real variables

Continuity of a real function of a real variable has been defined in various ways over almost 200 years. Contrary to popular belief, the definitions are not all equivalent, because their consequences for four somewhat pathological functions reveal five essentially different cases. The four defensible ones imply just two cases for continuity on an interval if that is defined by using pointwise continuity at each point. Some authors had trouble: two different textbooks each gave two arguably inconsistent definitions, three more changed their definitions in their second editions, two more claimed continuity at a point for functions not defined there, and one gave a definition implying it for a function with no limit there.     

A modified bisection algorithm for the determination of the eigenvalues of a symmetric tridiagonal matrix

Summary A modification to the well known bisection algorithm [1] when used to determine the eigenvalues of a real symmetric matrix is presented. In the new strategy the terms in the Sturm sequence are computed only as long as relevant information on the required eigenvalues is obtained. The resulting algorithm usingincomplete Sturm sequences can be shown to minimise the computational work required especially when only a few eigenvalues are required.The technique is also applicable to other computational methods which use the bisection process.     

On generalized bisection of -simplices

A generalized procedure of bisection of -simplices is introduced, where the bisection point can be an (almost) arbitrary point at one of the longest edges. It is shown that nested sequences of simplices generated by successive generalized bisection converge to a singleton, and an exact bound of the convergence speed in terms of diameter reduction is given. For regular simplices, which mark the worst case, the edge lengths of each worst and best simplex generated by successive bisection are given up to depth . For and , the sequence of worst case diameters is provided until it is halved.

     

最大割问题和最大平分割问题基于半定规划松弛的近似算法

考虑每条边具有非负权重的无向图, 最大割问题要求将顶点集划分为两个集合使得它们之间的边的权重之和最大. 当最大割问题半定规划松弛的最优解落到二维空间时, Goemans将近似比从0.87856...改进为0.88456. 依赖于半定规划松弛的目标值与总权和的比值的曲线, 此曲线的最低点为0.88456, 当半定规划松弛的目标值与总权和的比值在0.5到0.9044之间时, 利用Gegenbauer多项式舍入技巧, 改进了Zwick的近似比曲线. 进一步, 考虑最大割问题的重要变形------最大平分割问题, 在此问题中增加了划分的两部分的点数相等的要求. 同样考虑了最大平分割问题半定规划松弛的最优解落到二维空间的情形, 并利用前述的Gegenbauer多项式舍入技巧得到0.7091-近似算法.     

实C~*-代数中*运算的唯一性

本文指出：如果有两个*运算使得同一个实Banach代数均成为实C*-代数,则这两个*运算必然是相同的,即实C*-代数中*运算是唯一的．     

Integral invariants and limit sets of planar vector fields

We show that if a planar system of differential equations admits an inverse integrating factor V defined in a neighborhood of a singular point with exactly one zero eigenvalue then V vanishes along any separatrix of the singular point. Additionally we prove that if K is a compact α- or ω-limit set that contains a regular point (or has an elliptic or parabolic sector if not), and if V is defined on a neighborhood of K, then V vanishes at at least one point of K (and on all of K if V is real analytic or Morse).     

Properties of triangulations obtained by the longest-edge bisection

The Longest-Edge (LE) bisection of a triangle is obtained by joining the midpoint of its longest edge with the opposite vertex. Here two properties of the longest-edge bisection scheme for triangles are proved. For any triangle, the number of distinct triangles (up to similarity) generated by longest-edge bisection is finite. In addition, if LE-bisection is iteratively applied to an initial triangle, then minimum angle of the resulting triangles is greater or equal than a half of the minimum angle of the initial angle. The novelty of the proofs is the use of an hyperbolic metric in a shape space for triangles.     

A lambda-dendroid with two shore points whose union is not a shore set

A subset of a given continuum is called a shore set if there is a sequence of continua in the complement of this set converging to the whole continuum with respect to the Hausdorff metric. A point is called a shore point if the one point set containing this point is a shore set. We present several examples of a lambda-dendroid which contains two disjoint shore continua whose union is not a shore set. This answers a question of Van C. Nall in negative.     

Specker sequences revisited

Specker sequences are constructive, increasing, bounded sequences of rationals that do not converge to any constructive real. A sequence is said to be a strong Specker sequence if it is Specker and eventually bounded away from every constructive real. Within Bishop's constructive mathematics we investigate non‐decreasing, bounded sequences of rationals that eventually avoid sets that are unions of (countable) sequences of intervals with rational endpoints. This yields surprisingly straightforward proofs of certain basic results fromconstructive mathematics. Within Russian constructivism, we show how to use this general method to generate Specker sequences. Furthermore, we show that any nonvoid subset of the constructive reals that has no isolated points contains a strictly increasing sequence that is eventually bounded away from every constructive real. If every neighborhood of every point in the subset contains a rational number different from that point, the subset contains a strong Specker sequence. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Bounds for rectilinear crossing numbers

A rectilinear drawing of a graph is one where each edge is drawn as a straight-line segment, and the rectilinear crossing number of a graph is the minimum number of crossings over all rectilinear drawings. We describe, for every integer k ≥ 4, a class of graphs of crossing number k, but unbounded rectilinear crossing number. This is best possible since the rectilinear crossing number is equal to the crossing number whenever the latter is at most 3. Further, if we consider drawings where each edge is drawn as a polygonal line segment with at most one break point, then the resulting crossing number is at most quadratic in the regular crossing number. © 1993 John Wiley & Sons, Inc.     

Linear Arboricity of NIC-Planar Graphs

Acta Mathematicae Applicatae Sinica, English Series - A graph is NIC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share at...     

Ordered thinnings of point processes and random measures

This is a study of thinnings of point processes and random measures on the real line that satisfy a weak law of large numbers. The thinning procedures have dependencies based on the order of the points or masses being thinned such that the thinned process is a composition of two random measures. It is shown that the thinned process (normalized by a certain function) converges in distribution if and only if the thinning process does. This result is used to characterize the convergence of thinned processes to infinitely divisible processes, such as a compound Poisson process, when the thinning is independent and nonhomogeneous, stationary, Markovian, or regenerative. Thinning by a sequence of independent identically distributed operations is also discussed. The results here contain Renyi's classical thinning theorem and many of its extensions.     

Two maps on one surface

Two embeddings of a graph in a surface S are said to be “equivalent” if they are identical under an homeomorphism of S that is orientation‐preserving for orientable S. Two graphs cellularly embedded simultaneously in S are said to be “jointly embedded” if the only points of intersection involve an edge of one graph transversally crossing an edge of the other. The problem is to find equivalent embeddings of the two graphs that minimize the number of these edge‐crossings; this minimum we call the “joint crossing number” of the two graphs. In this paper, we calculate the exact value for the joint crossing number for two graphs simultaneously embedded in the projective plane. Furthermore, we give upper and lower bounds when the surface is the torus, which in many cases give an exact answer. In particular, we give a construction for re‐embedding (equivalently) the graphs in the torus so that the number of crossings is best possible up to a constant factor. Finally, we show that if one of the embeddings is replaced by its “mirror image,” then the joint crossing number can decrease, but not by more than 6.066%. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 198–216, 2001     

Weakly Computable Real Numbers

A real number x is recursively approximable if it is a limit of a computable sequence of rational numbers. If, moreover, the sequence is increasing (decreasing or simply monotonic), then x is called left computable (right computable or semi-computable). x is called weakly computable if it is a difference of two left computable real numbers. We show that a real number is weakly computable if and only if there is a computable sequence (x_s)_s of rational numbers which converges to x weakly effectively, namely the sum of jumps of the sequence is bounded. It is also shown that the class of weakly computable real numbers extends properly the class of semi-computable real numbers and the class of recursively approximable real numbers extends properly the class of weakly computable real numbers.     

On some continuity and differentiability properties of paths of Gaussian processes

The following path properties of real separable Gaussian processes ξ with parameter set an arbitrary interval are established. At every fixed point the paths of ξ are continuous, or differentiable, with probability zero or one. If ξ is measurable, then with probability one its paths have essentially the same points of continuity and differentiability. If ξ is measurable and not mean square continuous or differentiable at every point, then with probability one its paths are almost nowhere continuous or differentiable, respectively. If ξ harmonizable or if it is mean square continuous with stationary increments, then its paths are absolutely continuous with probability one if and only if ξ is mean square differentiable; also mean square differentiability of ξ implies path differentiability with probability one at every fixed point. If ξ is mean square differentiable and stationary, then on every interval with probability one its paths are either differentiable everywhere or nondifferentiable on countable dense subsets. Also a class of harmonizable processes is determined for which of the following are true: (i) with probability one paths are either continuous or unbounded on every interval, and (ii) mean square differentiability implies that with probability one on every interval paths are either differentiable everywhere or nondifferentiable on countable dense subsets.     

Reconfiguring closed polygonal chains in Euclideand-space

Consider the problem of moving a closed chain ofn links in two or more dimensions from one given configuration to another. The links have fixed lengths and may rotate about their endpoints, possibly passing through one another. The notion of a “line-tracking motion” is defined, and it is shown that when reconfiguration is possible by any means, it can be achieved byO(n) line-tracking motions. These motions can be computed inO(n) time on real RAM. It is shown that in three or more dimensions, reconfiguration is always possible, but that in dimension two this is not the case. Reconfiguration is shown to be always possible in two dimensions if and only if the sum of the lengths of the second and third longest links add to at most the sum of the lengths of the remaining links. AnO(n) algorithm is given for determining whether it is possible to move between two given configurations of a closed chain in the plane and, if it is possible, for computing a sequence of line-tracking motions to carry out the reconfiguration. The research of the second author was partially supported by an NSERC operating grant.