An approximate version of Sumner?s universal tournament conjecture

Sumner?s universal tournament conjecture states that any tournament on 2n−2 vertices contains a copy of any directed tree on n vertices. We prove an asymptotic version of this conjecture, namely that any tournament on (2+o(1))n vertices contains a copy of any directed tree on n vertices. In addition, we prove an asymptotically best possible result for trees of bounded degree, namely that for any fixed Δ, any tournament on (1+o(1))n vertices contains a copy of any directed tree on n vertices with maximum degree at most Δ.     

Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge

Tutte proved that every 3‐connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth‐first‐search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3‐regular or if G does not contain two disjoint pairs of adjacent degree‐3 vertices.     

A Combinatorial Property of Points and Balls,a Colored Version

Any finite set X⊂ℝ ^d colored with colors, contains a rainbow subset Y⊂X, such that any ball that contains Y contains a positive fraction of the points of X. The bound on the number of colors is tight. This work was done while the author was visiting the Mathematical Sciences Research Institute, Berkeley. The author was supported by the UCL Graduate School Research Grant, #1.03/04.RP.EMB.     

On k‐ary spanning trees of tournaments

It is well known that every tournament contains a Hamiltonian path, which can be restated as that every tournament contains a unary spanning tree. The purpose of this article is to study the general problem of whether a tournament contains a k‐ary spanning tree. In particular, we prove that, for any fixed positive integer k, there exists a minimum number h(k) such that every tournament of order at least h(k) contains a k‐ary spanning tree. The existence of a Hamiltonian path for any tournament is the same as h(1) = 1. We then show that h(2) = 4 and h(3) = 8. The values of h(k) remain unknown for k ≥ 4. © 1999 John & Sons, Inc. J Graph Theory 30: 167–176, 1999     

Interpolation theorem for the number of end-vertices of spanning trees

The following interpolation theorem is proved: If a graph G contains spanning trees having exactly m and n end-vertices, with m < n, then for every integer k, m < k < n, G contains a spanning tree having exactly k end-vertices. This settles a problem posed by Chartrand at the Fourth International Conference on Graph Theory and Applications held in Kalamazoo, 1980.     

χ‐bounded families of oriented graphs

A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star S and integer k, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size k or it contains S as an induced subgraph. As an evidence, we prove that for any oriented star S, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order 3 or S as an induced subdigraph. We then study for which sets of orientations of P₄ (the path on four vertices) similar statements hold. We establish some positive and negative results.     

A Survey of Total Positivity

This paper contains an exposition of the classical work of Schoenberg and Gantmacher, Krein on the theory of totally positive matrices. It also contains a generalization of this theory to the Lie theoretic context and an application to the recent results of Fock and Goncharov on Teichmüller theory. Leonardo da Vinci lecture held on May 28, 2007 Received: June 2007     

Independence and graph homomorphisms graph homomorphisms

A graph with n vertices that contains no triangle and no 5-cycle and minimum degree exceeding n/4 contains an independent set with at least (3n)/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7-cycle and invoking the No Homomorphism Lemma. For k ≥ 4, a graph with n vertices, odd girth 2k+1, and minimum degree exceeding n/(k+1) contains an independent set with at least kn/(2k+1) vertices; however, we suspect this is not best possible. © 1993 John Wiley & Sons, Inc.     

Lineability of sets of nowhere analytic functions

Although the set of nowhere analytic functions on [0,1] is clearly not a linear space, we show that the family of such functions in the space of C^∞-smooth functions contains, except for zero, a dense linear submanifold. The result is even obtained for the smaller class of functions having Pringsheim singularities everywhere. Moreover, in spite of the fact that the space of differentiable functions on [0,1] contains no closed infinite-dimensional manifold in C([0,1]), we prove that the space of real C^∞-smooth functions on (0,1) does contain such a manifold in C((0,1)).     

Subdivisions of K5 in Graphs Embedded on Surfaces With Face‐Width at Least 5

We prove that if G is a 5‐connected graph embedded on a surface Σ (other than the sphere) with face‐width at least 5, then G contains a subdivision of K₅. This is a special case of a conjecture of P. Seymour, that every 5‐connected nonplanar graph contains a subdivision of K₅. Moreover, we prove that if G is 6‐connected and embedded with face‐width at least 5, then for every v ∈ V(G), G contains a subdivision of K₅ whose branch vertices are v and four neighbors of v.     

Decomposition of Completely Positive Maps

