On small n-uniform hypergraphs with positive discrepancy

DOI10.1016/J.JCTB.2019.04.001MaRDI QIDQ2338645zbMATH OpenOpenAlexFDO

Authors Danila Cherkashin, F. V. Petrov

Publication date 21 November 2019

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

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

zbMATH Keywords

hypergraph coloringshypergraph discrepancyprescribed matrix determinant

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: A two-coloring of the vertices $V$ of the hypergraph $H=(V,E)$ by red and blue has discrepancy $d$ if $d$ is the largest difference between the number of red and blue points in any edge. Let $f(n)$ be the fewest number of edges in an $n$-uniform hypergraph without a coloring with discrepancy $0$. ErdH{o}s and S'os asked: is $f(n)$ unbounded? N. Alon, D. J. Kleitman, C. Pomerance, M. Saks and P. Seymour proved upper and lower bounds in terms of the smallest non-divisor ($mboxsnd$) of $n$. We refine the upper bound as follows: ${\displaystyle }$f (n) leq c log mbox{snd} {n}.${\displaystyle }$

Recommendations

• The smallest n-uniform hypergraph with positive discrepancy
• Discrepancy in graphs and hypergraphs
• Multi-color discrepancies
• scientific article; zbMATH DE number 15503
• scientific article; zbMATH DE number 2086378

Cites work

• A panorama of discrepancy theory
• Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
• Geometric discrepancy. An illustrated guide
• On two-colorings of hypergraphs
• The probabilistic method
• The smallest n-uniform hypergraph with positive discrepancy
• Upper bound in the Erdős-Hajnal problem of hypergraph coloring

Cited in

(17)

• The smallest n-uniform hypergraph with positive discrepancy
• Lower bounds on the clique-chromatic numbers of some distance graphs
• New lower bound for the minimal number of edges of simple uniform hypergraph without the property \(B_k\)
• The list-chromatic number of complete multipartite hypergraphs and multiple covers by independent sets
• New bounds on clique-chromatic numbers of Johnson graphs
• 2-colorings of hypergraphs with large girth
• New bounds for the clique-chromatic numbers of Johnson graphs
• On the independence numbers of distance graphs with vertices in \(\{-1, 0, 1\}^n\)
• Discrepancy of symmetric products of hypergraphs
• Discrepancy of random graphs and hypergraphs
• Partial Colorings of Unimodular Hypergraphs
• Discrepancy of products of hypergraphs
• scientific article; zbMATH DE number 881162 (Why is no real title available?)
• On non-adaptive majority problems of large query size
• Extremal problems in hypergraph colourings
• Discrepancy in graphs and hypergraphs
• Computational complexity of counting coincidences

This page was built for publication: On small \(n\)-uniform hypergraphs with positive discrepancy

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