Integration formulas via the Fenchel subdifferential of nonconvex functions

Starting from explicit expressions for the subdifferential of the conjugate function, we establish in the Banach space setting some integration results for the so-called epi-pointed functions. These results use the ε-subdifferential and the Fenchel subdifferential of an appropriate weak lower semicontinuous (lsc) envelope of the initial function. We apply these integration results to the construction of the lsc convex envelope either in terms of the ε-subdifferential of the nominal function or of the subdifferential of its weak lsc envelope.     

Remarks on subgradients and ?-subgradients

We show that Rockafellar's maximal monotonicity and maximal cyclical monotonicity theorems for subdifferentials can be reformulated and proved for the family of -subdifferentials of a proper, lower semicontinuous, convex function defined on a normed space. We also show that the subdifferential map of a lower semicontinuous convex function defined on a Banach space is bothX andX* locally maximal monotone.     

Testing Monotonicity

at arguments of its choice, the test always accepts a monotone f, and rejects f with high probability if it is ε-far from being monotone (i.e., every monotone function differs from f on more than an ε fraction of the domain). The complexity of the test is O(n/ε). The analysis of our algorithm relates two natural combinatorial quantities that can be measured with respect to a Boolean function; one being global to the function and the other being local to it. A key ingredient is the use of a switching (or sorting) operator on functions. Received March 29, 1999     

Functional inequality characterizing nonnegative concave functions in (0, ∞) k

Summary In the present note we prove that every functionf: (0, ) [0, ) satisfying the inequalityaf(s) + bf(t) f(as + bt), s, t > 0, for somea andb such that 0 <a < 1 <a + b must be of the formf(t) = f(1)t, (t > 0). This improves our recent result in [2], where the inequality is assumed to hold for alls, t 0, and gives a positive answer to the question raised there.An analogue for functions of several real variables of the above result characterizes concave functions. Conjugate functions and some relations to Hölder's and Minkowski's inequalities are mentioned.     

Fitzpatrick functions,cyclic monotonicity and Rockafellar’s antiderivative

Several deeper results on maximal monotone operators have recently found simpler proofs using Fitzpatrick functions. In this paper, we study a sequence of Fitzpatrick functions associated with a monotone operator. The first term of this sequence coincides with the original Fitzpatrick function, and the other terms turn out to be useful for the identification and characterization of cyclic monotonicity properties. It is shown that for any maximal cyclically monotone operator, the pointwise supremum of the sequence of Fitzpatrick functions is closely related to Rockafellar’s antiderivative. Several examples are explicitly computed for the purpose of illustration. In contrast to Rockafellar’s result, a maximal 3-cyclically monotone operator need not be maximal monotone. A simplified proof of Asplund’s observation that the rotation in the Euclidean plane by π/n$\pi /n$ is n$n$-cyclically monotone but not (n+1)$(n+1)$-cyclically monotone is provided. The Fitzpatrick family of the subdifferential operator of a sublinear and of an indicator function is studied in detail. We conclude with a new proof of Moreau’s result concerning the convexity of the set of proximal mappings.     

Quasi-symmetric 2, 3, 4-designs

Quasi-symmetric designs are block designs with two block intersection numbersx andy It is shown that with the exception of (x, y)=(0, 1), for a fixed value of the block sizek, there are finitely many such designs. Some finiteness results on block graphs are derived. For a quasi-symmetric 3-design with positivex andy, the intersection numbers are shown to be roots of a quadratic whose coefficients are polynomial functions ofv, k and λ. Using this quadratic, various characterizations of the Witt—Lüneburg design on 23 points are obtained. It is shown that ifx=1, then a fixed value of λ determines at most finitely many such designs.     

Cone monotone mappings: Continuity and differentiability

