Edge-colored complete graphs with precisely colored subgraphs

Letf(s, t; k) be the largest value ofm such that it is possible tok-color the edges of the complete graphK _m so that everyK _s ⊆K _m has exactlyt colors occuring on its edges. The main object of this paper is to describe the behavior of the functionf(s,t;k), usually thinking ofs andt fixed, and lettingk become large. Dedicated to Paul Erdős on his seventieth birthday     

On minimum and maximum spanning trees of linearly moving points

In this paper we investigate the upper bounds on the numbers of transitions of minimum and maximum spanning trees (MinST and MaxST for short) for linearly moving points. Here, a transition means a change on the combinatorial structure of the spanning trees. Suppose that we are given a set ofn points ind-dimensional space,S={p ₁,p ₂, ...p _n }, and that all points move along different straight lines at different but fixed speeds, i.e., the position ofp _i is a linear function of a real parametert. We investigate the numbers of transitions of MinST and MaxST whent increases from-∞ to +∞. We assume that the dimensiond is a fixed constant. Since there areO(n ²) distances amongn points, there are naivelyO(n ⁴) transitions of MinST and MaxST. We improve these trivial upper bounds forL ₁ andL _∞ distance metrics. Letk _p (n) (resp. ) be the number of maximum possible transitions of MinST (resp. MaxST) inL _p metric forn linearly moving points. We give the following results in this paper: κ₁(n)=O(n ^5/2 α(n)),κ _∞(n)=O(n ^5/2 α(n)), , and where α(n) is the inverse Ackermann's function. We also investigate two restricted cases, i.e., thec-oriented case in which there are onlyc distinct velocity vectors for movingn points, and the case in which onlyk points move.     

Error bounds for multistep methods revisited

For linear multistep methods with constant stepsize we consider error bounds in terms of weightedL ₂-norms ofh ^px^(p) rather than ofh ^px^(p+1). The bounds apply to stiff systemsx'=Ax+f(t,x) where the spectrum ofA lies in a sector andf is of moderate size.     

Onk-sets in arrangements of curves and surfaces

We extend the notion ofk-sets and (≤k)-sets (see [3], [12], and [19]) to arrangements of curves and surfaces. In the case of curves in the plane, we assume that each curve is simple and separates the plane. Ak-point is an intersection point of a pair of the curves which is covered by exactlyk interiors of (or half-planes bounded by) other curves; thek-set is the set of allk-points in such an arrangement, and the (≤k)-set is the union of allj-sets, forj≤k. Adapting the probabilistic analysis technique of Clarkson and Shor [13], we obtain bounds that relate the maximum size of the (≤k)-set to the maximum size of a 0-set of a sample of the curves. Using known bounds on the size of such 0-sets we obtain asympotically tight bounds for the maximum size of the (≤k)-set in the following special cases: (i) If each pair of curves intersect at most twice, the maximum size is Θ(nkα(nk)). (ii) If the curves are unbounded arcs and each pair of them intersect at most three times, then the maximum size is Θ(nkα(n/k)). (iii) If the curves arex-monotone arcs and each pair of them intersect in at most some fixed numbers of points, then the maximum size of the (≤k)-set is Θ(k ²λ _s (nk)), where λ _s (m) is the maximum length of (m,s)-Davenport-Schinzel sequences. We also obtain generalizations of these results to certain classes of surfaces in three and higher dimensions. Finally, we present various applications of these results to arrangements of segments and curves, high-order Voronoi diagrams, partial stabbing of disjoint convex sets in the plane, and more. An interesting application yields andO(n logn) bound on the expected number of vertically visible features in an arrangement ofn horizontal discs when they are stacked on top of each other in random order. This in turn leads to an efficient randomized preprocessing ofn discs in the plane so as to allow fast stabbing queries, in which we want to report all discs containing a query point. Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and 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 Academy of Sciences.     

Characterizations of the Poisson process as a renewal process via two conditional moments

Given two independent positive random variables, under some minor conditions, it is known that fromE(X^rX+Y)=a(X+Y)^r andE(X^sX+Y)=b(X+Y)^s, for certain pairs ofr ands, wherea andb are two constants, we can characterizeX andY to have gamma distributions. Inspired by this, in this article we will characterize the Poisson process among the class of renewal processes via two conditional moments. More precisely, let {A(t), t0} be a renewal process, with {S _k, k1} the sequence of arrival times, andF the common distribution function of the inter-arrival times. We prove that for some fixedn andk, kn, ifE(S _k ^r A(t)=n)=at^r andE(S _k ^s A(t)=n)=bt^s, for certain pairs ofr ands, wherea andb are independent oft, then {A(t), t0} has to be a Poisson process. We also give some corresponding results about characterizingFto be geometric whenF is discrete.Support for this research was provided in part by the National Science Council of the Republic of China, Grant No. NSC 81-0208-M110-06.     

Primarite DeL p(L r), 1<p,r<∞

