An asymptotic bound for the complexity of monotone graph properties

DOI10.1007/S00493-010-2485-3MaRDI QIDQ653841zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Torsten Korneffel, Eberhard Triesch

Publication date 19 December 2011

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-010-2485-3

zbMATH Keywords

simplicial complexprime number theoremcomplete bipartite graphasymptotic boundmonotone graph propertyevasiveness conjecturegroup of Oliver-typerecognition complexitytopological property

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Recommendations

• A lower bound for the complexity of monotone graph properties
• Evasiveness of graph properties and topological fixed-point theorems
• Decision tree complexity of graph properties with dimension at most 5
• A topological approach to evasiveness
• A lower bound for the recognition of digraph properties

Cites work

• scientific article; zbMATH DE number 3460321 (Why is no real title available?)
• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• A lower bound for the recognition of digraph properties
• A topological approach to evasiveness
• Evasiveness of subgraph containment and related properties
• Fixed-Point Theorems for Periodic Transformations
• Fixed-point sets of group actions on finite acyclic complexes
• Monotone Bipartite Graph Properties are Evasive
• On recognizing graph properties from adjacency matrices
• On the recognition complexity of some graph properties
• Some Results on Elusive Graph Properties

Cited in

(23)

• On the recognition complexity of some graph properties
• Graph properties in node-query setting: effect of breaking symmetry
• A topological approach to evasiveness
• An improved lower bound on the sensitivity complexity of graph properties
• Evasiveness of graph properties and topological fixed-point theorems
• The critical complexity of graph properties
• Evasiveness and the distribution of prime numbers
• Any monotone property of 3-uniform hypergraphs is weakly evasive
• scientific article; zbMATH DE number 168429 (Why is no real title available?)
• On the typical structure of graphs in a monotone property
• scientific article; zbMATH DE number 1754599 (Why is no real title available?)
• Monotone Bipartite Graph Properties are Evasive
• scientific article; zbMATH DE number 4003527 (Why is no real title available?)
• An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties
• scientific article; zbMATH DE number 1688357 (Why is no real title available?)
• Morse theory and evasiveness
• Complexity of edge monitoring on some graph classes
• A generalized model for understanding evasiveness
• Measures on monotone properties of graphs
• Monotone Properties of k -Uniform Hypergraphs Are Weakly Evasive
• Query complexity of tournament solutions
• A lower bound for the complexity of monotone graph properties
• Monotone properties of \(k\)-uniform hypergraphs are weakly evasive

This page was built for publication: An asymptotic bound for the complexity of monotone graph properties

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