We generalize some results of Borwein, Burke, Lewis, and Wang to mappings with values in metric (resp. ordered normed linear) spaces, and we define two classes of monotone mappings between an ordered linear space and a metric space (resp. ordered linear space): K$K$-monotone dominated and cone-to-cone monotone mappings. K$K$-monotone dominated mappings naturally generalize mappings with finite variation (in the classical sense) and K$K$-monotone functions defined by Borwein, Burke and Lewis to mappings with domains and ranges of higher dimensions. First, using results of Veselý and Zají?ek, we show some relationships between these classes. Then, we show that every K$K$-monotone function f:X→R$f:X\to \mathbb{R}$, where X$X$ is any Banach space, is continuous outside of a set which can be covered by countably many Lipschitz hypersurfaces. This sharpens a result due to Borwein and Wang. As a consequence, we obtain a similar result for K$K$-monotone dominated and cone-to-cone monotone mappings. Finally, we prove several results concerning almost everywhere differentiability (also in metric and w^∗$w^{\ast }$-senses) of these mappings.     

On the structure of singular sets of convex functions

Whenf is a convex function ofR ^h, andk is an integer with 0<k, then the set ^k (f)=x:dim(f(x)k may be covered by countably many manifolds of dimensionh–k and classC ² except an _h–k negligible subset.The author is supported by INdAM     

On the number of lines in planar spaces

SupposeS is a planar space withv>4 points and letq be the positive real number such thatv=q ³+q²+q+1. Assuming a weak non-degeneracy condition, we shall show thatS has at least (q²+1)(q²+q+1) lines with equality iffq is a prime power andS=PG(3,q).     

The implicit function theorem in a non-Archimedean setting

In this paper, the inverse function theorem and the implicit function theorem in a non-Archimedean setting will be discussed. We denote by N any non-Archimedean field extension of the real numbers that is real closed and Cauchy complete in the topology induced by the order; and we study the properties of locally uniformly differentiable functions from Nⁿ to N^m. Then we use that concept of local uniform differentiability to formulate and prove the inverse function theorem for functions from Nⁿ to Nⁿ and the implicit function theorem for functions from Nⁿ to N^m with m<n.     

A functional inequality characterizing convex functions,conjugacy and a generalization of Hölder's and Minkowski's inequalities

Summary The main result says that, iff: _{+ +} satisfies the functional inequalityaf(s) + bf(t) f (as + bt) (s,t 0) for somea, b such that 0 <a < 1 <a + b, thenf(t) = f(1)t, (t 0). A relevant result for the reverse inequality is also discussed. Applying these results we determine the form of all functionsf: _k ⁺ ₊ satisying the above inequalities. This leads to a characterization of both concave and convex functions defined on ₊ ^k–1 , to a notion of conjugate functions and to a general inequality which contains Hölder's and Minkowski's inequalities as very special cases.     

On the full automorphism group of a graph

While it is easy to characterize the graphs on which a given transitive permutation groupG acts, it is very difficult to characterize the graphsX with Aut (X)=G. We prove here that for the certain transitive permutation groups a simple necessary condition is also sufficient. As a corollary we find that, whenG is ap-group with no homomorphism ontoZ _p wrZ _p , almost all Cayley graphs ofG have automorphism group isomorphic toG.     

Euler configurations and quasi-polynomial systems

Consider the problem of three point vortices (also called Helmholtz’ vortices) on a plane, with arbitrarily given vorticities. The interaction between vortices is proportional to 1/r, where r is the distance between two vortices. The problem has 2 equilateral and at most 3 collinear normalized relative equilibria. This 3 is the optimal upper bound. Our main result is that the above standard statements remain unchanged if we consider an interaction proportional to r ^b, for any b < 0. For 0 < b < 1, the optimal upper bound becomes 5. For positive vorticities and any b < 1, there are exactly 3 collinear normalized relative equilibria. The case b = −2 of this last statement is the well-known theorem due to Euler: in the Newtonian 3-body problem, for any choice of the 3 masses, there are 3 Euler configurations (also known as the 3 Euler points). These small upper bounds strengthen the belief of Kushnirenko and Khovanskii [18]: real varieties defined by simple systems should have a simple topology. We indicate some hard conjectures about the configurations of relative equilibrium and suggest they could be attacked within the quasi-polynomial framework.     

Monotone clones and the varieties they determine

A finite, nontrivial algebra is order-primal if its term functions are precisely the monotone functions for some order on the underlying set. We show that the prevariety generated by an order-primal algebra P is relatively congruence-distributive and that the variety generated by P is congruence-distributive if and only if it contains at most two non-ismorphic subdirectly irreducible algebras. We also prove that if the prevarieties generated by order-primal algebras P and Q are equivalent as categories, then the corresponding orders or their duals generate the same order variety. A large class of order-primal algebras is described each member of which generates a variety equivalent as a category to the variety determined by the six-element, bounded ordered set which is not a lattice. These results are proved by considering topological dualities with particular emphasis on the case where there is a monotone near-unanimity function.This research was carried out while the third author held a research fellowship at La Trobe University supported by ARGS grant B85154851. The second author was supported by a grant from the NSERC.     

Ordinary and strong density continuity of complex analytic functions

In the paper we prove that the complex analytic functions are (ordinarily) density continuous. This stays in contrast with the fact that even such a simple function asG:²²,G(x,y)=(x,y ³ ), is not density continuous [1]. We will also characterize those analytic functions which are strongly density continuous at the given pointa . From this we conclude that a complex analytic functionf is strongly density continuous if and only iff(z)=a+bz, wherea, b andb is either real or imaginary.     

Asymptotic expansions and acceleration of convergence for higher order iteration processes

Summary We analyze the convergence behavior of sequences of real numbers {x _n }, which are defined through an iterative process of the formx _n :=T(x _n –1), whereT is a suitable real function. It will be proved that under certain mild assumptions onT, these numbersx _n possess an asymptotic (error) expansion, where the type of this expansion depends on the derivative ofT in the limit point ; this generalizes a result of G. Meinardus [6].It is well-known that the convergence of sequences, which possess an asymptotic expansion, can be accelerated significantly by application of a suitable extrapolation process. We introduce two types of such processes and study their main properties in some detail. In addition, we analyze practical aspects of the extrapolation and present the results of some numerical tests. As we shall see, even the convergence of Newton's method can be accelerated using the very simple linear extrapolation process.Dedicated to Professor Dr. Günter Meinardus on the occasion of his 65^th birthday     

The maximal monotonicity of the subdifferentials of convex functions: Simons' problem

In the paper we deal with the problem when the graph of the subdifferential operator of a convex lower semicontinuous function has a common point with the product of two convex nonempty weak and weak^* compact sets, i.e. when graph (Q × Q ^*) 0. The results obtained partially solve the problem posed by Simons as well as generalize the Rockafellar Maximal Monotonicity Theorem.     

A new lower bound for Snake-in-the-Box Codes

In this paper we give a new lower bound on the length of Snake-in-the-Box Codes, i.e., induced cycles in thed-dmensional cube. The bound is a linear function of the number of vertices of the cube and improves the boundc·2 ^d /d, wherec is a constant, proved by Danzer and Klee.     

On profinite completions and canonical extensions

We show that if a variety V of monotone lattice expansions is finitely generated, then profinite completions agree with canonical extensions on V. The converse holds for varieties of finite type. This paper is dedicated to Walter Taylor. Received May 14, 2005; accepted in final form September 8, 2005.     

Small Complete Arcs in Projective Planes

In the late 1950s, B. Segre introduced the fundamental notion of arcs and complete arcs [48,49]. An arc in a nite projective plane is a set of points with no three on a line and it is complete if cannot be extended without violating this property. Given a projective plane , determining , the size of its smallest complete arc, has been a major open question in finite geometry for several decades. Assume that has order q, it was shown by Lunelli and Sce [41], more than 40 years ago, that . Apart from this bound, practically nothing was known about , except for the case is the Galois plane. For this case, the best upper bound, prior to this paper, was O(q ^3/4) obtained by Sznyi using the properties of the Galois field GF(q).In this paper, we prove that for any projective plane of order q, where c is a universal constant. Together with Lunelli-Sces lower bound, our result determines up to a polylogarithmic factor. Our proof uses a probabilistic method known as the dynamic random construction or Rödls nibble. The proof also gives a quick randomized algorithm which produces a small complete arc with high probability.The key ingredient of our proof is a new concentration result, which applies for non-Lipschitz functions and is of independent interest.* Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship.Part of this work was done at AT&T Bell Labs and Microsoft Research