On small non-uniform hypergraphs without property B

2023/03/07 by Danila Cherkashin, Cherkashin, Danila
Computer Science · Engineering · Mathematics · #05C15 #05C65 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2303.03803

openalex publication_date 2023/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a given hypergraph H = (V,E) consider the sum q(H) of 2^-|e| over e ∈ E. Consider the class of hypergraphs with the smallest edge of size n and without a 2-colouring without monochromatic edges. Let q(n) be the smallest value of q(H) in this class. We provide a survey of the known bounds on q(n) and make some minor refinements.

Related

• Improved Lower Bounds for Property B
• On small n-uniform hypergraphs with positive discrepancy
• On some generalizations of the property B-problem of an n-uniform hypergraph
• A note on panchromatic colorings
• Coloring H-free Hypergraphs