Infinite ordered sets spanned by finitely many chains

We say that an ordered set P is spanned by a family C of chains if P=(P, ) is the transitive closure of {(C, | C) C C. It is shown that there is a function h: such that if P is spanned by k< chains, then P has a finite cutset-number h(k) (i.e. for any xP, there is a finite set F of size |F|h(k)–1, such that the elements of F are incomparable with x and {x}F meets every maximal chain of P). The function h is exponentially bounded but eventually dominates any polynomial function, even if it is only required that there are at most h(k) pairwise disjoint maximal chains in P, whenever P is spanned by k< chains.     

There are only finitely many finite distance-transitive graphs of given valency greater than two

The result of the title is proved, assuming the truth of Sims’ conjecture on primitive permutation groups (which has recently been established using the classification of finite simple groups). An alternative approach to this result, using less group theory but relying on a theorem of Macpherson on infinite distance-transitive graphs, is explored.     

Geradenanordnungen Mit Maximaler Anzahl Vierseitiger Flächen

Ohne Zusammenfassung

---

     

Kinematic formulas for finite lattices

In analogy to valuation characterizations and kinematic formulas of convex geometry, we develop a combinatorial theory of invariant valuations and kinematic formulas for finite lattices. Combinatorial kinematic formulas are shown to have application to some probabilistic questions, leading in turn to polynomial identities for Möbius functions and Whitney numbers.     

Sets associated with the farthest point problem

LetS be a convex compact set in a normed linear spaceX. For each cardinal numbern, defineS _n = {x X:x has exactlyn farthest points inS} andT _n = _kn S _k. It is shown that ifX =E thenT ₃ is countable andT ₂ is contractible to a point. Properties of associated level curves are given.     

Ideal convergent subseries in Banach spaces

Abstract

Assume that is an ideal on ?, and ∑_n x_n is a divergent series in a Banach space X. We study the Baire category, and the measure of the set A() := {t ∈ {0, 1}^?: ∑_n t(n)x_n is -convergent}. In the category case, we assume that has the Baire property and ∑_n x_n is not unconditionally convergent, and we deduce that A() is meager. We also study the smallness of A() in the measure case when the Haar probability measure λ on {0, 1}^? is considered. If is analytic or coanalytic, and ∑_n x_n is -divergent, then λ(A()) = 0 which extends the theorem of Dindo?, ?alát and Toma. Generalizing one of their examples, we show that, for every ideal on ?, with the property of long intervals, there is a divergent series of reals such that λ(A(Fin)) = 0 and λ(A()) = 1.     

Convex bodies with extremal volumes having prescribed brightness in finitely many directions

We consider the class of convex bodies in ⁿ with prescribed projection (n – 1)-volumes along finitely many fixed directions. We prove that in such a class there exists a unique body (up to translation) with maximumn-volume. The maximizer is a centrally symmetric polytope and the normal vectors to its facets depend only on the assigned directions.Conditions for the existence of bodies with minimumn-volume in the class defined above are given. Each minimizer is a polytope, and an upper bound for the number of its facets is established.Work partially supported by Istituto di Analisi Globale e Applicazioni, CNR, Firenze.     

The number of edges of many faces in a line segment arrangement

We show that the maximum number of edges boundingm faces in an arrangement ofn line segments in the plane isO(m ^2/3 n ^2/3+n(n)+nlogm). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is (m ^2/3 n ^2/3+n(n)). In addition, we show that the number of edges bounding anym faces in an arrangement ofn line segments with a total oft intersecting pairs isO(m ^2/3 t ^1/3+n(t/n)+nmin{logm,logt/n}), almost matching the lower bound of (m ^2/3 t ^1/3+n(t/n)) demonstrated in this paper.Work on this paper by the first and fourth authors has been partially supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484. Work by the first author has also been supported by an AT&T Bell Laboratories Ph.D. scholarship at New York University and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center (NSF-STC88-09648). Work by the second author has been supported by NSF under Grants CCR-87-14565 and CCR-89-21421. Work by the fourth author has additionally been supported by grants from the U.S.-Israeli Binational Science Foundation, the NCRD (the Israeli National Council for Research and Development) and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli National Academy of Sciences.     

Strong convergence theorems for finitely many nonexpansive mappings

Under the assumption that E$E$ is a reflexive Banach space whose norm is uniformly Gêteaux differentiable and which has a weakly continuous duality mapping _Jφ$J_{\phi }$ with gauge function φ$\phi$, Ceng–Cubiotti–Yao [Strong convergence theorems for finitely many nonexpansive mappings and applications, Nonlinear Analysis 67 (2007) 1464–1473] introduced a new iterative scheme for a finite commuting family of nonexpansive mappings, and proved strong convergence theorems about this iteration. In this paper, only under the hypothesis that E$E$ is a reflexive Banach space which has a weakly continuous duality mapping _Jφ$J_{\phi }$ with gauge function φ$\phi$, and several control conditions about the iterative coefficient are removed, we present a short and simple proof of the above theorem.     

Krasnosel'skii numbers for bounded finitely starlike sets inR d

For eachk andd, 1kd, definef(d, d)=d+1 andf(d, k)=2d if 1kd–1. The following results are established:Let be a uniformly bounded collection of compact, convex sets inR ^d . For a fixedk, 1kd, dim {MM in }k if and only if for some > 0, everyf(d, k) members of contain a commonk-dimensional set of measure (volume) at least.LetS be a bounded subset ofR ^d . Assume that for some fixedk, 1kd, there exists a countable family of (k–l)-flats {H _i :i1} inR ^d such that clS S {H_i i 1 } and for eachi1, (clS S) H _i has (k–1) dimensional measure zero. Every finite subset ofS sees viaS a set of positivek-dimensional measure if and only if for some>0, everyf(d,k) points ofS see viaS a set ofk-dimensional measure at least .The numbers off(d,d) andf(d, 1) above are best possible.Supported in part by NSF grant DMS-8705336.     

There are uncountably many universal topological planes

We prove the existence of uncountably many nonisomorphic topological projective planes, each universal in the sense that it contains an isomorphic copy of every pseudoline arrangement.     

Some Krasnosel'skii numbers for finitely starlike sets in the plane

Let S be a subset of the plane. In case (int cl S) S = , then S is finitely starlike if and only if every 4 points of S see via S a common point. In case (int cl S) S has at most countably many components, each a singleton set, then S is finitely starlike if and only if every 5 points of S see via S a common point. Each of the numbers 4 and 5 is best possible. Examples show that these results fail without suitable restrictions on (int cl S) S. Moreover, a final example shows that if a general Krasnosel'skii number . exists to characterize finitely starlike sets in the plane, then > 9.     

Pairs of edge-disjoint Hamiltonian circuits

Aequationes mathematicae -     

The solution of graham’s greatest common divisor problem

The following conjecture of R. L. Graham is verified: Ifn≧n ₀, wheren ₀ is an explicitly computable constant, then for anyn distinct positive integersa ₁,a ₂, ...,a _n we have a _i /(a _i ,a _j ) ≧ ≧n, and equality holds only in two trivial cases. Here (a _i ,a _j ) stands for the greatest cnmmon divisor ofa _i anda _j .     

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.     

The hypermetric cone is polyhedral

The hypermetric coneH _n is the cone in the spaceR ^n(n–1)/2 of all vectorsd=(d _ij)_1i<jn satisfying the hypermetric inequalities: –_1ijn z _j z _j d _ij 0 for all integer vectorsz inZ ⁿ with –_1in z _i =1. We explore connections of the hypermetric cone with quadratic forms and the geometry of numbers (empty spheres andL-polytopes in lattices). As an application, we show that the hypermetric coneH _n is polyhedral.     

The necessary condition for the discrete L0-Minkowski problem in {mathbb{R}}^{2}

We prove that the sufficiency condition employed to show the existence and, in certain cases the uniqueness, of solutions to the discrete, planar L ₀-Minkowski problem with data containing, at least, a pair of opposite vectors is also a necessary condition.      

Path-closed sets

Given a digraphG = (V, E), call a node setT ⊆V path-closed ifv, v′ εT andw εV is on a path fromv tov′ impliesw εT. IfG is the comparability graph of a posetP, the path-closed sets ofG are the convex sets ofP. We characterize the convex hull of (the incidence vectors of) all path-closed sets ofG and its antiblocking polyhedron inR ^v , using lattice polyhedra, and give a minmax theorem on partitioning a given subset ofV into path-closed sets. We then derive good algorithms for the linear programs associated to the convex hull, solving the problem of finding a path-closed set of maximum weight sum, and prove another min-max result closely resembling Dilworth’s theorem.     

Convexly independent sets

A family of pairwise disjoint compact convex sets is called convexly independent, if none of its members is contained in the convex hull of the union of the other members of the family. The main result of the paper gives an upper bound for the maximum cardinalityh(k, n) of a family of mutually disjoint compact convex sets such that any subfamily of at mostk members of is convexly independent, but no subfamily of sizen is.