A note on the axiomatisation of real numbers

Is it possible to give an abstract characterisation of constructive real numbers? A condition should be that all axioms are valid for Dedekind reals in any topos, or for constructive reals in Bishop mathematics. We present here a possible first‐order axiomatisation of real numbers, which becomes complete if one adds the law of excluded middle. As an application of the forcing relation defined in [3, 2], we give a proof that the formula which specifies the maximum function is not provable in this theory. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Strengthening Theorems of Dirac and Erdős on Disjoint Cycles

Let be an integer, be the set of vertices of degree at least 2k in a graph G , and be the set of vertices of degree at most in G . In 1963, Dirac and Erd?s proved that G contains k (vertex) disjoint cycles whenever . The main result of this article is that for , every graph G with containing at most t disjoint triangles and with contains k disjoint cycles. This yields that if and , then G contains k disjoint cycles. This generalizes the Corrádi–Hajnal Theorem, which states that every graph G with and contains k disjoint cycles.     

二部图中的独立6-圈

本文主要证明了对二部图G=(V_1,V_2,E),|V_1|=|V_2|=3k,其中k为正整数.若G的最小度至少为2k-1,则G至少包含k-1个独立6-圈.     

Disjoint Paths in Graphs III,Characterization

Let G be a graph, $ \{a, b, c\}\subseteq V(G) $, and $ \{a', b', c'\}\subseteq V(G) $ such that $ \{a, b, c\}\neq \{a', b', c'\} $. We say that $ (G, \{a, c\}, \{a', c'\}, (b, b')) $ is an obstruction if, for any three vertex disjoint paths from {a, b, c} to {a', b', c'} in G, one path is from b to b'. In this paper we characterize obstructions. As a consequence, we show that no obstruction can be 8-connected, unless b = b' or {a, c} = {a', c'}.AMS Subject Classification: 05C38.     

Short Disjoint Paths in Locally Connected Graphs

Chartrand and Pippert proved that a connected, locally k-connected graph is (k + 1)-connected. We investigate the lengths of k + 1 disjoint paths between two vertices in locally k-connected graphs with respect to several graph parameters, e.g. the k-diameter of a graph. We also give a generalization of the mentioned result. This research was partly done on a visit to the Institute of Systems Science of Academia Sinica (Beijing, China) under the project ME 418 of the Czech Ministery of Education. These authors are partly supported by the project LN00A056 of the Czech Ministery of Education.     

Cycle Transversals in Tournaments with Few Vertex Disjoint Cycles

We prove that every tournament T with no three disjoint cycles contains a set X of at most four vertices such that is acyclic.     

Heegaaed分解有不交曲线性质的一个充分条件

In the paper,we give two conditions that the Heegaard splitting admits the disjoint cnrve property.The main result is that for a genus g(g≥2)strongly irreducible Heegaard splitting(C1,C2;F),let Di be an essential disk in Ci,i=1,2,satisfying(1)at least one of (の)D4 and (の)D2 is separating in F and |(の)D1 (∩)(の)D2|≤ 2g-1;or(2)both (の)D1 and (の)D2 are non-separating in F and |(の)D1 (∩)(の)D2|≤ 2g-2,then(C1,C2;F)has the disjoint curve property.     

New Constructions of Disjoint Distinct Difference Sets

New constructions of regular disjoint distinct difference sets (DDDS) are presented. In particular, multiplicative and additive DDDS are considered.     

不交乘积和方法的并行化计算

本文探讨了不交积和方法的并行性提取问题，提出了不交乘积和方法并行计算的基本框架，实现了一种不交乘积和算法的并行化版本，测试结果显示，算法效率获得明显提高，加速比与并行节点数近乎线性关系。     

Maximally Disjoint Solutions of the Set Covering Problem

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP-complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, extensive computational tests are given demonstrating the nature of these algorithms. These tests are carried out both on randomly generated problems and on problems found in the literature.     

Disjoint perfect matchings in 3‐uniform hypergraphs

For a hypergraph H, let denote the minimum vertex degree in H. Kühn, Osthus, and Treglown proved that, for any sufficiently large integer n with , if H is a 3‐uniform hypergraph with order n and then H has a perfect matching, and this bound on is best possible. In this article, we show that under the same conditions, H contains at least pairwise disjoint perfect matchings, and this bound is sharp.     

Disjoint paths, planarizing cycles, and spanning walks

We study the existence of certain disjoint paths in planar graphs and generalize a theorem of Thomassen on planarizing cycles in surfaces. Results are used to prove that every 5-connected triangulation of a surface with sufficiently large representativity is hamiltonian, thus verifying a conjecture of Thomassen. We also obtain results about spanning walks in graphs embedded in a surface with large representativity.

     

Soft almost disjoint families

An almost disjoint family is said to be soft if there is an infinite set that meets each in a nonempty but finite set. We consider the associated cardinal invariant defined to be the minimal cardinality of an almost disjoint family that is not soft. We show that this cardinal coincides with J. Brendle's cardinal .

     

秩函数在研究独立空间拥有一对互斥基的特征上之作用

利用秩函数,本文给出如何判定一个独立空间拥有一对互斥基的一些充要条件.其目的是回答这样一个公开问题:在什么条件下,一个独立空间可以拥有一对互斥基.该问题是Welsh于1976年提出的.     

Disjoint 3‐Cycles in Tournaments: A Proof of The Bermond–Thomassen Conjecture for Tournaments

We prove that every tournament with minimum out‐degree at least contains k disjoint 3‐cycles. This provides additional support for the conjecture by Bermond and Thomassen that every digraph D of minimum out‐degree contains k vertex disjoint cycles. We also prove that for every , when k is large enough, every tournament with minimum out‐degree at least contains k disjoint cycles. The linear factor 1.5 is best possible as shown by the regular tournaments.     

Constructions of External Difference Families and Disjoint Difference Families

External difference families (EDFs) are a type of new combinatorial designs originated from cryptography. In this paper, some earlier ideas of recursive and cyclotomic constructions of combinatorial designs are extended, and a number of classes of EDFs and disjoint difference families are presented. A link between a subclass of EDFs and a special type of (almost) difference sets is set up.     

Riesz空间中的极大不相交系和表示理论

设Ｅ是阿基米德Ｒｉｅｓｚ空间，有弱单位元ｅ和极大不相交系｛ｅｉ：ｉ∈Ｉ｝，其中每一个ｅｉ都是投影元素．由ｅｉ生成的主带记为Ｂ（ｅｉ）．本文考虑如下论述：（ａ）存在完全正则Ｈａｕｓｄｏｒｆ空间Ｘ，使Ｅ是Ｒｉｅｓｚ同构于Ｃ（Ｘ）；（ｂ）对每一个ｉ∈Ｉ，存在一个完全正则Ｈａｕｓｄｏｒｆ空间Ｘｉ使Ｂ（ｅｉ）是Ｒｉｅｓｚ同构于Ｃ（Ｘｉ）．我们证明（ａ）可推出（ｂ）．但其逆在一般情况下不成立．当（ｂ）成立时，我们得到一些与（ａ）等价的论述．     

Disjoint Paths in Decomposable Digraphs

The k‐linkage problem is as follows: given a digraph and a collection of k terminal pairs such that all these vertices are distinct; decide whether D has a collection of vertex disjoint paths such that is from to for . A digraph is k‐linked if it has a k‐linkage for every choice of 2k distinct vertices and every choice of k pairs as above. The k‐linkage problem is NP‐complete already for [11] and there exists no function such that every ‐strong digraph has a k‐linkage for every choice of 2k distinct vertices of D [17]. Recently, Chudnovsky et al. [9] gave a polynomial algorithm for the k‐linkage problem for any fixed k in (a generalization of) semicomplete multipartite digraphs. In this article, we use their result as well as the classical polynomial algorithm for the case of acyclic digraphs by Fortune et al. [11] to develop polynomial algorithms for the k‐linkage problem in locally semicomplete digraphs and several classes of decomposable digraphs, including quasi‐transitive digraphs and directed cographs. We also prove that the necessary condition of being ‐strong is also sufficient for round‐decomposable digraphs to be k‐linked, obtaining thus a best possible bound that improves a previous one of . Finally we settle a conjecture from [3] by proving that every 5‐strong locally semicomplete digraph is 2‐linked. This bound is also best possible (already for tournaments) [1].