skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, January 16 until 2:00 AM ET on Friday, January 17 due to maintenance. We apologize for the inconvenience.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


  • Home
  • Search Results
  • Page 1 of 1

Search for: All records

Creators/Authors contains: "Leroux, Brett"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; ( , Random Structures & Algorithms)
    Abstract

    A conjecture of Milena Mihail and Umesh Vazirani (Proc. 24th Annu. ACM Symp. Theory Comput., ACM, Victoria, BC, 1992, pp. 26–38.) states that the edge expansion of the graph of every polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of the conjecture of Mihail and Vazirani says that the edge expansion of the graph of a polytope in is greater than one over some polynomial function of . This weaker version of the conjecture would suffice for all applications. Our main result is that the edge expansion of the graph of arandompolytope in is at least with high probability.

     
    more » « less
    Free, publicly-accessible full text available March 1, 2025
  2. ; ( , Discrete & Computational Geometry)
    Full Text Available 
  3. ; ( , Discrete & Computational Geometry)
    Full Text Available