Improved algorithms for colorings of simple hypergraphs and applications

DOI10.1016/J.JCTB.2015.09.004zbMATH Open1327.05113arXiv1409.6921OpenAlexW1947129526MaRDI QIDQ896005FDOQ896005

D. A. Shabanov, Jakub Kozik

Publication date: 11 December 2015

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: The paper deals with extremal problems concerning colorings of hypergraphs. By using a random recoloring algorithm we show that any $n$-uniform simple (i.e. every two distinct edges share at most one vertex) hypergraph $H$ with maximum edge degree at most [ Delta(H)leq ccdot nr^{n-1}, ] is $r$-colorable, where $c>0$ is an absolute constant. %We prove also that similar result holds for $b$-simple hypergraphs. As an application of our proof technique we establish a new lower bound for Van der Waerden number $W(n,r)$, the minimum $N$ such that in any $r$-coloring of the set $1,\mathrm{...},N$ there exists a monochromatic arithmetic progression of length $n$. We show that [ W(n,r)>ccdot r^{n-1}, ] for some absolute constant $c>0$.

Full work available at URL: https://arxiv.org/abs/1409.6921

Recommendations

• Improved bounds and algorithms for hypergraph 2-coloring
• scientific article; zbMATH DE number 956855
• Extremal problems for colorings of simple hypergraphs and applications
• Randomized algorithms for colourings of hypergraphs
• Deterministic Hypergraph Coloring and Its Applications
• scientific article; zbMATH DE number 1301963
• Improved bounds on coloring of graphs
• Coloring mixed hypergraphs: theory, algorithms and applications
• scientific article; zbMATH DE number 25263

zbMATH Keywords

sparse hypergraphscolorings of hypergraphsrandom recoloring methodvan der Waerden number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cites Work

• Coloring uniform hypergraphs with few edges
• Constructions of sparse uniform hypergraphs with high chromatic number
• Title not available (Why is that?)
• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
• Coloring \(H\)-free hypergraphs
• Improved bounds and algorithms for hypergraph 2-coloring
• An application of Lovász' local lemma-A new lower bound for the van der Waerden number
• A note on random greedy coloring of uniform hypergraphs
• Multipass greedy coloring of simple uniform hypergraphs
• A Construction for Partitions Which Avoid Long Arithmetic Progressions
• Colourings of Uniform Hypergraphs with Large Girth and Applications
• On the chromatic number of set systems
• A remark concerning arithmetic progressions
• Random coloring method in the combinatorial problem of Erdős and Lovász

Cited In (14)

• Coloring hypergraphs with bounded cardinalities of edge intersections
• A new lower bound for van der Waerden numbers
• Colorings of \(b\)-simple hypergraphs
• Panchromatic 3-colorings of random hypergraphs
• 2-colorings of hypergraphs with large girth
• Extremal problems in hypergraph colourings
• Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings
• On some generalizations of the property B problem of an \(n\)-uniform hypergraph
• Random constructions of hypergraphs with large girth and without panchromatic colorings
• Equitable colorings of hypergraphs with few edges
• Monochromatic Hilbert cubes and arithmetic progressions
• On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• New lower bound for the minimal number of edges of simple uniform hypergraph without the property \(B_k\)

This page was built for publication: Improved algorithms for colorings of simple hypergraphs and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896005)