共查询到20条相似文献，搜索用时 15 毫秒
1.
《Random Structures and Algorithms》2018,53(1):76-139
Given an integer k, we consider the parallel k‐stripping process applied to a hypergraph H: removing all vertices with degree less than k in each iteration until reaching the k‐core of H. Take H as : a random r‐uniform hypergraph on n vertices and m hyperedges with the uniform distribution. Fixing with , it has previously been proved that there is a constant such that for all m = cn with constant , with high probability, the parallel k‐stripping process takes iterations. In this paper, we investigate the critical case when . We show that the number of iterations that the process takes can go up to some power of n, as long as c approaches sufficiently fast. A second result we show involves the depth of a non‐k‐core vertex v: the minimum number of steps required to delete v from where in each step one vertex with degree less than k is removed. We will prove lower and upper bounds on the maximum depth over all non‐k‐core vertices. 相似文献
2.
Peter Allen Julia Böttcher Yoshiharu Kohayakawa Yury Person 《Random Structures and Algorithms》2015,46(3):446-465
We give an algorithmic proof for the existence of tight Hamilton cycles in a random r‐uniform hypergraph with edge probability for every . This partly answers a question of Dudek and Frieze (Random Struct Algor 42 (2013), 374–385), who used a second moment method to show that tight Hamilton cycles exist even for where arbitrary slowly, and for . The method we develop for proving our result applies to related problems as well. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 446–465, 2015 相似文献
3.
4.
We show that any k‐uniform hypergraph with n edges contains two isomorphic edge disjoint subgraphs of size for k = 4, 5 and 6. This is best possible up to a logarithmic factor due to an upper bound construction of Erd?s, Pach, and Pyber who show there exist k‐uniform hypergraphs with n edges and with no two edge disjoint isomorphic subgraphs with size larger than . Furthermore, our result extends results Erd?s, Pach and Pyber who also established the lower bound for k = 2 (eg. for graphs), and of Gould and Rödl who established the result for k = 3. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 767–793, 2016 相似文献
5.
We solve a problem proposed by Jacobson, Kézdy, and Lehel [4] concerning the existence of forbidden induced subgraph characterizations of line graphs of linear k-uniform hypergraphs with sufficiently large minimal edge-degree. Actually, we prove that for each k3 there is a finite set Z(k) of graphs such that each graph G with minimum edge-degree at least 2k2–3k+1 is the line graph of a linear k-uniform hypergraph if and only if G is a Z(k)-free graph.Acknowledgments. We thank the anonymous referees, whose suggestions helped to improve the presentation of the paper.Winter 2002/2003 DIMACS Award is gratefully acknowledged2000 Mathematics Subject Classification: 05C65 (05C75, 05C85) 相似文献
6.
Wiebke Bedenknecht Jie Han Yoshiharu Kohayakawa Guilherme O. Mota 《Random Structures and Algorithms》2019,55(4):795-807
For k ≥ 2 and r ≥ 1 such that k + r ≥ 4, we prove that, for any α > 0, there exists ε > 0 such that the union of an n‐vertex k‐graph with minimum codegree and a binomial random k‐graph with on the same vertex set contains the rth power of a tight Hamilton cycle with high probability. This result for r = 1 was first proved by McDowell and Mycroft. 相似文献
7.
8.
Pu Gao 《Random Structures and Algorithms》2015,47(2):341-360
In this paper, we show that in the random graph , with high probability, there exists an integer such that a subgraph of , whose vertex set differs from a densest subgraph of by vertices, is sandwiched by the and the ‐core, for almost all sufficiently large c. We determine the value of . We also prove that (a), the threshold of the k‐core being balanced coincides with the threshold that the average degree of the k‐core is at most , for all sufficiently large k; (b) with high probability, there is a subgraph of whose density is significantly denser than any of its nonempty cores, for almost all sufficiently large c > 0. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 341–360, 2015 相似文献
9.
In this paper we show that e/n is the sharp threshold for the existence of tight Hamilton cycles in random k ‐uniform hypergraphs, for all k ≥ 4. When k = 3 we show that 1/n is an asymptotic threshold. We also determine thresholds for the existence of other types of Hamilton cycles. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013 相似文献
10.
Peter Ayre Amin Coja‐Oghlan Catherine Greenhill 《Random Structures and Algorithms》2019,54(4):615-652
Improving a result of Dyer, Frieze and Greenhill [Journal of Combinatorial Theory, Series B, 2015], we determine the q‐colorability threshold in random k‐uniform hypergraphs up to an additive error of , where . The new lower bound on the threshold matches the “condensation phase transition” predicted by statistical physics considerations [Krzakala et al., PNAS 2007]. 相似文献
11.
For a pair of integers 1≤γ<r, the γ-chromatic number of an r-uniform hypergraph H=(V, E) is the minimal k, for which there exists a partition of V into subsets T1,…,Tk such that |e∩Ti|≤γ for every e∈E. In this paper we determine the asymptotic behavior of the γ-chromatic number of the random r-uniform hypergraph Hr(n, p) for all possible values of γ and for all values of p down to p=Θ(n−r+1). © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 381–403, 1998 相似文献
12.
Answering in a strong form a question posed by Bollobás and Scott, in this paper we determine the discrepancy between two random k‐uniform hypergraphs, up to a constant factor depending solely on k. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 47, 147–162, 2015 相似文献
13.
Bla Bollobs 《Random Structures and Algorithms》1990,1(1):95-104
In this article it is shown that for almost every random cube process the hitting time of a complete matching equals the hitting time of having minimal degree (at least) one and also the hitting time of connectedness. It follows from this that if t = (n + c + o(1))2n?2 for some constant c, then the probability that a random subgraph of the n-cube having precisely t edges has a complete matching tends to e. 相似文献
14.
Let H be a 3‐uniform hypergraph with n vertices. A tight Hamilton cycle C ? H is a collection of n edges for which there is an ordering of the vertices v1,…,vn such that every triple of consecutive vertices {vi,vi+1,vi+2} is an edge of C (indices are considered modulo n ). We develop new techniques which enable us to prove that under certain natural pseudo‐random conditions, almost all edges of H can be covered by edge‐disjoint tight Hamilton cycles, for n divisible by 4. Consequently, we derive the corollary that random 3‐uniform hypergraphs can be almost completely packed with tight Hamilton cycles whp, for n divisible by 4 and p not too small. Along the way, we develop a similar result for packing Hamilton cycles in pseudo‐random digraphs with even numbers of vertices. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011 相似文献
15.
16.
A triangle in a hypergraph is a collection of distinct vertices u, v, w and distinct edges e, f, g with , and . Johansson [Tech. report (1996)] proved that every triangle‐free graph with maximum degree Δ has list chromatic number . Frieze and Mubayi (Electron J Comb 15 (2008), 27) proved that every linear (meaning that every two edges share at most one vertex) triangle‐free triple system with maximum degree Δ has chromatic number . The restriction to linear triple systems was crucial to their proof. We provide a common generalization of both these results for rank 3 hypergraphs (edges have size 2 or 3). Our result removes the linear restriction from 8 , while reducing to the (best possible) result [Johansson, Tech. report (1996)] for graphs. In addition, our result provides a positive answer to a restricted version of a question of Ajtai Erd?s, Komlós, and Szemerédi (combinatorica 1 (1981), 313–317) concerning sparse 3‐uniform hypergraphs. As an application, we prove that if is the collection of 3‐uniform triangles, then the Ramsey number satisfies for some positive constants a and b. The upper bound makes progress towards the recent conjecture of Kostochka, Mubayi, and Verstraëte (J Comb Theory Ser A 120 (2013), 1491–1507) that where C3 is the linear triangle. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 487–519, 2015 相似文献
17.
Ali Pourmiri 《Random Structures and Algorithms》2016,49(1):185-208
The Push‐Pull protocol is a well‐studied round‐robin rumor spreading protocol defined as follows: initially a node knows a rumor and wants to spread it to all nodes in a network quickly. In each round, every informed node sends the rumor to a random neighbor, and every uninformed node contacts a random neighbor and gets the rumor from her if she knows it. We analyze the behavior of this protocol on random ‐trees, a class of power law graphs, which are small‐world and have large clustering coefficients, built as follows: initially we have a ‐clique. In every step a new node is born, a random ‐clique of the current graph is chosen, and the new node is joined to all nodes of the ‐clique. When is fixed, we show that if initially a random node is aware of the rumor, then with probability after rounds the rumor propagates to nodes, where is the number of nodes and is any slowly growing function. Since these graphs have polynomially small conductance, vertex expansion and constant treewidth, these results demonstrate that Push‐Pull can be efficient even on poorly connected networks. On the negative side, we prove that with probability the protocol needs at least rounds to inform all nodes. This exponential dichotomy between time required for informing almost all and all nodes is striking. Our main contribution is to present, for the first time, a natural class of random graphs in which such a phenomenon can be observed. Our technique for proving the upper bound successfully carries over to a closely related class of graphs, the random ‐Apollonian networks, for which we prove an upper bound of rounds for informing nodes with probability when is fixed. Here, © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 185–208, 2016 相似文献
18.
假设H和H（分别是具有h个顶点和n个顶点的r一致超图．我们称一个具有n/h个分支,且每个分支都同构于H的H的生成子图为H的一个H-因子．记α（H） = max{｜E′｜/｜V′｜-1 ｜},其中的最大值取遍H的所有满足｜V’｜〉1的子超图（V’,E′）．δ（H）表示超图H的最小度．在本文中,我们证明了如果δ（H）〈α（H）,那么P=p（n）=n-1／α（H）就是随机超图Hr（n,P）包含．H-因子的一个紧的门槛函数．也就是说,存在两个常数c和C使得对任意P=p（n）=cn-1／α（H）,几乎所有的随机超图Hr（n,P）都不包含一个H-因子,对任意P=p（n）=cn-1／α（H）,几乎所有的随机超图Hr（n,P）都包含一个H-因子． 相似文献
19.
Domingos Dellamonica Jr. Yoshiharu Kohayakawa Vojtěch Rödl Andrzej Ruciński 《Random Structures and Algorithms》2015,46(2):274-299
We give a polynomial time randomized algorithm that, on receiving as input a pair (H, G) of n‐vertex graphs, searches for an embedding of H into G. If H has bounded maximum degree and G is suitably dense and pseudorandom, then the algorithm succeeds with high probability. Our algorithm proves that, for every integer and a large enough constant C = Cd, as , asymptotically almost all graphs with n vertices and at least edges contain as subgraphs all graphs with n vertices and maximum degree at most d. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 2014 相似文献
20.
Amin Coja‐Oghlan Cristopher Moore Vishal Sanwalani 《Random Structures and Algorithms》2007,31(3):288-329