Improved algorithms for colorings of simple hypergraphs and applications

DOI10.1016/J.JCTB.2015.09.004MaRDI QIDQ896005zbMATH OpenOpenAlexFDO

Authors Jakub Kozik, D. A. Shabanov

Publication date 11 December 2015

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

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• A Construction for Partitions Which Avoid Long Arithmetic Progressions
• A note on random greedy coloring of uniform hypergraphs
• A remark concerning arithmetic progressions
• An application of Lovász' local lemma-A new lower bound for the van der Waerden number
• Coloring H-free hypergraphs
• Coloring uniform hypergraphs with few edges
• Colourings of uniform hypergraphs with large girth and applications
• Constructions of sparse uniform hypergraphs with high chromatic number
• Improved bounds and algorithms for hypergraph 2-coloring
• Multipass greedy coloring of simple uniform hypergraphs
• On the chromatic number of set systems
• Random coloring method in the combinatorial problem of Erdős and Lovász
• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems

Cited in

(18)

• Coloring hypergraphs with bounded cardinalities of edge intersections
• A new lower bound for van der Waerden numbers
• Multipass greedy coloring of simple uniform hypergraphs
• Colourings of uniform hypergraphs with large girth and applications
• 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
• Extremal problems for colorings of simple hypergraphs and applications
• 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
• Lower bounds for multicolor van der Waerden numbers
• 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)