The paper is concerned with completely positive maps on the algebra of unbounded operatore L+(D) and on its completion L(D, D⁺). A decomposition theorem for continuous positive functionals is proved in [Tim. Loef.), and [Scholz 91] contains a generalization to maps into operator algebra on finite dimensional Hilbert spaces H₀. The aim of the present paper is to construct an analogous decomposition without the assumption that H₀ is finite dimensional. Moreover, the Kraus - theorem [Kraus] is proved for normal completely positive mappings on L(D, D⁺). The paper is organized as follows. Section 1 contains the necessary definitions and notations. In Section 2 we prove the decomposition theorem. Section 3 deal with the structure of the normal completely positive mappings.     

Colorful Strips

We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k − 1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4 ln k + ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that in dimension d the required coverage is at most d(k − 1) + 1. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast with the planar case, for which this decision problem is easy.     

Bipartite graphs with cycles of all even lengths

Let G = (X, Y, E) be a bipartite graph with X = Y = n. Chvátal gave a condition on the vertex degrees of X and Y which implies that G contains a Hamiltonian cycle. It is proved here that this condition also implies that G contains cycles of every even length when n > 3.     

On the existence of closed timelike geodesics in compact spacetimes. II

 The purpose of this paper is on the one hand to extend and generalize, in terms of Clifford translations, some results in a previous paper (Math. Z. 239 (2002), 277–291) concerning the existence of closed timelike geodesics in compact spacetimes, and on the other hand to prove that a compact flat spacetime (M, g) contains a closed timelike geodesic if and only if the fundamental group π₁(M) contains a non-trivial timelike translation. Received: 22 January 2002; in final form: 12 August 2002 / Published online: 16 May 2003 Mathematics Subject Classification (2000): 53C50, 53C22.     

Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture

We give a short constructive proof of a theorem of Fisher: every tournament contains a vertex whose second outneighborhood is as large as its first outneighborhood. Moreover, we exhibit two such vertices provided that the tournament has no dominated vertex. The proof makes use of median orders. A second application of median orders is that every tournament of order 2n − 2 contains every arborescence of order n > 1. This is a particular case of Sumner's conjecture: every tournament of order 2n − 2 contains every oriented tree of order n > 1. Using our method, we prove that every tournament of order (7n − 5)/2 contains every oriented tree of order n. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 244–256, 2000     

Modal Aggregation and the Theory of Paraconsistent Filters

This paper articulates the structure of a two species of weakly aggregative necessity in a common idiom, neighbourhood semantics, using the notion of a k-filter of propositions. A k-filter on a non-empty set I is a collection of subsets of I which (i) contains I, (ii) is closed under supersets on I, and (iii) contains ∪{X_i ≤ X_j : 0 ≤ i < j ≤ k} whenever it contains the subsets X₀,…, X_k. The mathematical content of the proof that weakly aggregative modal logic is complete relative to k-ary frame theory, the standard semantic idiom for weakly aggregative modal logic (see [1]) is presented in language-independent terms as a representation theorem for k-filters: every non-trivial k-filter is included in the union of ≤ k non-trivial filters. The elementary theory of k-filters is developed and then applied in the form of an ultrafilter extension result for k-ary frame theory. Mathematics Subject Classification: 03B45.     

Injectives of strongly hereditary relative homological algebras

IfR is a strongly hereditary relative homological algebra of Abelian groups which contains the torsion split sequences, then theR-injectives can be completely characterized. IfR is a relative homological algebra with enough projectives and enough injectives, which contains the torsiol split sequences, then equivalent conditions forR to be strongly hereditary are given.     

Knots and links in spatial graphs

The main purpose of this paper is to show that any embedding of K₇ in three-dimensional euclidean space contains a knotted cycle. By a similar but simpler argument, it is also shown that any embedding of K₆ contains a pair of disjoint cycles which are homologically linked.     

Turán-type results for partial orders and intersection graphs of convex sets

We prove Ramsey-type results for intersection graphs of geometric objects. In particular, we prove the following bounds, all of which are tight apart from the constant c. There is a constant c > 0 such that for every family F of n convex sets in the plane, the intersection graph of F or its complement contains a balanced complete bipartite graph of size at least cn. There is a constant c > 0 such that for every family F of n x-monotone curves in the plane, the intersection graph G of F contains a balanced complete bipartite graph of size at least cn/log n or the complement of G contains a balanced complete bipartite graph of size at least cn. Our bounds rely on new Turán-type results on incomparability graphs of partially ordered sets.     

Pasch trades with a negative block

A Steiner triple system of order v, STS(v), may be called equivalent to another STS(v) if one can be converted to the other by a sequence of three simple operations involving Pasch trades with a single negative block. It is conjectured that any two STS(v)s on the same base set are equivalent in this sense. We prove that the equivalence class containing a given system S on a base set V contains all the systems that can be obtained from S by any sequence of well over one hundred distinct trades, and that this equivalence class contains all isomorphic copies of S on V. We also show that there are trades which cannot be effected by means of Pasch trades with a single negative block.