An augmenting path algorithm for linear matroid parity

Linear matroid parity generalizes matroid intersection and graph matching (and hence network flow, degree-constrained subgraphs, etc.). A polynomial algorithm was given by Lovász. This paper presents an algorithm that uses timeO(mn ³), wherem is the number of elements andn is the rank. (The time isO(mn ^2.5) using fast matrix multiplication; both bounds assume the uniform cost model). For graphic matroids the time isO(mn ²). The algorithm is based on the method of augmenting paths used in the algorithms for all subcases of the problem. First author was supported in part by the National Science Foundation under grants MCS 78-18909, MCS-8302648, and DCR-8511991. The research was done while the second author was at the University of Denver and at the University of Colorado at Boulder.     

How to Cut Pseudoparabolas into Segments

Let Γ be a collection of unbounded x -monotone Jordan arcs intersecting at most twice each other, which we call pseudoparabolas, since two axis parallel parabolas intersect at most twice. We investigate how to cut pseudoparabolas into the minimum number of curve segments so that each pair of segments intersect at most once. We give an Ω( n ^4/3 ) lower bound and O(n ^5/3 ) upper bound on the number of cuts. We give the same bounds for an arrangement of circles. Applying the upper bound, we give an O(n ^23/12 ) bound on the complexity of a level in an arrangement of pseudoparabolas, and an O(n ^11/6 ) bound on the complexity of a combinatorially concave chain of pseudoparabolas. We also give some upper bounds on the number of transitions of the minimum weight matroid base when the weight of each element changes as a quadratic function of a single parameter. Received January 17, 1996, and in revised form November 7, 1996.     

Two constructions of oriented matroids with disconnected extension space

The extension space ℰ(ℳ) of an oriented matroid ℳ is the poset of all one-element extensions of ℳ, considered as a simplicial complex. We present two different constructions leading to rank 4 oriented matroids with disconnected extension space. We prove especially that if an elementf is not contained in any mutation of a rank 4 oriented matroid ℳ, then ℰ(ℳ\f) contains an isolated point. A uniform nonrealizable arrangement of pseudoplanes with this property is presented. The examples described contrast results of Sturmfels and Ziegler [12] who proved that for rank 3 oriented matroids the extension space has the homotopy type of the 2-sphere.     

The monotone circuit complexity of boolean functions

Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of sizes in a graphm vertices requires monotone circuits of size Ω(m ^s /(logm)^2s ) for fixeds, and sizem ^Ω(logm) form/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/logm)^2/3 requires monotone circuits exp (Ω((m/logm)^1/3)). For fixeds, any monotone circuit that detects cliques of sizes requiresm) ^s ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function ofn variables is exp (Ω(n ^1/4 · (logn)^1/2)), improving a recent result of exp (Ω(n ^1/8-ε)) due to Andreev. First author supported in part by Allon Fellowship, by Bat Sheva de-Rotschild Foundation by the Fund for basic research administered by the Israel Academy of Sciences. Second author supported in part by a National Science Foundation Graduate Fellowship.     

On the complexity of a single cell in certain arrangements of surfaces related to motion planning

We obtain near-quadratic upper bounds on the maximum combinatorial complexity of a single cell in certain arrangements ofn surfaces in 3-space where the lower bound for this quantity is Ω(n ²) or slightly larger. We prove a theorem that identifies a collection of topological and combinatorial conditions for a set of surface patches in space, which make the complexity of a single cell in an arrangement induced by these surface patches near-quadratic. We apply this result to arrangements related to motion-planning problems of two types of robot systems with three degrees of freedom and also to a special type of arrangements of triangles in space. The complexity of the entire arrangement in each case that we study can be Θ(n ³) in the worst case, and our single-cell bounds are of the formO(n ² α(n)), O(n ² logn), orO(n ² α(n)logn). The only previously known similar bounds are for the considerably simpler arrangements of planes or of spheres in space, where the bounds are Θ(n) and Θ(n ²), respectively. For some of the arrangements that we study we derive near-quadratic-time algorithms to compute a single cell. A preliminary version of this paper has appeared inProc. 7th ACM Symposium on Computational Geometry, North Conway, NH, 1991, pp. 314–323.     

