Recent Comments

Recent Posts
 Updates (belated) Between New Haven, Jerusalem, and TelAviv
 Oded Goldreich Fest
 The Race to Quantum Technologies and Quantum Computers (Useful Links)
 Around the GarsiaStanley’s Partitioning Conjecture
 My Answer to TYI 28
 Test your intuition 28: What is the most striking common feature to all these remarkable individuals
 R(5,5) ≤ 48
 Test Your Intuition (27) about the AlonTarsi Conjecture
 Thilo Weinert: Transfinite Ramsey Numbers
Top Posts & Pages
 Borsuk's Conjecture
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 In how many ways you can chose a committee of three students from a class of ten students?
 The Race to Quantum Technologies and Quantum Computers (Useful Links)
 Can Category Theory Serve as the Foundation of Mathematics?
 A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24
 A Proof by Induction with a Difficulty
 Symplectic Geometry, Quantization, and Quantum Noise
 Is Mathematics a Science?
RSS
Tag Archives: Hirsch conjecture
The Polynomial Hirsch Conjecture – How to Improve the Upper Bounds.
I can see three main avenues toward making progress on the Polynomial Hirsch conjecture. One direction is trying to improve the upper bounds, for example, by looking at the current proof and trying to see if it is wasteful and if so where … Continue reading
Posted in Convex polytopes, Open discussion, Open problems
Tagged Discussion, Hirsch conjecture
14 Comments
The Polynomial Hirsch Conjecture, a Proposal for Polymath3 (Cont.)
The Abstract Polynomial Hirsch Conjecture A convex polytope is the convex hull of a finite set of points in a real vector space. A polytope can be described as the intersection of a finite number of closed halfspaces. Polytopes have … Continue reading
Posted in Convex polytopes, Open discussion, Open problems
Tagged Hirsch conjecture, Polymath proposals
5 Comments
The Polynomial Hirsch Conjecture: A proposal for Polymath3
This post is continued here. Eddie Kim and Francisco Santos have just uploaded a survey article on the Hirsch Conjecture. The Hirsch conjecture: The graph of a dpolytope with n vertices facets has diameter at most nd. We devoted several … Continue reading
A Diameter problem (7): The Best Known Bound
Our Diameter problem for families of sets Consider a family of subsets of size d of the set N={1,2,…,n}. Associate to a graph as follows: The vertices of are simply the sets in . Two vertices and are adjacent if . … Continue reading
A Diameter Problem (6): Abstract Objective Functions
George Dantzig and Leonid Khachyan In this part we will not progress on the diameter problem that we discussed in the earlier posts but will rather describe a closely related problem for directed graphs associated with ordered families of sets. The role models for … Continue reading
Posted in Combinatorics, Convex polytopes, Open problems
Tagged Hirsch conjecture, Linear programming
7 Comments
A Diameter Problem (5)
6. First subexponential bounds. Proposition 1: How to prove it: This is easy to prove: Given two sets and in our family , we first find a path of the form where, and . We let with and consider the family … Continue reading
Diameter Problem (4)
Let us consider another strategy to deal with our diameter problem. Let us try to associate other graphs to our family of sets. Recall that we consider a family of subsets of size of the set . Let us now associate … Continue reading
Diameter Problem (3)
3. What we will do in this post and and in future posts We will now try all sorts of ideas to give good upper bounds for the abstract diameter problem that we described. As we explained, such bounds apply … Continue reading
Posted in Combinatorics, Convex polytopes, Open problems
Tagged Hirsch conjecture, Linear programming, Quasiautomated proofs
1 Comment