On polyhedral extension of some LP theorems

McLinden (Mathematical Programming 24 (1982) 162–176) has extended theorems of Tucker (1956) and Williams (1970) on the complementarity behaviour of feasible and optimal solutions to a pair of canonical linear programs to proper convex polyhedral functions. He achieved this by heavily using the well-developed machinery of convex analysis. In this note, we prove most of his results mainly using linear programming theory.     

On the Lipschitzian properties of polyhedral multifunctions

In this paper, we show that for a polyhedral multifunctionF:R ⁿ →R ^m with convex range, the inverse functionF ⁻¹ is locally lower Lipschitzian at every point of the range ofF (equivalently Lipschitzian on the range ofF) if and only if the functionF is open. As a consequence, we show that for a piecewise affine functionf:R ⁿ →R ⁿ ,f is surjective andf ⁻¹ is Lipschitzian if and only iff is coherently oriented. An application, via Robinson's normal map formulation, leads to the following result in the context of affine variational inequalities: the solution mapping (as a function of the data vector) is nonempty-valued and Lipschitzian on the entire space if and only if the solution mapping is single-valued. This extends a recent result of Murthy, Parthasarathy and Sabatini, proved in the setting of linear complementarity problems. Research supported by the National Science Foundation Grant CCR-9307685.     

Numerical index of some polyhedral norms on the plane

We give explicit formulae for the numerical index of some (real) polyhedral spaces of dimension two. Concretely, we calculate the numerical index of a family of hexagonal norms, two families of octagonal norms and the family of norms whose unit balls are regular polygons with an even number of vertices.     

On the convergence of metric and geometric properties of polyhedral surfaces

We provide conditions for convergence of polyhedral surfaces and their discrete geometric properties to smooth surfaces embedded in Euclidean 3-space. Under the assumption of convergence of surfaces in Hausdorff distance, we show that convergence of the following properties are equivalent: surface normals, surface area, metric tensors, and Laplace–Beltrami operators. Additionally, we derive convergence of minimizing geodesics, mean curvature vectors, and solutions to the Dirichlet problem. This work was supported by the DFG Research Center Matheon “Mathematics for key technologies” in Berlin.     

On random permutations without cycles of some lenghts

We deal with random permutations of the symmetric group S_Nendowed with the Haar probability measure. The main purpose of the remark is to obtain uniform lower estimates for the probability of a permutation without cycles having lengths in some J ⊂ {1, . . . . N} . ThesetJcan itself depend on N. The only information used is a bound for the sum of reciprocals of elements in J.     

Odd cycles and matrices with integrality properties

A cycle of a bipartite graphG(V⁺, V^?; E) is odd if its length is 2 (mod 4), even otherwise. An odd cycleC is node minimal if there is no odd cycleC′ of cardinality less than that ofC′ such that one of the following holds:C′ ∩V ⁺ ?C ∩V ⁺ orC′ ∩V ^? ?C ∩V ^?. In this paper we prove the following theorem for bipartite graphs: For a bipartite graphG, one of the following alternatives holds:

-All the cycles ofG are even.

-G has an odd chordless cycle.

-For every node minimal odd cycleC, there exist four nodes inC inducing a cycle of length four.

-An edge (u, v) ofG has the property that the removal ofu, v and their adjacent nodes disconnects the graphG.

To every (0, 1) matrixA we can associate a bipartite graphG(V⁺, V^?; E), whereV ⁺ andV ^? represent respectively the row set and the column set ofA and an edge (i,j) belongs toE if and only ifa _ij = 1. The above theorem, applied to the graphG(V⁺, V^?; E) can be used to show several properties of some classes of balanced and perfect matrices. In particular it implies a decomposition theorem for balanced matrices containing a node minimal odd cycleC, having the property that no four nodes ofC induce a cycle of length 4. The above theorem also yields a proof of the validity of the Strong Perfect Graph Conjecture for graphs that do not containK ₄?e as an induced subgraph.     

Graceful signed graphs: II. The case of signed cycles with connected negative sections

In our earlier paper [9], generalizing the well known notion of graceful graphs, a (p, m, n)-signed graph S of order p, with m positive edges and n negative edges, is called graceful if there exists an injective function f that assigns to its p vertices integers 0, 1,...,q = m + n such that when to each edge uv of S one assigns the absolute difference |f(u)-f(v)| the set of integers received by the positive edges of S is {1,2,...,m} and the set of integers received by the negative edges of S is {1,2,...,n}. Considering the conjecture therein that all signed cycles Z_k, of admissible length k 3 and signed structures, are graceful, we establish in this paper its truth for all possible signed cycles of lengths 0, 2 or 3 (mod 4) in which the set of negative edges forms a connected subsigraph.     

The convex floating body and polyhedral approximation

We consider the convex floating body of a polytope and polyhedral approximation of a convex body. Supported by NSF grant DMS-8902327.     

Small-amplitude limit cycles of some Liénard-type systems

As we know, the Liénard system and its generalized forms are classical and important models of nonlinear oscillators, and have been widely studied by mathematicians and scientists. The main problem considered by most people is the number of limit cycles. In this paper, we investigate two kinds of Liénard systems and obtain the maximal number (i.e. the least upper bound) of limit cycles appearing in Hopf bifurcations by applying some known bifurcation theorems with technical analysis.     

On some three color Ramsey numbers for paths and cycles

For given graphs G₁,G₂,…,G_k, k≥2, the multicolor Ramsey number, denoted by R(G₁,G₂,…,G_k), is the smallest integer n such that if we arbitrarily color the edges of a complete graph on n vertices with k colors, there is always a monochromatic copy of G_i colored with i, for some 1≤i≤k. Let P_k (resp. C_k) be the path (resp. cycle) on k vertices. In the paper we consider the value for numbers of type R(P_i,P_k,C_m) for odd m, k≥m≥3 and when i is odd, and when i is even. In addition, we provide the exact values for Ramsey numbers R(P₃,P_k,C₄) for all integers k≥3.