On Maximum-sized k-Regular Matroids

 Let k be an integer exceeding one. The class of k-regular matroids is a generalization of the classes of regular and near-regular matroids. A simple rank-r regular matroid has the maximum number of points if and only if it is isomorphic to M(K _r+1), the cycle matroid of the complete graph on r+1 vertices. A simple rank-r near-regular matroid has the maximum number of points if and only if it is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding a point to a 3-point line of M(K _r+2) and then contracting this point. This paper determines the maximum number of points that a simple rank-r k-regular matroid can have and determines all such matroids having this number. With one exception, there is exactly one such matroid. This matroid is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding k independent points to a flat of M(K _r+k+1) isomorphic to M(K _k+2) and then contracting each of these points. Revised: July 27, 1998     

A Trace Bound for the Hereditary Discrepancy

Let A be the incidence matrix of a set system with m sets and n points, m ≤ n , and let t= \mathop \rm tr M , where M= A ^T A . Finally, let σ = \mathop \rm tr M ² be the sum of squares of the elements of M . We prove that the hereditary discrepancy of the set system is at least . This general trace bound allows us to resolve discrepancy-type questions for which spectral methods had previously failed. Also, by using this result in conjunction with the spectral lemma for linear circuits, we derive new complexity bounds for range searching. We show that the (red—blue) discrepancy of the set system formed by n points and n lines in the plane is Ω(n ^1/6 ) in the worst case and always ¹ \tilde O(n ^1/6 ) . We give a simple explicit construction of n points and n halfplanes with hereditary discrepancy \tildeΩ(n ^1/4 ) . We show that in any dimension d= Ω( log n/\kern -1ptlog log n ) , there is a set system of n points and n axis-parallel boxes in \bf R ^d with discrepancy n ^{Ω(1/\kern -1pt log log n)} . Applying these discrepancy results together with a new variation of the spectral lemma, we derive a lower bound of Ω(nlog n) on the arithmetic complexity of off-line range searching for points and lines (for nonmonotone circuits). We also prove a lower bound of Ω(nlog n/\kern -1ptlog log n) on the complexity of orthogonal range searching in any dimension Ω(log n/\kern -1ptlog log n) . ¹ We use the notation \tilde O(m) and \tilde Ω(m) as shorthand for O(mlog ^c m) and Ω(m/\kern -1ptlog ^c m) , respectively, for some constant c>0 . Received April 5, 2000, and in revised form October 17, 2000. Online publication June 22, 2001.     

Lower bounds for off-line range searching

This paper proves three lower bounds for variants of the following rangesearching problem: Given n weighted points inR ^d andn axis-parallel boxes, compute the sum of the weights within each box: (1) if both additions and subtractions are allowed, we prove that Ω(n log logn) is a lower bound on the number of arithmetic operations; (2) if subtractions are disallowed the lower bound becomes Ω(n(logn/loglogn)^d-1), which is nearly optimal; (3) finally, for the case where boxes are replaced by simplices, we establish a quasi-optimal lower bound of Ω(n^2-2/(d+1))/polylog(n). A preliminary version of this paper appeared inProc. 27th Ann. ACM Symp. on Theory of Computing, May 1995, pp. 733–740. This work was supported in part by NSF Grant CCR-93-01254 and the Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc.     

Well-posedness and sharp uniform decay rates at the L 2(Ω)-Level of the Schrödinger equation with nonlinear boundary dissipation

We prove that the Schr?dinger equation defined on a bounded open domain of and subject to a certain attractive, nonlinear, dissipative boundary feedback is (semigroup) well-posed on L₂(Ω) for any n = 1, 2, 3, ..., and, moreover, stable on L₂(Ω) for n = 2, 3, with sharp (optimal) uniform rates of decay. Uniformity is with respect to all initial conditions contained in a given L₂(Ω)-ball. This result generalizes the corresponding linear case which was proved recently in [L-T-Z.2]. Both results critically rely—at the outset—on a far general result of interest in its own right: an energy estimate at the L₂(Ω)-level for a fully general Schr?dinger equation with gradient and potential terms. The latter requires a heavy use of pseudo-differential/micro-local machinery [L-T-Z.2, Section 10], to shift down the more natural H¹(Ω)-level energy estimate to the L₂(Ω)-level. In the present nonlinear boundary dissipation case, the resulting energy estimate is then shown to fit into the general uniform stabilization strategy, first proposed in [La-Ta.1] in the case of wave equations with nonlinear (interior and) boundary dissipation.     

