Description:
A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. We deal with the connectivity of the graphs of cubical polytopes. We first establish that, for any d >= 3, the graph of a cubical d-polytope with minimum degree 5 is min{delta, 2d - 2}-connected. Second, we show, for any d >= 4, that every minimum separator of cardinality at most 2d - 3 in such a graph consists of all the neighbours of some vertex and that removing the vertices of the separator from the graph leaves exactly two components, with one of them being the vertex itself. (C) 2019 Elsevier Inc. All rights reserved.
Description:
A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. We deal with the connectivity of the graphs of cubical polytopes. We first establish that, for any d >= 3, the graph of a cubical d-polytope with minimum degree 5 is min{delta, 2d - 2}-connected. Second, we show, for any d >= 4, that every minimum separator of cardinality at most 2d - 3 in such a graph consists of all the neighbours of some vertex and that removing the vertices of the separator from the graph leaves exactly two components, with one of them being the vertex itself. (C) 2019 Elsevier Inc. All rights reserved.
Description:
Variational analysis, a relatively new area of research in mathematics, has become one of the most powerful tools in nonsmooth optimisation and neighbouring areas. The extremal principle, a tool to substitute the conventional separation theorem in the general nonconvex environment, is a fundamental result in variational analysis. There have seen many attempts to generalise the conventional extremal principle in order to tackle certain optimisation models. Models involving collections of sets, initiated by the extremal principle, have proved their usefulness in analysis and optimisation, with non-intersection properties (or their absence) being at the core of many applications: recall the ubiquitous convex separation theorem, extremal principle, Dubovitskii Milyutin formalism and various transversality/regularity properties. We study elementary nonintersection properties of collections of sets, making the core of the conventional definitions of extremality and stationarity. In the setting of general Banach/Asplund spaces, we establish nonlinear primal (slope) and linear/nonlinear dual (generalised separation) characterisations of these non-intersection properties. We establish a series of consequences of our main results covering all known formulations of extremality/ stationarity and generalised separability properties. This research develops a universal theory, unifying all the current extensions of the extremal principle, providing new results and better understanding for the exquisite theory of variational analysis. This new study also results in direct solutions for many open questions and new future research directions in the fields of variational analysis and optimisation. Some new nonlinear characterisations of the conventional extremality/stationarity properties are obtained. For the first time, the intrinsic transversality property is characterised in primal space without involving normal cones. This characterisation brings a new perspective on intrinsic transversality. In the process, we thoroughly expose and classify all quantitative geometric and metric characterisations of transversality properties of collections of sets and regularity properties of set-valued mappings.
Description:
Variational analysis, a relatively new area of research in mathematics, has become one of the most powerful tools in nonsmooth optimisation and neighbouring areas. The extremal principle, a tool to substitute the conventional separation theorem in the general nonconvex environment, is a fundamental result in variational analysis. There have seen many attempts to generalise the conventional extremal principle in order to tackle certain optimisation models. Models involving collections of sets, initiated by the extremal principle, have proved their usefulness in analysis and optimisation, with non-intersection properties (or their absence) being at the core of many applications: recall the ubiquitous convex separation theorem, extremal principle, Dubovitskii Milyutin formalism and various transversality/regularity properties. We study elementary nonintersection properties of collections of sets, making the core of the conventional definitions of extremality and stationarity. In the setting of general Banach/Asplund spaces, we establish nonlinear primal (slope) and linear/nonlinear dual (generalised separation) characterisations of these non-intersection properties. We establish a series of consequences of our main results covering all known formulations of extremality/ stationarity and generalised separability properties. This research develops a universal theory, unifying all the current extensions of the extremal principle, providing new results and better understanding for the exquisite theory of variational analysis. This new study also results in direct solutions for many open questions and new future research directions in the fields of variational analysis and optimisation. Some new nonlinear characterisations of the conventional extremality/stationarity properties are obtained. For the first time, the intrinsic transversality property is characterised in primal space without involving normal cones. This characterisation brings a new perspective on intrinsic transversality. In the process, we thoroughly expose and classify all quantitative geometric and metric characterisations of transversality properties of collections of sets and regularity properties of set-valued mappings.
Description:
The core arguments used in various proofs of the extremal principle and its extensions as well as in primal and dual characterizations of approximate stationarity and transversality of collections of sets are exposed, analysed and refined, leading to a unifying theory, encompassing all existing approaches to obtaining ‘extremal’ statements. For that, we examine and clarify quantitative relationships between the parameters involved in the respective definitions and statements. Some new characterizations of extremality properties are obtained.
Description:
The core arguments used in various proofs of the extremal principle and its extensions as well as in primal and dual characterizations of approximate stationarity and transversality of collections of sets are exposed, analysed and refined, leading to a unifying theory, encompassing all existing approaches to obtaining ‘extremal’ statements. For that, we examine and clarify quantitative relationships between the parameters involved in the respective definitions and statements. Some new characterizations of extremality properties are obtained.
Description:
The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least 2k vertices is k-linked if, for every set of k disjoint pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We say that a polytope is k-linked if its graph is k-linked. We establish that the d-dimensional cube is [(d + 1)/2]-linked, for every d ≠ 3; this is the maximum possible linkedness of a d-polytope. This result implies that, for every d ≥ 1, a cubical d-polytope is [d/2]-linked, which answers a question of Wotzlaw (Incidence graphs and unneighborly polytopes, Ph.D. thesis, 2009). Finally, we introduce the notion of strong linkedness, which is slightly stronger than that of linkedness. A graph G is strongly k-linked if it has at least 2k + 1 vertices and, for every vertex v of G, the subgraph G − v is k-linked. We show that cubical 4-polytopes are strongly 2-linked and that, for each d ≥ 1, d-dimensional cubes are strongly
Description:
The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least 2k vertices is k-linked if, for every set of k disjoint pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We say that a polytope is k-linked if its graph is k-linked. We establish that the d-dimensional cube is [(d + 1)/2]-linked, for every d ≠ 3; this is the maximum possible linkedness of a d-polytope. This result implies that, for every d ≥ 1, a cubical d-polytope is [d/2]-linked, which answers a question of Wotzlaw (Incidence graphs and unneighborly polytopes, Ph.D. thesis, 2009). Finally, we introduce the notion of strong linkedness, which is slightly stronger than that of linkedness. A graph G is strongly k-linked if it has at least 2k + 1 vertices and, for every vertex v of G, the subgraph G − v is k-linked. We show that cubical 4-polytopes are strongly 2-linked and that, for each d ≥ 1, d-dimensional cubes are strongly
Description:
We state the problems discussed in the open problem session at Variational Analysis Down Under conference held in honour of Prof. Asen Dontchev on 19-21 February 2018 at Federation University Australia.
Description:
We state the problems discussed in the open problem session at Variational Analysis Down Under conference held in honour of Prof. Asen Dontchev on 19-21 February 2018 at Federation University Australia.