Minimum number of edges of polytopes with 2d + 2 vertices
- Authors: Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2022
- Type: Text , Journal article
- Relation: Electronic Journal of Combinatorics Vol. 29, no. 3 (2022), p.
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: We define two d-polytopes, both with 2d + 2 vertices and (d + 3)(d
The lower bound theorem for d - polytopes with 2d + 1 vertices
- Authors: Pineda-Villavicencio, Guillermo , Yost, David
- Date: 2022
- Type: Text , Journal article
- Relation: SIAM Journal on Discrete Mathematics Vol. 36, no. 4 (2022), p. 2920-2941
- Full Text:
- Reviewed:
- Description: The problem of calculating exact lower bounds for the number of k-faces of dpolytopes with n vertices, for each value of k, and characterizing the minimizers has recently been solved for n not exceeding 2d. We establish the corresponding result for n = 2d+ 1; the nature of the lower bounds and the minimizing polytopes are quite different in this case. As a byproduct, we also characterize all d-polytopes with d + 3 vertices and only one or two edges more than the minimum. © 2022 Society for Industrial and Applied Mathematics.
Zero duality gap conditions via abstract convexity
- Authors: Bui, Hoa , Burachik, Regina , Kruger, Alexander , Yost, David
- Date: 2022
- Type: Journal article
- Relation: Optimization Vol. 71, no. 4 (2022), p. 811-847
- Relation: https://purl.org/au-research/grants/arc/DP160100854
- Full Text:
- Reviewed:
- Description: Using tools provided by the theory of abstract convexity, we extend conditions for zero duality gap to the context of non-convex and nonsmooth optimization. Mimicking the classical setting, an abstract convex function is the upper envelope of a family of abstract affine functions (being conventional vertical translations of the abstract linear functions). We establish new conditions for zero duality gap under no topological assumptions on the space of abstract linear functions. In particular, we prove that the zero duality gap property can be fully characterized in terms of an inclusion involving (abstract) (Formula presented.) -subdifferentials. This result is new even for the classical convex setting. Endowing the space of abstract linear functions with the topology of pointwise convergence, we extend several fundamental facts of functional/convex analysis. This includes (i) the classical Banach–Alaoglu–Bourbaki theorem (ii) the subdifferential sum rule, and (iii) a constraint qualification for zero duality gap which extends a fact established by Borwein, Burachik and Yao (2014) for the conventional convex case. As an application, we show with a specific example how our results can be exploited to show zero duality for a family of non-convex, non-differentiable problems. © 2021 Informa UK Limited, trading as Taylor & Francis Group.
Chebyshev multivariate polynomial approximation and point reduction procedure
- Authors: Sukhorukova, Nadezda , Ugon, Julien , Yost, David
- Date: 2021
- Type: Text , Journal article
- Relation: Constructive Approximation Vol. 53, no. 3 (2021), p. 529-544
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: We apply the methods of nonsmooth and convex analysis to extend the study of Chebyshev (uniform) approximation for univariate polynomial functions to the case of general multivariate functions (not just polynomials). First of all, we give new necessary and sufficient optimality conditions for multivariate approximation, and a geometrical interpretation of them which reduces to the classical alternating sequence condition in the univariate case. Then, we present a procedure for verification of necessary and sufficient optimality conditions that is based on our generalization of the notion of alternating sequence to the case of multivariate polynomials. Finally, we develop an algorithm for fast verification of necessary optimality conditions in the multivariate polynomial case. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.
Strictly convex banach algebras
- Authors: Yost, David
- Date: 2021
- Type: Text , Journal article
- Relation: Axioms Vol. 10, no. 3 (2021), p.
- Full Text:
- Reviewed:
- Description: We discuss two facets of the interaction between geometry and algebra in Banach algebras. In the class of unital Banach algebras, there is essentially one known example which is also strictly convex as a Banach space. We recall this example, which is finite-dimensional, and consider the open question of generalising it to infinite dimensions. In C
Almost simplicial polytopes : the lower and upper bound theorems
- Authors: Nevo, Eran , Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2020
- Type: Text , Journal article
- Relation: Canadian Journal of Mathematics Vol. 72, no. 2 (2020), p. 537-556. http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: We study -vertex -dimensional polytopes with at most one nonsimplex facet with, say, vertices, called almost simplicial polytopes. We provide tight lower and upper bound theorems for these polytopes as functions of, and, thus generalizing the classical Lower Bound Theorem by Barnette and the Upper Bound Theorem by McMullen, which treat the case where s = 0. We characterize the minimizers and provide examples of maximizers for any. Our construction of maximizers is a generalization of cyclic polytopes, based on a suitable variation of the moment curve, and is of independent interest. © 2018 Canadian Mathematical Society.
Observations on the separable quotient problem for banach spaces
- Authors: Morris, Sidney , Yost, David
- Date: 2020
- Type: Text , Journal article
- Relation: Axioms Vol. 9, no. 1 (2020), p.
- Full Text:
- Reviewed:
- Description: The longstanding Banach-Mazur separable quotient problem asks whether every infinite-dimensional Banach space has a quotient (Banach) space that is both infinite-dimensional and separable. Although it remains open in general, an affirmative answer is known in many special cases, including (1) reflexive Banach spaces, (2) weakly compactly generated (WCG) spaces, and (3) Banach spaces which are dual spaces. Obviously (1) is a special case of both (2) and (3), but neither (2) nor (3) is a special case of the other. A more general result proved here includes all three of these cases. More precisely, we call an infinite-dimensional Banach space X dual-like, if there is another Banach space E, a continuous linear operator T from the dual space E* onto a dense subspace of X, such that the closure of the kernel of T (in the relative weak* topology) has infinite codimension in E*. It is shown that every dual-like Banach space has an infinite-dimensional separable quotient. © 2020 by the authors.
Polytopes close to being simple
- Authors: Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2020
- Type: Text , Journal article
- Relation: Discrete and Computational Geometry Vol. 64, no. 1 (2020), p. 200-215
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: It is known that polytopes with at most two nonsimple vertices are reconstructible from their graphs, and that d-polytopes with at most d- 2 nonsimple vertices are reconstructible from their 2-skeletons. Here we close the gap between 2 and d- 2 , showing that certain polytopes with more than two nonsimple vertices are reconstructible from their graphs. In particular, we prove that reconstructibility from graphs also holds for d-polytopes with d+ k vertices and at most d- k+ 3 nonsimple vertices, provided k
Schur functions for approximation problems
- Authors: Sukhorukova, Nadezda , Ugon, Julien , Yost, David
- Date: 2020
- Type: Text , Book chapter
- Relation: 2018 Matrix Annals p. 331-337
- Full Text: false
- Reviewed:
- Description: In this paper we propose a new approach to least squares approximation problems. This approach is based on partitioning and Schur function. The nature of this approach is combinatorial, while most existing approaches are based on algebra and algebraic geometry. This problem has several practical applications. One of them is curve clustering. We use this application to illustrate the results.
Lower bound theorems for general polytopes
- Authors: Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2019
- Type: Text , Journal article
- Relation: European Journal of Combinatorics Vol. 79, no. (2019), p. 27-45
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: For a d-dimensional polytope with v vertices, d + 1 <= v <= 2d, we calculate precisely the minimum possible number of m-dimensional faces, when m = 1 or m >= 0.62d. This confirms a conjecture of Grunbaum, for these values of m. For v = 2d + 1, we solve the same problem when m = 1 or d - 2; the solution was already known for m = d - 1. In all these cases, we give a characterisation of the minimising polytopes. We also show that there are many gaps in the possible number of m-faces: for example, there is no polytope with 80 edges in dimension 10, and a polytope with 407 edges can have dimension at most 23.
On the reconstruction of polytopes
- Authors: Doolittle, Joseph , Nevo, Eran , Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2019
- Type: Text , Journal article
- Relation: Discrete and Computational Geometry Vol. 61, no. 2 (2019), p. 285-302. http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: Blind and Mani, and later Kalai, showed that the face lattice of a simple polytope is determined by its graph, namely its 1-skeleton. Call a vertex of a d-polytope nonsimple if the number of edges incident to it is more than d. We show that (1) the face lattice of any d-polytope with at most two nonsimple vertices is determined by its 1-skeleton; (2) the face lattice of any d-polytope with at most d- 2 nonsimple vertices is determined by its 2-skeleton; and (3) for any d> 3 there are two d-polytopes with d- 1 nonsimple vertices, isomorphic (d- 3) -skeleta and nonisomorphic face lattices. In particular, the result (1) is best possible for 4-polytopes. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.
Chebyshev multivariate polynomial approximation : alternance interpretation
- Authors: Sukhorukova, Nadezda , Ugon, Julien , Yost, David
- Date: 2018
- Type: Text , Book chapter
- Relation: 2016 Matrix Annals p. 177-182
- Full Text:
- Reviewed:
- Description: In this paper, we derive optimality conditions for Chebyshev approximation of multivariate functions. The theory of Chebyshev (uniform) approximation for univariate functions was developed in the late nineteenth and twentieth century. The optimality conditions are based on the notion of alternance (maximal deviation points with alternating deviation signs). It is not clear, however, how to extend the notion of alternance to the case of multivariate functions. There have been several attempts to extend the theory of Chebyshev approximation to the case of multivariate functions. We propose an alternative approach, which is based on the notion of convexity and nonsmooth analysis.
Compact convex sets with prescribed facial dimensions
- Authors: Roshchina, Vera , Sang, Tian , Yost, David
- Date: 2018
- Type: Text , Book chapter
- Relation: 2016 Matrix Annals p. 167-175
- Full Text:
- Reviewed:
- Description: While faces of a polytope form a well structured lattice, in which faces of each possible dimension are present, this is not true for general compact convex sets. We address the question of what dimensional patterns are possible for the faces of general closed convex sets. We show that for any finite sequence of positive integers there exist compact convex sets which only have extreme points and faces with dimensions from this prescribed sequence. We also discuss another approach to dimensionality, considering the dimension of the union of all faces of the same dimension. We show that the questions arising from this approach are highly nontrivial and give examples of convex sets for which the sets of extreme points have fractal dimension.
The excess degree of a polytope
- Authors: Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2018
- Type: Text , Journal article
- Relation: SIAM Journal on Discrete Mathematics Vol. 32, no. 3 (2018), p. 2011-2046, http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: We define the excess degree \xi (P) of a d-polytope P as 2f1 - df0, where f0 and f1 denote the number of vertices and edges, respectively. This parameter measures how much P deviates from being simple. It turns out that the excess degree of a d-polytope does not take every natural number: the smallest possible values are 0 and d - 2, and the value d - 1 only occurs when d = 3 or 5. On the other hand, for fixed d, the number of values not taken by the excess degree is finite if d is odd, and the number of even values not taken by the excess degree is finite if d is even. The excess degree is then applied in three different settings. First, it is used to show that polytopes with small excess (i.e., \xi (P) < d) have a very particular structure: provided d ot = 5, either there is a unique nonsimple vertex, or every nonsimple vertex has degree d + 1. This implies that such polytopes behave in a similar manner to simple polytopes in terms of Minkowski decomposability: they are either decomposable or pyramidal, and their duals are always indecomposable. Second, we characterize completely the decomposable d-polytopes with 2d + 1 vertices (up to combinatorial equivalence). Third, all pairs (f0, f1), for which there exists a 5-polytope with f0 vertices and f1 edges, are determined.
More indecomposable polyhedra
- Authors: Przesławski, Krzysztof , Yost, David
- Date: 2016
- Type: Text , Journal article
- Relation: Extracta Mathematicae Vol. 31, no. 2 (2016), p. 169-188
- Full Text:
- Reviewed:
- Description: We apply combinatorial methods to a geometric problem: the classification of polytopes, in terms of Minkowski decomposability. Various properties of skeletons of polytopes are exhibited, each sufficient to guarantee indecomposability of a significant class of polytopes. We illustrate further the power of these techniques, compared with the traditional method of examining triangular faces, with several applications. In any dimension d 6= 2, we show that of all the polytopes with d2 + 1 2 d or fewer edges, only one is decomposable. In 3 dimensions, we complete the classification, in terms of decomposability, of the 260 combinatorial types of polyhedra with 15 or fewer edges.
- Description: We apply combinatorial methods to a geometric problem: the classification of polytopes, in terms of Minkowski decomposability. Various properties of skeletons of polytopes are exhibited, each sufficient to guarantee indecomposability of a significant class of polytopes. We illustrate further the power of these techniques, compared with the traditional method of examining triangular faces, with several applications. In any dimension $d\neq 2$, we show that of all the polytopes with $d^2+\frac{d}{2}$ or fewer edges, only one is decomposable. In 3 dimensions, we complete the classification, in terms of decomposability, of the 260 combinatorial types of polyhedra with 15 or fewer edges.
Quasilinear Mappings, M-Ideals and Popyhedra
- Authors: Yost, David
- Date: 2012
- Type: Text , Conference paper
- Relation: Operators and Matrices Vol. 6, p. 279-286
- Full Text:
- Reviewed:
- Description: We survey the connection between two results from rather different areas: failure of the 3-space property for local convexity (and other properties) within the category of quasi-Banach spaces, and the irreducibility (in the sense of Minkowski difference) of large families of finite dimensional polytopes.
- Description: C1
Lipschitz selections for multifunctions
- Authors: Yost, David
- Date: 2010
- Type: Text , Conference proceedings
- Full Text: false
A Different Johnson-Lindenstrauss Space
- Authors: Yost, David
- Date: 2008
- Type: Text , Journal article
- Relation: New Zealand Journal of Mathematics Vol. 37, no. (2008), p. 47-49
- Full Text: false
- Reviewed:
- Description: We exhibit a non-trivial twisted sum of c0 with a Hilbert space, which is not isomorphic to the example constructed by Johnson and Lindenstrauss in 1974. In fact, no non-separable subspace of either example is isomorphic to any subspace of the other.
- Description: 2003006488
Decomposability of polytopes
- Authors: Przeslawski, Krzysztof , Yost, David
- Date: 2008
- Type: Text , Journal article
- Relation: Discrete & Computational Geometry Vol. 39, no. 1-3 (Mar 2008), p. 460-468
- Full Text:
- Reviewed:
- Description: A known characterization of the decomposability of polytopes is reformulated in a way which may be more computationally convenient, and a more transparent proof is given. New sufficient conditions for indecomposability are then deduced, and illustrated with some examples.
- Description: C1
Integration: Reversing traditional pedagogy
- Authors: Yost, David
- Date: 2008
- Type: Text , Journal article
- Relation: Australian Senior Mathematics Journal Vol. 22, no. 2 (2008), p. 37-40
- Full Text: false
- Reviewed:
- Description: The author recommends teaching integration first, and move on to differential calculus only after a sound understanding of integration has been attained. A rationale for teaching integrals before derivatives in a first calculus unit intended primarily for engineering students at the University of Ballarat is presented. It is concluded that students fail to see the connection between getting the right answer and understanding what they are doing. It is noted that the formal manipulations required for high school differential calculus questions are simpler than those for integral calculus.