View in EDS HTML Full Text PDF Full Text

On the Circuit Diameter Conjecture.

Saved in:
Bibliographic Details
Title: On the Circuit Diameter Conjecture.
Authors: Borgwardt, Steffen1 steffen.borgwardt@ucdenver.edu, Stephen, Tamon2 tamon@sfu.ca, Yusun, Timothy2 tyusun@sfu.ca
Source: Discrete & Computational Geometry. Oct2018, Vol. 60 Issue 3, p558-587. 30p.
Subjects: Polyhedra, Polyhedra models, Geometric modeling, Geometric surfaces, Diameter
Abstract: From the point of view of optimization, a critical issue is relating the combinatorial diameter of a polyhedron to its number of facets f and dimension d. In the seminal paper of Klee and Walkup (Acta Math 117:53-78, 1967), the Hirsch conjecture of an upper bound of f-d was shown to be equivalent to several seemingly simpler statements, and was disproved for unbounded polyhedra through the construction of a particular 4-dimensional polyhedron U4 with eight facets. The Hirsch bound for bounded polyhedra was only recently disproved by Santos (Ann Math 176(1):383-412, 2012). We consider analogous properties for a variant of the combinatorial diameter called the circuit diameter. In this variant, the walks are built from the circuit directions of the polyhedron, which are the minimal non-trivial solutions to the system defining the polyhedron. We are able to prove that circuit variants of the so-called non-revisiting conjecture and d-step conjecture both imply the circuit analogue of the Hirsch conjecture. For the equivalences in Klee and Walkup, the wedge construction was a fundamental proof technique. We exhibit why it is not available in the circuit setting, and what are the implications of losing it as a tool. Further, we show the circuit analogue of the non-revisiting conjecture implies a linear bound on the circuit diameter of all unbounded polyhedra—in contrast to what is known for the combinatorial diameter. Finally, we give two proofs of a circuit version of the 4-step conjecture. These results offer some hope that the circuit version of the Hirsch conjecture may hold, even for unbounded polyhedra. A challenge in the circuit setting is that different realizations of polyhedra with the same combinatorial structure may have different diameters. We adapt the notion of simplicity to work with circuits in the form of C-simple and wedge-simple polyhedra. We show that it suffices to consider such polyhedra for studying circuit analogues of the Hirsch conjecture. [ABSTRACT FROM AUTHOR]
Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 131498427
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On the Circuit Diameter Conjecture.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Borgwardt%2C+Steffen%22">Borgwardt, Steffen</searchLink><relatesTo>1</relatesTo><i> steffen.borgwardt@ucdenver.edu</i><br /><searchLink fieldCode="AR" term="%22Stephen%2C+Tamon%22">Stephen, Tamon</searchLink><relatesTo>2</relatesTo><i> tamon@sfu.ca</i><br /><searchLink fieldCode="AR" term="%22Yusun%2C+Timothy%22">Yusun, Timothy</searchLink><relatesTo>2</relatesTo><i> tyusun@sfu.ca</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+%26+Computational+Geometry%22">Discrete & Computational Geometry</searchLink>. Oct2018, Vol. 60 Issue 3, p558-587. 30p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Polyhedra%22">Polyhedra</searchLink><br /><searchLink fieldCode="DE" term="%22Polyhedra+models%22">Polyhedra models</searchLink><br /><searchLink fieldCode="DE" term="%22Geometric+modeling%22">Geometric modeling</searchLink><br /><searchLink fieldCode="DE" term="%22Geometric+surfaces%22">Geometric surfaces</searchLink><br /><searchLink fieldCode="DE" term="%22Diameter%22">Diameter</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: From the point of view of optimization, a critical issue is relating the combinatorial diameter of a polyhedron to its number of facets f and dimension d. In the seminal paper of Klee and Walkup (Acta Math 117:53-78, <xref>1967</xref>), the Hirsch conjecture of an upper bound of f-d<inline-graphic></inline-graphic> was shown to be equivalent to several seemingly simpler statements, and was disproved for unbounded polyhedra through the construction of a particular 4-dimensional polyhedron U4<inline-graphic></inline-graphic> with eight facets. The Hirsch bound for bounded polyhedra was only recently disproved by Santos (Ann Math 176(1):383-412, <xref>2012</xref>). We consider analogous properties for a variant of the combinatorial diameter called the circuit diameter. In this variant, the walks are built from the circuit directions of the polyhedron, which are the minimal non-trivial solutions to the system defining the polyhedron. We are able to prove that circuit variants of the so-called non-revisiting conjecture and d-step conjecture both imply the circuit analogue of the Hirsch conjecture. For the equivalences in Klee and Walkup, the wedge construction was a fundamental proof technique. We exhibit why it is not available in the circuit setting, and what are the implications of losing it as a tool. Further, we show the circuit analogue of the non-revisiting conjecture implies a linear bound on the circuit diameter of all unbounded polyhedra—in contrast to what is known for the combinatorial diameter. Finally, we give two proofs of a circuit version of the 4-step conjecture. These results offer some hope that the circuit version of the Hirsch conjecture may hold, even for unbounded polyhedra. A challenge in the circuit setting is that different realizations of polyhedra with the same combinatorial structure may have different diameters. We adapt the notion of simplicity to work with circuits in the form of C<inline-graphic></inline-graphic>-simple and wedge-simple polyhedra. We show that it suffices to consider such polyhedra for studying circuit analogues of the Hirsch conjecture. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=131498427
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00454-018-9995-y
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 30
        StartPage: 558
    Subjects:
      – SubjectFull: Polyhedra
        Type: general
      – SubjectFull: Polyhedra models
        Type: general
      – SubjectFull: Geometric modeling
        Type: general
      – SubjectFull: Geometric surfaces
        Type: general
      – SubjectFull: Diameter
        Type: general
    Titles:
      – TitleFull: On the Circuit Diameter Conjecture.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Borgwardt, Steffen
      – PersonEntity:
          Name:
            NameFull: Stephen, Tamon
      – PersonEntity:
          Name:
            NameFull: Yusun, Timothy
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 10
              Text: Oct2018
              Type: published
              Y: 2018
          Identifiers:
            – Type: issn-print
              Value: 01795376
          Numbering:
            – Type: volume
              Value: 60
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: Discrete & Computational Geometry
              Type: main
ResultId 1