An asymptotic bound for the complexity of monotone graph properties
DOI10.1007/S00493-010-2485-3zbMATH Open1231.05222DBLPjournals/combinatorica/KorneffelT10OpenAlexW1983880126WikidataQ56701661 ScholiaQ56701661MaRDI QIDQ653841FDOQ653841
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
Recommendations
simplicial complexprime number theoremcomplete bipartite graphasymptotic boundmonotone graph propertyevasiveness conjecturegroup of Oliver-typerecognition complexitytopological property
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)
Cites Work
- Title not available (Why is that?)
- On recognizing graph properties from adjacency matrices
- Fixed-point sets of group actions on finite acyclic complexes
- A topological approach to evasiveness
- Title not available (Why is that?)
- On the recognition complexity of some graph properties
- Evasiveness of subgraph containment and related properties
- Monotone Bipartite Graph Properties are Evasive
- Some Results on Elusive Graph Properties
- Fixed-Point Theorems for Periodic Transformations
- A lower bound for the recognition of digraph properties
Cited In (23)
- Graph properties in node-query setting: effect of breaking symmetry
- On the recognition complexity of some graph properties
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the typical structure of graphs in a monotone property
- Monotone Bipartite Graph Properties are Evasive
- Title not available (Why is that?)
- Morse theory and evasiveness
- Title not available (Why is that?)
- An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties
- 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)