Eigenvalues Estimate for the Neumann Problem of a Bounded Domain

In this note, we investigate upper bounds of the Neumann eigenvalue problem for the Laplacian of a domain Ω in a given complete (not compact a priori) Riemannian manifold (M,g). For this, we use test functions for the Rayleigh quotient subordinated to a family of open sets constructed in a general metric way, interesting for itself. As applications, we prove that if the Ricci curvature of (M,g) is bounded below Ric  ^g ≥−(n−1)a ², a≥0, then there exist constants A _n >0,B _n >0 only depending on the dimension, such that

On K s -free subgraphs in K s+k -free graphs and vertex Folkman numbers

Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers 2 ≤ s < t let f _s,t (n) = min{max{|S|: S ⊆ V (H) and H[S] contains no K _s }}, where the minimum is taken over all K _t -free graphs H of order n. This function attracted a considerable amount of attention but despite that, the gap between the lower and upper bounds is still fairly wide. For example, when t=s+1, the best bounds have been of the form Ω(n ^1/2+o(1)) ≤ f _s,s+1(n) ≤ O(n ^1−ɛ(s)), where ɛ(s) tends to zero as s tends to infinity. In this paper we improve the upper bound by showing that f _s,s+1(n) ≤ O(n ^2/3). Moreover, we show that for every ɛ > 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n ^1/2−ɛ ) ≤ f _s,s+k (n) ≤ O(n ^1/2+ɛ . In addition, we also discuss some connections between the function f _s,t and vertex Folkman numbers.     

Multigrid methods for the computation of singular solutions and stress intensity factors II: Crack singularities

We consider the Poisson equation −Δu=f with homogeneous Dirichlet boundary condition on a two-dimensional polygonal domain Ω with cracks. Multigrid methods for the computation of singular solutions and stress intensity factors using piecewise linear functions are analyzed. The convergence rate for the stress intensity factors is whenfεL ²(Ω) and whenfεH ¹(Ω). The convergence rate in the energy norm is in the first case and in the second case. The costs of these multigrid methods are proportional to the number of elements in the triangulation. The general case wherefεH ^m (Ω) is also discussed. The work of the first author was partially supported by NSF under grant DMS-96-00133     

Potential space estimates in local Hardy spaces for Green potentials in convex domains

Let Ω be a bounded co.nvex domain in Rn(n≥3) and G(x,y) be the Green function of the Laplace operator -△ on Ω. Let hrp(Ω) = {f ∈ D'(Ω) :(E)F∈hp(Rn), s.t. F|Ω = f}, by the atom characterization of Local Hardy spaces in a bounded Lipschitz domain, the bound of f→(△)2(Gf) for every f ∈ hrp(Ω) is obtained, where n/(n 1)＜p≤1.     

Torsion in Boundary Coinvariants and K -Theory for Affine Buildings

Let (G, I, N, S) be an affine topological Tits system, and let Γ be a torsion-free cocompact lattice in G. This article studies the coinvariants H ₀(Γ; C(Ω,Z)), where Ω is the Furstenberg boundary of G. It is shown that the class [1] of the identity function in H ₀(Γ; C(Ω, Z)) has finite order, with explicit bounds for the order. A similar statement applies to the K ₀ group of the boundary crossed product C ^*-algebra C(Ω)Γ. If the Tits system has type ? ₂, exact computations are given, both for the crossed product algebra and for the reduced group C ^*-algebra.     

D p spaces on bounded symmetric domains ofC n

In this paper, the spaceD ^p(Ω) of functions holomorphic on bounded symmetric domain ofC ⁿ is defined. We prove thatH ^p(Ω)⊂D ^p(Ω) if 0<p≤2, andD ^p(Ω)⊂H ^p(Ω) ifp≥2, and both the inclusions are proper. Further, we find that some theorems onH ^p(Ω) can be extended to a wider classD ^p(Ω) for 0<p≤2.     

Approximation in weighted Hardy spaces

This paper is concerned with several approximation problems in the weighted Hardy spacesH ^p(Ω) of analytic functions in the open unit disc D of the complex plane ℂ. We prove that ifX is a relatively closed subset of D, the class of uniform limits onX of functions inH ^p(Ω) coincides, moduloH ^p(Ω), with the space of uniformly continuous functions on a certain hull ofX which are holomorphic on its interior. We also solve the simultaneous approximation problems of describing Farrell and Mergelyan sets forH ^p(Ω), giving geometric characterizations for them. By replacing approximating polynomials by polynomial multipliers of outer functions, our results lead to characterizations of the same sets with respect to cyclic vectors in the classical Hardy spacesH ^p(D), 1 ⪯p < ∞. Dedicated to Professor Nácere Hayek on the occasion of his 75th birthday.     

Polytopal and nonpolytopal spheres an algorithmic approach

The convexity theory for oriented matroids, first developed by Las Vergnas [17], provides the framework for a new computational approach to the Steinitz problem [13]. We describe an algorithm which, for a given combinatorial (d − 2)-sphereS withn vertices, determines the setC _d,n(S) of rankd oriented matroids withn points and face latticeS. SinceS is polytopal if and only if there is a realizableM εC _d,n(S), this method together with the coordinatizability test for oriented matroids in [10] yields a decision procedure for the polytopality of a large class of spheres. As main new result we prove that there exist 431 combinatorial types of neighborly 5-polytopes with 10 vertices by establishing coordinates for 98 “doubted polytopes” in the classification of Altshuler [1]. We show that for alln ≧k + 5 ≧8 there exist simplicialk-spheres withn vertices which are non-polytopal due to the simple fact that they fail to be matroid spheres. On the other hand, we show that the 3-sphereM ₉₆₃ ⁹ with 9 vertices in [2] is the smallest non-polytopal matroid sphere, and non-polytopal matroidk-spheres withn vertices exist for alln ≧k + 6 ≧ 9.     

Better lower bounds on detecting affine and spherical degeneracies

We show that in the worst case, Ω(n ^d ) sidedness queries are required to determine whether a set ofn points in ℝ ^d is affinely degenerate, i.e., whether it containsd+1 points on a common hyperplane. This matches known upper bounds. We give a straightforward adversary argument, based on the explicit construction of a point set containing Ω(n ^d ) “collapsible” simplices, any one of which can be made degenerate without changing the orientation of any other simplex. As an immediate corollary, we have an Ω(n ^d ) lower bound on the number of sidedness queries required to determine the order type of a set ofn points in ℝ ^d . Using similar techniques, we also show that Ω(n ^d+1) in-sphere queries are required to decide the existence of spherical degeneracies in a set ofn points in ℝ ^d . An earlier version of this paper was presented at the 34th Annual IEEE Symposium on Foundations of Computer Science [8]. This research has been supported by NSF Presidential Young Investigator Grant CCR-9058440.     

Cyclotomic and simplicial matroids

We show that two naturally occurring matroids representable over ℚ are equal: thecyclotomic matroid μ_n represented by then ^th roots of unity 1, ζ, ζ², …, ζ^n-1 inside the cyclotomic extension ℚ(ζ), and a direct sum of copies of a certain simplicial matroid, considered originally by Bolker in the context of transportation polytopes. A result of Adin leads to an upper bound for the number of ℚ-bases for ℚ(ζ) among then ^th roots of unity, which is tight if and only ifn has at most two odd prime factors. In addition, we study the Tutte polynomial of μ_n in the case thatn has two prime factors. First author supported by NSF Postdoctoral Fellowship. Second author supported by NSF grant DMS-0245379.     

Seshadri-exceptional foliations

 The maximal Seshadri number μ(L) of an ample line bundle L on a smooth projective variety X measures the local positivity of the line bundle L at a general point of X. By refining the method of Ein-Küchle-Lazarsfeld, lower bounds on μ(L) are obtained in terms of L ⁿ , n=dim(X), for a class of varieties. The main idea is to show that if a certain lower bound is violated, there exists a non-trivial foliation on the variety whose leaves are covered by special curves. In a number of examples, one can show that such foliations must be trivial and obtain lower bounds for μ(L). The examples include the hyperplane line bundle on a smooth surface in ℙ³ and ample line bundles on smooth threefolds of Picard number 1. Received: 29 June 2001 / Published online: 16 October 2002 RID="⋆" ID="⋆" Supported by Grant No. 98-0701-01-5-L from the KOSEF. RID="⋆⋆" ID="⋆⋆" Supported by Grant No. KRF-2001-041-D00025 from the KRF.