In this article we show thatL ^p(L ^r) is primary forp andr in ]1,+∞[. If (h _k) _k≧1 denote the Haar basis, we begin with a study of the sequence (h _k ⊗h _i) and, in particular, the space generated by a subsequence of this sequence. In the first part we study the base ofL ^p(L ^r) and in the second part we show that this space is primary.     

An extremal set theoretical characterization of some steiner systems

Letn, k, t be integers,n>k>t≧0, and letm(n, k, t) denote the maximum number of sets, in a family ofk-subsets of ann-set, no two of which intersect in exactlyt elements. The problem of determiningm(n, k, t) was raised by Erdős in 1975. In the present paper we prove that ifk≦2t+1 andk−t is a prime, thenm(n, k, t)≦( _t ⁿ )( _k ^2k-t-1 )/( _t ^2k-t-1 ). Moreover, equality holds if and only if an (n, 2k−t−1,t)-Steiner system exists. The proof uses a linear algebraic approach.     

Central limit theorem for stochastically continuous processes. Convergence to stable limit

LetX={X(t), t[0, 1]} be a stochastically continuous cadlag process. Assume that thek dimensional finite joint distributions ofX are in the domain of normal attraction of strictlyp-stable, 0<p<2, measure onR ^k for all 1k<. For functionsf, g such that _p (|X(x–X(u)|) >g(u–s) and _p (|X(s–X(t|)|X(t)–X(u|)>f(u–s), 0 s t u 1, conditions are found which imply that the distributions –(n ^–1/p (X ₁+···+X _n )),n1, converge weakly inD[0, 1] to the distribution of ap-stable process. HereX ₁,X ₂, ... are independent copies ofX and _p (Z)=sup _t<0 t ^pP{|Z|<t} denotes the weakpth moment of a random variable Z.     

Lower bounds for Turán's problem

Turán's problem is to determine the maximum numberT(n,k,t) oft-element subsets of ann-set without a complete sub-hypergraph onk vertices, i.e., allt-subsets of ak-set. It is proved that fora≥1 fixed andt sufficiently largeT(n, t+a,t)>(1-a(a+4+o(1))logt/( _a ^t )( _t ⁿ holds     

On maximal t-linearly independent sets

Consider a finite t + r ? 1 dimensional projective space PG(t + r ? 1, s) over a Galois field GF(s) of order s = ?^h, where ? and h are positive integers and ? is the prime characteristic of the field. A collection of k points in PG (t + r ? 1, s) constitutes an L(t, k)-set if no t of them are linearly dependent. An L(t, k)-set is maximal if there exists no other L(t, k′)-set with k′ > k. The largest k for which an L(t, k)-set exists is denoted by M_t(t + r, s). K. A. Bush [3] established that M_t(t, s) = t + 1 for t ? s. The purpose of this paper is to generalize this result and study M_t(t + r, s) for t, r, and s in certain relationships.     

Maximal Collections of Intersecting Arithmetic Progressions

Let N _t (k) be the maximum number of k-term arithmetic progressions of real numbers, any two of which have t points in common. We determine N ₂(k) for prime k and all large k, and give upper and lower bounds for N _t (k) when t 3.* Research supported in part by NSF grant DMS-0070618.     

Topological entropy and blocking cost for geodesics in Riemannian manifolds

For a pair of points x, y in a compact, Riemannian manifold M let n _t (x, y) (resp. s _t (x, y)) be the number of geodesic segments with length ≤ t joining these points (resp. the minimal number of point obstacles needed to block these geodesic segments). We study relationships between the growth rates of n _t (x, y) and s _t (x, y) as t → ∞. We obtain lower bounds on s _t (x, y) in terms of the topological entropy h(M) and the fundamental group π ₁(M). For instance, we show that if h(M) > 0 then s _t grows exponentially, with the rate at least h(M)/2. This strengthens earlier results on blocking of geodesics (Burns and Gutkin Discrete Contin Dyn Syst 21:403–413, 2008; Lafont and Schmidt Geom Topol 11:867–887, 2007), and puts them in a new perspective.      

An approximation of a nonlinear integral equation driven by a function of boundedp-variation

The uniform distance between the solution of a nonlinear equation driven by a functionh with boundedp-variation and its Milstein-type approximation is estimated by δ _n v γ _p (n) v γ _p ² (n), where δ _n =max(t _k −t _k−1 ) is the maximum step size of the approximation on the interval [0,T], γ _p (n)=max υ _p ^1/p (h;[t _k-1,t _k ]), 1 <p < 2, and υ _p (h;[t _k-1,t _k ]) is thep-variation of the functionh on [t _k-1,t _k]. In particular, ifh is a Lipschitz function of order α, then the uniform distance has the bound δ _n ^α for δ_n <1. Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius; Vilnius Technical University, Saulétekio 11, 2054 Vilnius, Lithuania. Published in Lietuvos Matematikos Rinkinys, Vol. 39, No. 3, pp. 317–330, July–September, 1999.     

On projectively normal embeddings of generalk-gonal curves

Fix integersg, k andt witht>0,k≥3 andtk<g/2−1. LetX be a generalk-gonal curve of genusg andR∈Pic ^k (X) the uniqueg _k ¹ onX. SetL:=K _X⊗(R ^*)^⊗t.L is very ample. Leth _L:X→P(H ⁰(X, L)^*) be the associated embedding. Here we prove thath _L(X) is projectively normal. Ifk≥4 andtk<g/2−2 the curveh _L(X) is scheme-theoretically cut out by quadrics. The author was partially supported by MURST and GNSAGA of CNR (Italy).     

Covering abelian groups with cyclic subsets

Summary Letk andm be positive integers. An abelian groupG is said to have ann-cover if there is a subsetS ofG consisting ofn elements such that every non-zero element ofG can be expressed in the formig for some elementg inS and integeri, 1 i k. Lets _n (k) be the largest order of abelian groups that have ann-cover. We investigate the behavior ofs _n (k)/k ask andn is fixed.     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K_k?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004     

New applications of random sampling in computational geometry

This paper gives several new demonstrations of the usefulness of random sampling techniques in computational geometry. One new algorithm creates a search structure for arrangements of hyperplanes by sampling the hyperplanes and using information from the resulting arrangement to divide and conquer. This algorithm requiresO(s ^d+ ) expected preprocessing time to build a search structure for an arrangement ofs hyperplanes ind dimensions. The expectation, as with all expected times reported here, is with respect to the random behavior of the algorithm, and holds for any input. Given the data structure, and a query pointp, the cell of the arrangement containingp can be found inO(logs) worst-case time. (The bound holds for any fixed >0, with the constant factors dependent ond and .) Using point-plane duality, the algorithm may be used for answering halfspace range queries. Another algorithm finds random samples of simplices to determine the separation distance of two polytopes. The algorithm uses expectedO(n ^[d/2]) time, wheren is the total number of vertices of the two polytopes. This matches previous results [10] for the cased = 3 and extends them. Another algorithm samples points in the plane to determine their orderk Voronoi diagram, and requires expectedO(s ¹⁺ k) time fors points. (It is assumed that no four of the points are cocircular.) This sharpens the boundO(sk ² logs) for Lee's algorithm [21], andO(s ² logs+k(s–k) log² s) for Chazelle and Edelsbrunner's algorithm [4]. Finally, random sampling is used to show that any set ofs points inE ³ hasO(sk ² log⁸ s/(log logs)⁶) distinctj-sets withjk. (ForS E ^d , a setS S with |S| =j is aj-set ofS if there is a half-spaceh ⁺ withS =S h ⁺.) This sharpens with respect tok the previous boundO(sk ⁵) [5]. The proof of the bound given here is an instance of a probabilistic method [15].A preliminary version of this paper appeared in theProceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, CA, 1986.     

An analysis of the solution set to a homotopy equation between polynomials with real coefficients

We investigate the structure of the solution setS to a homotopy equationH(Z,t)=0 between two polynomialsF andG with real coefficients in one complex variableZ. The mapH is represented asH(x+iy, t)=h ₁(x, y, t)+ih ₂(x, y, t), whereh ₁ andh ₂ are polynomials from ℝ² × [0,1] into ℝ and i is the imaginary unit. Since all the coefficients ofF andG are real, there is a polynomialh ₃ such thath ₂(x, y, t)=yh₃(x, y, t). Then the solution setS is divided into two sets {(x, t)∶h ₁(x, 0, t)=0} and {(x+iy, t)∶h ₁(x, y, t)=0,h ₃(x, y, t)=0}. Using this division, we make the structure ofS clear. Finally we briefly explain the structure of the solution set to a homotopy equation between polynomial systems with real coefficients in several variables.     

Some characterization results based on the conditional expectation of a function of non-adjacent order statistic (record value)

In this paper, we attempt to characterize a distribution by means ofE[ψ(X _k +s:n)|X _k:n =z]g(z), under some mild conditions on ψ(·) andg(·). An explicit result is provided in the case ofs=1 and a uniqueness result is proved in the case ofs=2. For the general case, an expression is provided for the conditional expectation. Similar results are proved for the record values, both in the continuous as well as in the discrete case (weak records).     

Designs of ϕ-optimal control for second-order processes

Consider a realization of the process on the intervalT=[0,1] for functionsf ₁(t),f ₂(t),...,f _n (t) inH(R), the reproducing kernel Hilbert space with reproducing kernelR(s,t) onT×T, whereR(s,t)=E[ξ(s)ξt)] is assumed to be continuous and known. Problems of the selection of functions {f _k (t)} _k=1 ⁿ to be ϕ-optimal design are given, and an unified approach to the solutions ofD-,A-,E- andD _s-optimal design problems are discussed.