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.     

An Ω(n 4/3) lower bound on the randomized complexity of graph properties

We improve King's (n ^5/4) lower bound on the randomized decision tree complexity of monotone graph properties to (n ^4/3). The proof follows Yao's approach and improves it in a different direction from King's. At the heart of the proof are a duality argument combined with a new packing lemma for bipartite graphs.The paper was written while the author was a graduate student at the University of Chicago and was completed at M.I.T. The work was supported in part by NSF under GRANT number NSF 5-27561, the Air Force under Contract OSR-86-0076 and by DIMACS (Center for Discret Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648.     

On the Value of a Random Minimum Weight Steiner Tree

Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center.     

Improved lower bounds on the length of Davenport-Schinzel sequences

We derive lower bounds on the maximal length _s(n) of (n, s) Davenport Schinzel sequences. These bounds have the form _2s=1(n)=(n^s(n)), where(n) is the extremely slowly growing functional inverse of the Ackermann function. These bounds extend the nonlinear lower bound ₃ (n)=(n(n)) due to Hart and Sharir [5], and are obtained by an inductive construction based upon the construction given in [5].Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.     

On Heilbronn’s Problem in Higher Dimension

Heilbronn conjectured that given arbitrary n points in the 2-dimensional unit square [0, 1]², there must be three points which form a triangle of area at most O(1/n²). This conjecture was disproved by a nonconstructive argument of Komlós, Pintz and Szemerédi [10] who showed that for every n there is a configuration of n points in the unit square [0, 1]² where all triangles have area at least (log n/n²). Considering a generalization of this problem to dimensions d3, Barequet [3] showed for every n the existence of n points in the d-dimensional unit cube [0, 1]^d such that the minimum volume of every simplex spanned by any (d+1) of these n points is at least (1/n^d). We improve on this lower bound by a logarithmic factor (log n).     

Energy functional depending on elastic strain and chemical composition

In this paper we deal with energy functionals depending on elastic strain and chemical composition and we obtain lower semicontinuity results, existence theorems and relaxation in the spacesH ^1,p(; ⁿ)×L ^q (; ^d) with respect to weak convergence. Our proofs use parametrized measures associated with weakly converging sequences.The research was partially supported by the National Science Foundation under Grants No. DMS-9000133 and DMS-9201215 and also by the Army Research Office and the National Science Foundation through the Center for Nonlinear Analysis.The research was partially supported by the National Science Foundation uncer Grants No. DMs 911572, the AFOSR 91 0301, the ARO DAAL03 92 G 003 and also by the ARO and the NSF through the Center for Nonlinear Analysis.The research was supported by DGICYT (Spain) through Programa de Perfeccionamiento y Movilidad del Personal Investigador and through grant PB90-0245, by the Army Research Office and the National Science Foundation through the Center for Nonlinear Analysis and also by the project EurHomogenization SC1-CT91-0732 of the European Comunity.     

On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

On the width of an orientation of a tree

There are 2 ^n-1 ways in which a tree on n vertices can be oriented. Each of these can be regarded as the (Hasse) diagram of a partially ordered set. The maximal and minimal widths of these posets are determined. The maximal width depends on the bipartition of the tree as a bipartite graph and it can be determined in time O(n). The minimal width is one of [/2] or [/2]+1, where is the number of leaves of the tree. An algorithm of execution time O(n + ² log ) to construct the minimal width orientation is given.This research was partially funded by the National Science and Engineering Research Council of Canada under Grant Number A4219.     

Norm-graphs and bipartite turán numbers

For everyt>1 and positiven we construct explicit examples of graphsG with |V (G)|=n, |E(G)|c _t ·n ^2–1/t which do not contain a complete bipartite graghK _t,t !+1 This establishes the exact order of magnitude of the Turán numbers ex (n, K _t,s ) for any fixedt and allst!+1, improving over the previous probabilistic lower bounds for such pairs (t, s). The construction relies on elementary facts from commutative algebra.Research supported in part by NSF Grants DMS-8707320 and DMS-9102866.Research supported in part by Hungarian National Foundation for Scientific Research Grant     

