Randomly coloring simple hypergraphs with fewer colors

被引：6

作者：

Frieze, Alan ^{[1
]}

Anastos, Michael ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

来源：

INFORMATION PROCESSING LETTERS | 2017年 / 126卷

关键词：

Analysis of algorithms; Markov Chain Monte Carolo; Hypergraph coloring; CONVEX-BODIES; ALGORITHM; VOLUME;

D O I：

10.1016/j.ipl.2017.06.005

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study the problem of constructing a (near) uniform random proper q-coloring of a simple k-uniform hypergraph with n vertices and maximum degree A. (Proper in that no edge is mono-colored and simple in that two edges have maximum intersection of size one.) We show that if q >= max {C-k logn, 500k(3)Delta(l/(k-1))} then the Glauber Dynamics will become close to uniform in 0 logn) time, given a random (improper) start. This improves on the results in Frieze and Melsted [5]. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：39 / 42

页数：4

共 15 条

[1]

Alon N., 2008, The Probabilistic Method

[2]

Brightwell GR, 2002, BOLYAI MATH STUD, V10, P247

[3]

Cousins B., 2015, BYPASSING KLS GAUSSI

[4] A RANDOM POLYNOMIAL-TIME ALGORITHM FOR APPROXIMATING THE VOLUME OF CONVEX-BODIES [J].