排序方式: 共有31条查询结果,搜索用时 15 毫秒
1.
Denote by
the class of all triangle-free
graphs on n vertices and
m edges. Our main result is
the following sharp threshold, which answers the question for
which densities a typical triangle-free graph is bipartite. Fix
> 0 and let
. If
n/2 m (1 – ) t
3, then almost
all graphs in
are not bipartite, whereas if
m (1 + )t
3, then almost
all of them are bipartite. For m (1 + )t
3, this allows
us to determine asymptotically the number of graphs in
. We also obtain corresponding
results for C
-free graphs, for any
cycle C
of fixed odd length.
Forschergruppe Algorithmen, Struktur, Zufall
supported by Deutsche Forschungsgemeinschaft grant FOR
413/1-1 相似文献
2.
We say that a k-uniform hypergraph C is an ?-cycle if there exists a cyclic ordering of the vertices of C such that every edge of C consists of k consecutive vertices and such that every pair of consecutive edges (in the natural ordering of the edges) intersects in precisely ? vertices. We prove that if 1??<k and k−? does not divide k then any k-uniform hypergraph on n vertices with minimum degree at least contains a Hamilton ?-cycle. This confirms a conjecture of Hàn and Schacht. Together with results of Rödl, Ruciński and Szemerédi, our result asymptotically determines the minimum degree which forces an ?-cycle for any ? with 1??<k. 相似文献
3.
Given a graph H, a random maximal H‐free graph is constructed by the following random greedy process. First assign to each edge of the complete graph on n vertices a birthtime which is uniformly distributed in [0, 1]. At time p=0 start with the empty graph and increase p gradually. Each time a new edge is born, it is included in the graph if this does not create a copy of H. The question is then how many edges such a graph will have when p=1. Here we give asymptotically almost sure bounds on the number of edges if H is a strictly 2‐balanced graph, which includes the case when H is a complete graph or a cycle. Furthermore, we prove the existence of graphs with girth greater than 𝓁 and chromatic number n*y1/(𝓁‐1)+o(1), which improves on previous bounds for 𝓁>3. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 61–82, 2001 相似文献
4.
A long-standing conjecture of Kelly states that every regular tournament on n vertices can be decomposed into (n−1)/2 edge-disjoint Hamilton cycles. We prove this conjecture for large n. In fact, we prove a far more general result, based on our recent concept of robust expansion and a new method for decomposing graphs. We show that every sufficiently large regular digraph G on n vertices whose degree is linear in n and which is a robust outexpander has a decomposition into edge-disjoint Hamilton cycles. This enables us to obtain numerous further results, e.g. as a special case we confirm a conjecture of Erd?s on packing Hamilton cycles in random tournaments. As corollaries to the main result, we also obtain several results on packing Hamilton cycles in undirected graphs, giving e.g. the best known result on a conjecture of Nash-Williams. We also apply our result to solve a problem on the domination ratio of the Asymmetric Travelling Salesman problem, which was raised e.g. by Glover and Punnen as well as Alon, Gutin and Krivelevich. 相似文献
5.
We prove that any k-uniform hypergraph on n vertices with minimum degree at least contains a loose Hamilton cycle. The proof strategy is similar to that used by Kühn and Osthus for the 3-uniform case. Though some additional difficulties arise in the k-uniform case, our argument here is considerably simplified by applying the recent hypergraph blow-up lemma of Keevash. 相似文献
6.
Mader conjectured that for all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order . In this note, we observe that if the minimum outdegree of a digraph is sufficiently large compared to its order then one can even guarantee a subdivision of a large complete digraph. More precisely, let be a digraph of order n whose minimum outdegree is at least d. Then contains a subdivision of a complete digraph of order . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 1–6, 2008 相似文献
7.
Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let δ(H,n) denote the smallest integer k such that every graph G whose order n is divisible by |H| and with δ(G)≥k contains a perfect H-packing. We show that
.
The value of χ*(H) depends on the relative sizes of the colour classes in the optimal colourings of H and satisfies χ(H)−1<χ*(H)≤χ(H). 相似文献
8.
Deryk Osthus 《Journal of Combinatorial Theory, Series A》2000,90(2):336
We consider the random poset (n, p) which is generated by first selecting each subset of [n]={1, …, n} with probability p and then ordering the selected subsets by inclusion. We give asymptotic estimates of the size of the maximum antichain for arbitrary p=p(n). In particular, we prove that if pn/log n→∞, an analogue of Sperner's theorem holds: almost surely the maximum antichain is (to first order) no larger than the antichain which is obtained by selecting all elements of (n, p) with cardinality n/2. This is almost surely not the case if pn=∞. 相似文献
9.
We form the random poset 𝒫(n, p) by including each subset of [n]={1,…,n} with probability p and ordering the subsets by inclusion. We investigate the length of the longest chain contained in 𝒫(n, p). For p≥e/n we obtain the limit distribution of this random variable. For smaller p we give thresholds for the existence of chains which imply that almost surely the length of 𝒫(n, p) is asymptotically n(log n−log log 1/p)/log 1/p. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 177–194, 2000 相似文献
10.
Let denote the graph obtained from Kr by deleting one edge. We show that for every integer r≥4 there exists an integer n0=n0(r) such that every graph G whose order n≥n0 is divisible by r and whose minimum degree is at least contains a perfect -packing, i.e. a collection of disjoint copies of which covers all vertices of G. Here is the critical chromatic number of . The bound on the minimum degree is best possible and confirms a conjecture of Kawarabayashi for large n. 相似文献