Monotone Properties of k -Uniform Hypergraphs Are Weakly Evasive

DOI10.1145/3313908MaRDI QIDQ5205809zbMATH OpenOpenAlexFDO

Authors Timothy J. F. Black

Publication date 16 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3313908

zbMATH Keywords

evasiveness conjecturedecision-tree complexitymonotone hypergraph properties

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Hypergraphs (05C65) Group actions on combinatorial structures (05E18)

Recommendations

• Monotone properties of \(k\)-uniform hypergraphs are weakly evasive
• Any monotone property of 3-uniform hypergraphs is weakly evasive
• Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive
• Monotone Bipartite Graph Properties are Evasive
• On the monotonicity of (k;g,h)-graphs
• Cover \(k\)-uniform hypergraphs by monochromatic loose paths
• scientific article; zbMATH DE number 168429
• An asymptotic bound for the complexity of monotone graph properties
• A lower bound for the complexity of monotone graph properties
• On the typical structure of graphs in a monotone property

Cited in

(6)

• Evasiveness through a circuit lens (extended abstract)
• scientific article; zbMATH DE number 1880713 (Why is no real title available?)
• Any monotone property of 3-uniform hypergraphs is weakly evasive
• Monotone Bipartite Graph Properties are Evasive
• Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive
• Monotone properties of \(k\)-uniform hypergraphs are weakly evasive

This page was built for publication: Monotone Properties of k -Uniform Hypergraphs Are Weakly Evasive

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