A new graph triconnectivity algorithm and its parallelization

We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called open ear decomposition. A parallel implementation of the algorithm on a CRCW PRAM runs inO(log² n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109.     

On depth first search strees inm-out digraphs

We consider depth first search (DFS for short) trees in a class of random digraphs: am-out model. Let _i be thei ^th vertex encountered by DFS andL(i, m, n) be the height of _i in the corresponding DFS tree. We show that ifi/n asn, then there exists a constanta(,m), to be defined later, such thatL(i, m, n)/n converges in probability toa(,m) asn. We also obtain results concerning the number of vertices and the number of leaves in a DFS tree.     

Finding the αn-th largest element

We describe an algorithm for selecting the n-th largest element (where 0<<1), from a totally ordered set ofn elements, using at most (1+(1+o(1))H())·n comparisons whereH() is the binary entropy function and theo(1) stands for a function that tends to 0 as tends to 0. For small values of this is almost the best possible as there is a lower bound of about (1+H())·n comparisons. The algorithm obtained beats the global 3n upper bound of Schönhage, Paterson and Pippenger for <1/3.     

Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm

In this paper we analyze the average number of steps performed by the self-dual simplex algorithm for linear programming, under the probabilistic model of spherical symmetry. The model was proposed by Smale. Consider a problem ofn variables withm constraints. Smale established that for every number of constraintsm, there is a constantc(m) such that the number of pivot steps of the self-dual algorithm,(m, n), is less thanc(m)(lnn) ^m(m+1) . We improve upon this estimate by showing that(m, n) is bounded by a function ofm only. The symmetry of the function inm andn implies that(m, n) is in fact bounded by a function of the smaller ofm andn. Parts of this research were done while the author was visiting Stanford University, XEROX- PARC, Carnegie-Mellon University and Northwestern University and was supported in part by the National Science Foundation under Grants MCS-8300984, ECS-8218181 and ECS-8121741.     

An Ω(n 5/4) lower bound on the randomized complexity of graph properties

A decision tree algorithm determines whether an input graph withn nodes has a property by examining the entries of the graph's adjacency matrix and branching according to the information already gained. All graph properties which are monotone (not destroyed by the addition of edges) and nontrivial (holds for somes but not all graphs) have been shown to require (n ²) queries in the worst case.In this paper, we investigate the power of randomness in recognizing these properties by considering randomized decision tree algorithms in which coins may be flipped to determine the next entry to be examined. The complexity of a randomized algorithm is the expected number of entries that are examined in the worst case. The randomized complexity of a property is the minimum complexity of any randomized decision tree algorithm which computes the property. We improve Yao's lower bound on the randomized complexity of any nontrivial monotone graph property from (n log^1/12 n) to (n ^5/4).     

A generalization of Lévy's concentration-variance inequality

Summary Sharp lower bounds are found for the concentration of a probability distribution as a function of the expectation of any given convex symmetric function . In the case (x)=(x-c)², wherec is the expected value of the distribution, these bounds yield the classical concentration-variance inequality of Lévy. An analogous sharp inequality is obtained in a similar linear search setting, where a sharp lower bound for the concentration is found as a function of the maximum probability swept out from a fixed starting point by a path of given length.Research partially supported by NSF Grant SES-88-21999Research partially supported by NSF Grants DMS-87-01691 and DMS-89-01267 and a Fulbright Research Grant     

Lower bounds on moving a ladder in two and three dimensions

It is shown that (n ²) distinct moves may be necessary to move a line segment (a ladder) in the plane from an initial to a final position in the presence of polygonal obstacles of a total ofn vertices, and that (n ⁴) moves may be necessary for the same problem in three dimensions. These two results establish lower bounds on algorithms that solve the motion-planning problems by listing the moves of the ladder. The best upper bounds known areO(n ² logn) in two dimensions, andO(n ⁵ logn) in three dimensions.This work was partially supported by NSF Grants DCR-83-51468 and grants from Martin Marietta, IBM, and General Motors.     

Low diameter graph decompositions

Adecomposition of a graphG=(V,E) is a partition of the vertex set into subsets (calledblocks). Thediameter of a decomposition is the leastd such that any two vertices belonging to the same connected component of a block are at distance d. In this paper we prove (nearly best possible) statements, of the form: Anyn-vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [4] it was shown that every graph has a decomposition into at mosts(n) blocks of diameter at mosts(n) for . Using a technique of Awerbuch [3] and Awerbuch and Peleg [5], we improve this result by showing that every graph has a decomposition of diameterO (logn) intoO(logn) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in timeO(log² n). The construction can be parameterized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible, for two families of graphs: the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner's lemma for the first class and Tucker's lemma for the second.A preliminary version of this paper appeared as Decomposing Graphs into Regions of Small Diameter in Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms (1991) 321-330.This work was supported in part by NSF grant DMS87-03541 and by a grant from the Israel Academy of Science.This work was supported in part by NSF grant DMS87-03541 and CCR89-11388.     

The local nature of Δ-coloring and its algorithmic applications

Given a connected graphG=(V, E) with |V|=n and maximum degree such thatG is neither a complete graph nor an odd cycle, Brooks' theorem states thatG can be colored with colors. We generalize this as follows: letG-v be -colored; then,v can be colored by considering the vertices in anO(log n) radius aroundv and by recoloring anO(log n) length augmenting path inside it. Using this, we show that -coloringG is reducible inO(log³ n/log) time to (+1)-vertex coloringG in a distributed model of computation. This leads to fast distributed algorithms and a linear-processorNC algorithm for -coloring.A preliminary version of this paper appeared as part of the paper Improved Distributed Algorithms for Coloring and Network Decomposition Problems, in theProceedings of the ACM Symposium on Theory of Computing pages 581–592, 1992. This research was done when the authors were at the Computer Science Department of Cornell University. The research was supported in part by NSF PYI award CCR-89-96272 with matching funds from UPS and Sun Microsystems.     

Near Optimal Separation Of Tree-Like And General Resolution

We present the best known separation between tree-like and general resolution, improving on the recent exp(n ) separation of [2]. This is done by constructing a natural family of contradictions, of size n, that have O(n)-size resolution refutations, but only exp((n/log n))- size tree-like refutations. This result implies that the most commonly used automated theorem procedures, which produce tree-like resolution refutations, will perform badly on some inputs, while other simple procedures, that produce general resolution refutations, will have polynomial run-time on these very same inputs. We show, furthermore that the gap we present is nearly optimal. Specifically, if S (S _T ) is the minimal size of a (tree-like) refutation, we prove that S _T = exp(O(S log log S/log S)).* This research was supported by Clore Foundation Doctoral Scholarship. Research supported by NSF Award CCR-0098197 and USA–Israel BSF Grant 97-00188. This research was supported by grant number 69/96 of the Israel Science Foundation, founded by the Israel Academy for Sciences and Humanities.     

An Extension Of The Ruzsa-Szemerédi Theorem

  We let G ^(r)(n,m) denote the set of r-uniform hypergraphs with n vertices and m edges, and f ^(r)(n,p,s) is the smallest m such that every member of G ^(r)(n,m) contains amember of G ^(r)(p,s). In this paper we are interested in fixed values r,p and s for which f ^(r)(n,p,s) grows quadratically with n. A probabilistic construction of Brown, Erds and T. Sós ([2]) implies that f ^(r)(n,s(r-2)+2,s)=(n ²). In the other direction the most interesting question they could not settle was whether f ⁽³⁾(n,6, 3) = o(n ²). This was proved by Ruzsa and Szemerédi [11]. Then Erds, Frankl and Rödl [6] extended this result to any r: f ^(r)(n, 3(r-2)+3, 3)=o(n ²), and they conjectured ([4], [6]) that the Brown, Erds and T. Sós bound is best possible in the sense that f ^(r)(n,s(r-2)+3,s)=o(n ²).In this paper by giving an extension of the Erds, Frankl, Rödl Theorem (and thus the Ruzsa–Szemerédi Theorem) we show that indeed the Brown, Erds, T. Sós Theorem is not far from being best possible. Our main result is