共查询到20条相似文献,搜索用时 15 毫秒
1.
Daniela Kühn Richard Mycroft Deryk Osthus 《Journal of Combinatorial Theory, Series B》2011,101(6):415-447
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 Δ. 相似文献
2.
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. 相似文献
3.
Maria N. Prodromou 《Discrete and Computational Geometry》2007,38(4):641-650
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. 相似文献
4.
Xiaoyun Lu Da‐Wei Wang Gerard J. Chang In‐Jen Lin C. K. Wong 《Journal of Graph Theory》1999,30(3):167-176
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 相似文献
5.
Seymour Schuster 《Journal of Graph Theory》1983,7(2):203-208
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. 相似文献
6.
《Journal of Graph Theory》2018,89(3):304-326
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 P4 (the path on four vertices) similar statements hold. We establish some positive and negative results. 相似文献
7.
G. Lusztig 《Milan Journal of Mathematics》2008,76(1):125-134
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 相似文献
8.
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. 相似文献
9.
Lineability of sets of nowhere analytic functions 总被引:1,自引:0,他引:1
L. Bernal-Gonzlez 《Journal of Mathematical Analysis and Applications》2008,340(2):1284-1295
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)). 相似文献
10.
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 K5. This is a special case of a conjecture of P. Seymour, that every 5‐connected nonplanar graph contains a subdivision of K5. 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 K5 whose branch vertices are v and four neighbors of v. 相似文献
11.
Michael Paul 《Mathematische Nachrichten》1997,185(1):227-237
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 H0. The aim of the present paper is to construct an analogous decomposition without the assumption that H0 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. 相似文献
12.
Greg Aloupis Jean Cardinal S��bastien Collette Shinji Imahori Matias Korman Stefan Langerman Oded Schwartz Shakhar Smorodinsky Perouz Taslakian 《Graphs and Combinatorics》2011,27(3):327-339
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. 相似文献
13.
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. 相似文献
14.
Mohammed Guediri 《Mathematische Zeitschrift》2003,244(3):577-585
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 π1(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. 相似文献
15.
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 相似文献
16.
Peter Apostoli 《Mathematical Logic Quarterly》1996,42(1):175-190
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 ∪{Xi ≤ Xj : 0 ≤ i < j ≤ k} whenever it contains the subsets X0,…, Xk. 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. 相似文献
17.
Donald Cook 《manuscripta mathematica》1969,1(4):377-383
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. 相似文献
18.
The main purpose of this paper is to show that any embedding of K7 in three-dimensional euclidean space contains a knotted cycle. By a similar but simpler argument, it is also shown that any embedding of K6 contains a pair of disjoint cycles which are homologically linked. 相似文献
19.
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. 相似文献
20.
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. 相似文献