Superlinear Subset Partition Graphs With Dimension Reduction, Strong Adjacency, and Endpoint Count
| Autor: | Edward D. Kim, Tristram Bogart |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
021103 operations research Dimensionality reduction 010102 general mathematics 0211 other engineering and technologies Polytope 02 engineering and technology 01 natural sciences Upper and lower bounds Combinatorics Hirsch conjecture Computational Mathematics Discrete Mathematics and Combinatorics Partition (number theory) Adjacency list 0101 mathematics Mathematics |
| Zdroj: | Combinatorica. 38:75-114 |
| ISSN: | 1439-6912 0209-9683 |
| DOI: | 10.1007/s00493-016-3327-8 |
| Popis: | We construct a sequence of subset partition graphs satisfying the dimension reduction, adjacency, strong adjacency, and endpoint count properties whose diameter has a superlinear asymptotic lower bound. These abstractions of polytope graphs give further evidence against the Linear Hirsch Conjecture. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink