Randomly colouring simple hypergraphs

Simple item page
dc.creatorFrieze, Alan
dc.creatorMelsted, Pall
dc.date2009-01-23
dc.date.accessioned2026-07-07T12:33:45Z
dc.date.available2026-07-07T12:33:45Z
dc.descriptionWe study the problem of constructing a (near) random proper $q$-colouring of a simple k-uniform hypergraph with n vertices and maximum degree Δ. (Proper in that no edge is mono-coloured and simple in that two edges have maximum intersection of size one). We give conditions on q,Δso that if these conditions are satisfied, Glauber dynamics will converge in O(n\log n) time from a random (improper) start. The interesting thing here is that for k\geq 3 we can take q=o(\D).
dc.identifierhttps://arxiv.org/abs/0901.3699
dc.identifierhttp://arxiv.org/abs/0901.3699
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/217237
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.subjectF.2.2
dc.titleRandomly colouring simple hypergraphs
dc.typetext

Files

Collections

arXiv