Edge-Directions of Standard Polyhedra with Applications to Network Flows

Recent results show that edge-directions of polyhedra play an important role in (combinatorial) optimization; in particular, a d-dimensional polyhedron with |D| distinct edge-directions has at most O(|D|^d-1) vertices. Here, we obtain a characterization of the directions of edges that are adjacent to a given vertex of a standard polyhedron of the form P = {x : Ax = b, l⩽ x⩽ u, tightening a standard necessary condition which asserts that such directions must be minimal support solutions of the homogenous equation Ax = 0 which are feasible at the given vertex. We specialize the characterization for polyhedra that correspond to network flows, obtaining a graph characterization of circuits which correspond to edge-directions. Applications to partitioning polyhedra are discussed. Research of these authors was supported by a grant from ISF – the Israel Science Foundation, by a VPR grant at the Technion, and by the Fund for the Promotion of Research at the Technion.     

Brauer groups,embedding problems,and nilpotent groups as Galois groups

Let ℚ _ab denote the maximal abelian extension of the rationals ℚ, and let ℚ_abnil denote the maximal nilpotent extension of ℚ _ab . We prove that for every primep, the free pro-p group on countably many generators is realizable as the Galois group of a regular extension of ℚ_abnil(t). We also prove that ℚ_abnil is not PAC (pseudo-algebraically closed). This paper was inspired by the author's participation in a special year on the arithmetic of fields at the Institute for Advanced Studies at the Hebrew University of Jerusalem. I would like to express my appreciation to the Institute for its hospitality, and to the organizers, especially Moshe Jarden. Partially supported by the Fund for the Promotion of Research at the Technion and by the Technion VPR Fund-Japan Technion Society Research Fund.     

Carathéodory balls and norm balls inH n ={z ε ℂ n : ‖z‖1<1}

It is shown that the only balls in the Carathéodory distance onH _n ={z ε ℂ ⁿ :‖z‖₁<1},n≥2, which are balls with respect to the ℓ₁ norm in ℂ ⁿ are those centered at the origin. In memory of Albert Pfluger The research was partially supported by the Fund for the Promotion of Research at the Technion.     

Strongly perfect infinite graphs

An infinite graph G is calledstrongly perfect if each induced subgraph ofG has a coloring (C _i :i ∈I) and a clique meeting each colorC _i . A conjecture of the first author and V. Korman is that a perfect graph with no infinite independent set is strongly perfect. We prove the conjecture for chordal graphs and for their complements. The research was begun at the Sonderforschungsbereich 343 at Bielefeld University and supported by the Fund for the Promotion of Research at the Technion.     

Universal WCG banach spaces and universal Eberlein Compacts

We prove that for cardinalsτ satisfying τ^ω=τ and forτ=ω ₁, there do not exist universal Eberlein Compacts of weightτ, or universal WCG spaces of density characterτ. Ifτ is a strong limit cardinal of countable cofinality such universal spaces do exist. Thus under GCH universal spaces exist forτ iff cof(τ)=ω. The research of the second author was supported by a grant from the United States-Israel Binational Science Foundation and the Fund for the Promotion of Research at the Technion.     

Second order optimality conditions for theL 1-minimization problem

In this paper we establish necessary and sufficient second order optimality conditions for theL ₁-problem. The approach is based on optimality criteria in terms of a curved second directional derivative, discussed in [3]. Our conditions generalize conditions for theL ₁-problem given in [6]. An example demonstrates the usefulness of our criteria.This research was supported by NSF Grant No. ECS-8214081 and the Fund for Promotion of Research at the Technion, andDeutsche Forschungsgemeinschaft.     

Singularities and bifurcations of 3-dimensional Poisson structures

We give a normal form for families of 3-dimensional Poisson structures. This allows us to classify singularities with nonzero 1-jet and typical bifurcations. The Appendix contains corollaries on classification of families of integrable 1-forms on ℝ³. Zhitomirskii’s research was supported by the Fund for the Promotion of Research at the Technion.     

A geometrical property ofC(K) spaces

We introduce a geometrical property of norm one complemented subspaces ofC(K) spaces which is useful for computing lower bounds on the norms of projections onto subspaces ofC(K) spaces. Loosely speaking, in the dual of such a space ifx* is a w* limit of a net (x _a ^* ) andx*=x*₁+x*₂ with ‖x*‖=‖x*₁‖ + ‖x*₂‖, then we measure how efficiently thex _a ^* 's can be split into two nets converging tox*₁ andx*₂, respectively. As applications of this idea we prove that if for everyε>0,X is a norm (1+ε) complemented subspace of aC(K) space, then it is norm one complemented in someC(K) space, and we give a simpler proof that a slight modification of anl ₁-predual constructed by Benyamini and Lindenstrauss is not complemented in anyC(K) space. Research partially supported by a grant of the U.S.-Israel Binational Science Foundation. Research of the first-named author is supported in part by NSF grant DMS-8602395. Research of the second-named author was partially supported by the Fund for the Promotion of Research at the Technion, and by the Technion VPR-New York Metropolitan Research Fund.     

Boundary Harnack Principle for <Emphasis Type="Italic">p</Emphasis>-harmonic Functions in Smooth Euclidean Domains

We establish a scale-invariant version of the boundary Harnack principle for p-harmonic functions in Euclidean C ^1,1-domains and obtain estimates for the decay rates of positive p-harmonic functions vanishing on a segment of the boundary in terms of the distance to the boundary. We use these estimates to study the behavior of conformal Martin kernel functions and positive p-superharmonic functions near the boundary of the domain. H. A. was partially supported by Grant-in-Aid for (B) (2) (No. 15340046) Japan Society for the Promotion of Science. N. S. was partially supported by NSF grant DMS-0355027. X. Z. was partially supported by the Taft foundation.     

Optimal partitions having disjoint convex and conic hulls

LetA ¹,,A ⁿ be distinctk-dimensional vectors. We consider the problem of partitioning these vectors intom sets so as to maximize an objective which is a quasi-convex function of the sum of vectors in each set. We show that there exists an optimal partition whose sets have (pairwise) disjoint conic hulls. We also show that if the number of vectors in each of the sets is constrained, then a weaker conclusion holds, namely, there exists an optimal partition whose sets have (pairwise) disjoint convex hulls. The results rely on deriving necessary and sufficient conditions for a point to be an extreme point of a corresponding polytope.Research of this author was partially supported by NSF Grant ECS-83-10213 and by a Grant for the Promotion of Research at the Technion.     

Q-admissibility of certain nonsolvable groups

A finite groupG is calledQ-admissible if there exists a finite dimensional central division algebra overQ, containing a maximal subfield which is a Galois extension ofQ with Galois group isomorphic toG. It is proved thatS ₅ ⁻ , one of the two nontrivial central extensions ofS ₅ byZ/2Z, isQ-admissible. As a consequence of that result and previous results of Sonn and Stern, every finite Sylow-metacyclic group, havingA ₅ as a composition factor, isQ-admissible. This paper is part of a M.Sc. thesis written at the Technion — Israel Institute of Technology, under the supervision of Professor J. Sonn, whom the author wishes to thank for his valuable guidance.     

The zeros of functions in Nevanlinna’s area class

Let {Z_n=1{( _n ^∓ ) bea sequence of points in the unit open disk, and letNϕ(U) denote the class of functionsf analytic in the unit disk U such that |f|∈L ( _ϕ ¹ )(U). For ϕ ≡ 1, the necessary and sufficient conditions for the existence off εN(U) and vanishing atz _n is Σ( _n=1 ^∓ ) (1–|Z_n|)² ∞. Also we estimate a large family of canonical products. These results are extended to ϕ(z)=(1-|z|)^ϕ. This represents a part of a Ph.D. thesis conducted at the Technion — Israel Institute of Technology, Department of Mathematics, by Dr. C. A. Horowitz. His help during the preparation of this paper is gratefully acknowledged.     

Adjustable robust solutions of uncertain linear programs

We consider linear programs with uncertain parameters, lying in some prescribed uncertainty set, where part of the variables must be determined before the realization of the uncertain parameters (``non-adjustable variables'), while the other part are variables that can be chosen after the realization (``adjustable variables'). We extend the Robust Optimization methodology ([1, 3-6, 9, 13, 14]) to this situation by introducing the Adjustable Robust Counterpart (ARC) associated with an LP of the above structure. Often the ARC is significantly less conservative than the usual Robust Counterpart (RC), however, in most cases the ARC is computationally intractable (NP-hard). This difficulty is addressed by restricting the adjustable variables to be affine functions of the uncertain data. The ensuing Affinely Adjustable Robust Counterpart (AARC) problem is then shown to be, in certain important cases, equivalent to a tractable optimization problem (typically an LP or a Semidefinite problem), and in other cases, having a tight approximation which is tractable. The AARC approach is illustrated by applying it to a multi-stage inventory management problem.Research was partially supported by the Israeli Ministry of Science grant #0200-1-98, the Israel Science Foundation founded by The Israel Academy of Sciences and Humanities, grant #683/99-10.0, and the Fund for Promotion of Research at the Technion.     

Majorization of Gaussian processes and geometric applications

Summary Let (x _i ^* ) _i=1 ⁿ denote the decreasing rearrangement of a sequence of real numbers (x _i ) _i=1 ⁿ . Then for everyij, and every 1kn, the 2-nd order partial distributional derivatives satisfy the inequality, . As a consequence we generalize the theorem due to Fernique and Sudakov. A generalization of Slepian's lemma is also a consequence of another differential inequality. We also derive a new proof and generalizations to volume estimates of intersecting spheres and balls in ⁿ proved by Gromov.Supported by NSF grant # DMS 8909745, and the USA-Israel Binational Science Foundation grant # 86-00074, and grant for the Promotion of Research at the Technion     

A remark on almost extensions of lipschitz functions

We present a simpler proof of a result of J. Bourgain on almost extensions of functions satisfying a Lipschitz condition onδ-nets. This is part of the author’s Master Thesis written at the Technion — Israel Institute of Technology, under the supervision of Prof. Yoav Benyamini.     

Perturbation Analysis for the Eigenvalue Problem of a Formal Product of Matrices

We study the perturbation theory for the eigenvalue problem of a formal matrix product A ₁ ^{s 1} ··· A _p ^{s p}, where all A _k are square and s _k {–1, 1}. We generalize the classical perturbation results for matrices and matrix pencils to perturbation results for generalized deflating subspaces and eigenvalues of such formal matrix products. As an application we then extend the structured perturbation theory for the eigenvalue problem of Hamiltonian matrices to Hamiltonian/skew-Hamiltonian pencils.     

Independent systems of representatives in weighted graphs

The following conjecture may have never been explicitly stated, but seems to have been floating around: if the vertex set of a graph with maximal degree Δ is partitioned into sets V _i of size 2Δ, then there exists a coloring of the graph by 2Δ colors, where each color class meets each V _i at precisely one vertex. We shall name it the strong 2Δ-colorability conjecture. We prove a fractional version of this conjecture. For this purpose, we prove a weighted generalization of a theorem of Haxell, on independent systems of representatives (ISR’s). En route, we give a survey of some recent developments in the theory of ISR’s. The research of the first author was supported by grant no 780/04 from the Israel Science Foundation, and grants from the M. & M. L. Bank Mathematics Research Fund and the fund for the promotion of research at the Technion. The research of the third author was supported by the Sacta-Rashi Foundation.     

Evasion and prediction

 Say that a function π:n ^<ω →n (henceforth called a predictor) k-constantly predicts a real xn ^ω if for almost all intervals I of length k, there is iI such that x(i)=π(x↾i). We study the k-constant prediction number v _n ^const (k), that is, the size of the least family of predictors needed to k-constantly predict all reals, for different values of n and k, and investigate their relationship. Received: 27 June 2001 / Revised version: 10 September 2001 / Published online: 10 October 2002 RID="*" ID="*" Supported by Grant–in–Aid for Scientific Research (C)(2)12640124, Japan Society for the Promotion of Science RID="†" ID="†" Supported by The Israel Science Foundation founded by the Israel Academy of Sciences and Humanities. Publication 762     

A Julia-Carathéodory theorem for hyperbolically monotone mappings in the Hilbert ball

We establish a Julia-Carathéodory theorem and a boundary Schwarz-Wolff lemma for hyperbolically monotone mappings in the open unit ball of a complex Hilbert space. The second author was partially supported by the Fund for the Promotion of Research at the Technion and by the Technion VPR Fund-B. and G. Greenberg Research Fund (Ottawa).     

Boundary Behavior of Harmonic Functions for Truncated Stable Processes

For any α∈(0,2), a truncated symmetric α-stable process in ℝ ^d is a symmetric Lévy process in ℝ ^d with no diffusion part and with a Lévy density given by c|x|^−d−α 1_{|x|<1} for some constant c. In (Kim and Song in Math. Z. 256(1): 139–173, [2007]) we have studied the potential theory of truncated symmetric stable processes. Among other things, we proved that the boundary Harnack principle is valid for the positive harmonic functions of this process in any bounded convex domain and showed that the Martin boundary of any bounded convex domain with respect to this process is the same as the Euclidean boundary. However, for truncated symmetric stable processes, the boundary Harnack principle is not valid in non-convex domains. In this paper, we show that, for a large class of not necessarily convex bounded open sets in ℝ ^d called bounded roughly connected κ-fat open sets (including bounded non-convex κ-fat domains), the Martin boundary with respect to any truncated symmetric stable process is still the same as the Euclidean boundary. We also show that, for truncated symmetric stable processes a relative Fatou type theorem is true in bounded roughly connected κ-fat open sets. The research of P. Kim is supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) (KRF-2007-331-C00037). The research of R. Song is supported in part by a joint US-Croatia grant INT 0302167.