排序方式: 共有14条查询结果,搜索用时 0 毫秒
11.
Julia Böttcher Yoshiharu Kohayakawa Aldo Procacci 《Random Structures and Algorithms》2012,40(4):425-436
Let G be a graph on n vertices with maximum degree Δ. We use the Lovász local lemma to show the following two results about colourings χ of the edges of the complete graph Kn. If for each vertex v of Kn the colouring χ assigns each colour to at most (n ‐ 2)/(22.4Δ2) edges emanating from v, then there is a copy of G in Kn which is properly edge‐coloured by χ. This improves on a result of Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409–433, 2003]. On the other hand, if χ assigns each colour to at most n/(51Δ2) edges of Kn, then there is a copy of G in Kn such that each edge of G receives a different colour from χ. This proves a conjecture of Frieze and Krivelevich [Electron. J. Comb. 15(1), R59, 2008]. Our proofs rely on a framework developed by Lu and Székely [Electron. J. Comb. 14(1), R63, 2007] for applying the local lemma to random injections. In order to improve the constants in our results we use a version of the local lemma due to Bissacot, Fernández, Procacci, and Scoppola [preprint, arXiv:0910.1824]. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 425–436, 2012 相似文献
12.
Markus Jalsenius 《Random Structures and Algorithms》2012,40(4):501-533
We show that the Glauber dynamics on proper 9‐colourings of the triangular lattice is rapidly mixing, which allows for efficient sampling. Consequently, there is a fully polynomial randomised approximation scheme (FPRAS) for counting proper 9‐colourings of the triangular lattice. Proper colourings correspond to configurations in the zero‐temperature anti‐ferromagnetic Potts model. We show that the spin system consisting of proper 9‐colourings of the triangular lattice has strong spatial mixing. This implies that there is a unique infinite‐volume Gibbs distribution, which is an important property studied in statistical physics. Our results build on previous work by Goldberg, Martin and Paterson, who showed similar results for 10 colours on the triangular lattice. Their work was preceded by Salas and Sokal's 11‐colour result. Both proofs rely on computational assistance, and so does our 9‐colour proof. We have used a randomised heuristic to guide us towards rigourous results. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 501–533, 2012 相似文献
13.
A weak k-colouring of an m-cycle system is a colouring of the vertices of the system with k colours in such a way that no cycle of the system has all of its vertices receive the same colour. An m-cycle system is said to be weakly k-chromatic if it has a weak k-colouring but no weak (k−1)-colouring. In this paper we show that for all k?2 and m?3 with (k,m)≠(2,3) there is a weakly k-chromatic m-cycle system of order v for all sufficiently large admissible v. 相似文献
14.
A generalization of the circular chromatic number to hypergraphs is discussed. In particular, it is indicated how the basic theory, and five equivalent formulations of the circular chromatic number of graphs, can be carried over to hypergraphs with essentially the same proofs. 相似文献