About equivalent interval colorings of weighted graphs

Given a graph G=(V,E) with strictly positive integer weights ω_i on the vertices iV, a k-interval coloring of G is a function I that assigns an interval I(i){1,…,k} of ω_i consecutive integers (called colors) to each vertex iV. If two adjacent vertices x and y have common colors, i.e. I(i)∩I(j)≠0/ for an edge [i,j] in G, then the edge [i,j] is said conflicting. A k-interval coloring without conflicting edges is said legal. The interval coloring problem (ICP) is to determine the smallest integer k, called interval chromatic number of G and denoted χ_int(G), such that there exists a legal k-interval coloring of G. For a fixed integer k, the k-interval graph coloring problem (k-ICP) is to determine a k-interval coloring of G with a minimum number of conflicting edges. The ICP and k-ICP generalize classical vertex coloring problems where a single color has to be assigned to each vertex (i.e., ω_i=1 for all vertices iV).Two k-interval colorings I₁ and I₂ are said equivalent if there is a permutation π of the integers 1,…,k such that ℓI₁(i) if and only if π(ℓ)I₂(i) for all vertices iV. As for classical vertex coloring, the efficiency of algorithms that solve the ICP or the k-ICP can be increased by avoiding considering equivalent k-interval colorings, assuming that they can be identified very quickly. To this purpose, we define and prove a necessary and sufficient condition for the equivalence of two k-interval colorings. We then show how a simple tabu search algorithm for the k-ICP can possibly be improved by forbidding the visit of equivalent solutions.     

Inverse Matroid Intersection Problem

LetM ₁ andM ₂ be matroids onS,B be theirk-element common independent set, andw a weight function onS. Given two functionsb 0 andc 0 onS, the Inverse Matroid Intersection Problem (IMIP) is to determine a modified weight functionw such that (a)B becomes a maximum weight common independent set of cardinalityk underw, (b)c¦w — w¦ is minimum, and (c)¦w — w b. Many Inverse Combinatorial Optimization Problems can be considered as the special cases of the IMIP.In this paper we show that the IMIP can be solved in strongly polynomial time, and give a necessary and sufficient condition for the feasibility of the IMIP. Finally we extend the discussion to the version of the IMIP with Multiple Common Independent Sets.Research partially supported by the National Natural Science Foundation of China     

The caratheodory number for thek-core

Thek-core of the setS ⁿ is the intersection of the convex hull of all setsA S with ¦SA¦<-k. The Caratheodory number of thek-core is the smallest integerf (d,k) with the property thatx core _{kS, S} ⁿ implies the existence of a subsetT S such thatx core_kT and ¦T¦f (d, k). In this paper various properties off(d, k) are established.Research of this author was partially supported by Hungarian National Science Foundation grant no. 1812.     

The moduli of certain families of curves and the range of f(ζ0) in the class of univalent functions with real coefficients

By simultaneously considering two moduli problems for pairs of homotopic classes of curves a complete solution is obtained of the problem of the range of functions of the class S_R, where S_R is the class of functions in S with real coefficients, at a fixed point ₀ of the disk ¦¦<1, and min¦f(₀¦ in the class S_Ris also found. Partial results in this problem were obtained earlier by J. Jenkins and V. V. Chernikov.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 139, pp. 156–167, 1984.     

Solution of an extremal problem for sets using resultants of polynomials

A new, short proof is given of the following theorem of Bollobás: LetA ₁,..., A_h andB ₁,..., B_h be collections of sets with _i ¦A _i¦=r,¦B_i¦=s and ¦A _iB_j¦=Ø if and only ifi=j, thenh( _s ^r+s ). The proof immediately extends to the generalizations of this theorem obtained by Frankl, Alon and others.     

Monotone subsequences in (0, 1)-matrices

A (0, 1)-matrix contains anS ₀(k) if it has 0-cells (i, j ₁), (i + 1,j ₂),..., (i + k – 1,j _k) for somei andj ₁ < ... < j_k, and it contains anS ₁(k) if it has 1-cells (i ₁,j), (i ₂,j + 1),...,(i _k ,j + k – 1) for somej andi ₁ < ... <i _k . We prove that ifM is anm × n rectangular (0, 1)-matrix with 1 m n whose largestk for anS ₀(k) isk ₀ m, thenM must have anS ₁(k) withk m/(k ₀ + 1). Similarly, ifM is anm × m lower-triangular matrix whose largestk for anS ₀(k) (in the cells on or below the main diagonal) isk ₀ m, thenM has anS ₁(k) withk m/(k ₀ + 1). Moreover, these results are best-possible.     

Distances to the two and three furthest points

Let a compact setF ⁿ contain no less thank points. The functionf _k : ⁿ defined by the formulaf _k (M)=sup _i ^=1/k ¦MA _i ¦, whereA _i are distinct points inF, is convex. Fork=2 its minimum is attained at the center of the smallest ball containingF or on a segment passing through this center. Fork=3 (as well as for any oddk) the minimum point off _k is unique, whereas for evenk the domain wheref _k attains its minimum can include a segment.Translated fromMatematicheskie Zametki, Vol. 59, No. 5, pp. 703–708, May, 1996.This research was partially supported by the Russian Foundation for Basic Research under grant No. 94-01-01044     

Mutually independent hamiltonian cycles for the pancake graphs and the star graphs

A hamiltonian cycle C of a graph G is an ordered set u₁,u₂,…,u_n(G),u₁ of vertices such that u_i≠u_j for i≠j and u_i is adjacent to u_i+1 for every i{1,2,…,n(G)−1} and u_n(G) is adjacent to u₁, where n(G) is the order of G. The vertex u₁ is the starting vertex and u_i is the ith vertex of C. Two hamiltonian cycles C₁=u₁,u₂,…,u_n(G),u₁ and C₂=v₁,v₂,…,v_n(G),v₁ of G are independent if u₁=v₁ and u_i≠v_i for every i{2,3,…,n(G)}. A set of hamiltonian cycles {C₁,C₂,…,C_k} of G is mutually independent if its elements are pairwise independent. The mutually independent hamiltonicity IHC(G) of a graph G is the maximum integer k such that for any vertex u of G there exist k mutually independent hamiltonian cycles of G starting at u.In this paper, the mutually independent hamiltonicity is considered for two families of Cayley graphs, the n-dimensional pancake graphs P_n and the n-dimensional star graphs S_n. It is proven that IHC(P₃)=1, IHC(P_n)=n−1 if n≥4, IHC(S_n)=n−2 if n{3,4} and IHC(S_n)=n−1 if n≥5.     

On extremal contractions from threefolds to surfaces: The case of one non-Gorenstein point and a nonsingular base surface

In this paper, we study the local structure of extremal contractionsfXS from threefoldsX with only terminal singularities onto a surfaceS. If the surfaceS is nonsingular andX has a unique non-Gorenstein point on a fiber, we prove that either the linear system ¦–K _X ¦, ¦–2K _X ¦, or ¦–3K _X ¦contains a good divisor.Translated from Itogi Nauki i Tekhniki, Seriya Sovremennaya Matematika i Ee Prilozheniya. Tematicheskie Obzory. Vol. 45, Algebraic Geometry-8, 1997.     

Indecomposable Sylow 2-Subgroups of Simple Groups

Let S be a Sylow 2-subgroup of a finite simple group and let S=S₁×S₂××S_k be the direct product and each component S_i, i=1,2,...,k is indecomposable. In this article, we prove that each S_i is also a Sylow 2-subgroup of some simple group. Mathematics Subject Classifications (2000) 20E32, 20D20.     

Limit theorems for sums of dependent random variables occurring in statistical mechanics

Summary We study the asymptotic behavior of partial sums S _nfor certain triangular arrays of dependent, identically distributed random variables which arise naturally in statistical mechanics. A typical result is that under appropriate assumptions there exist a real number m, a positive real number , and a positive integer k so that (S _n–nm)/n^1–1/2k converges weakly to a random variable with density proportional to exp(–¦s¦ ^2k/(2k)!). We explain the relation of these results to topics in Gaussian quadrature, to the theory of moment spaces, and to critical phenomena in physical systems.Alfred P. Sloan Research Fellow. Research supported in part by a Broadened Faculty Research Grant at the University of Massachusetts and by National Science Foundation Grant MPS 76-06644Research supported in part by National Science Foundation Grants MPS 74-04870 A01 and MCS 77-20683     

Some monotonicity properties of symmetric pólya densities and their exponential families

Summary In this note we observe that for independent symmetric random variables X and Y, when the pdf of X is PF, the conditional distributions of ¦Y¦ given S = X + Y form a MLR family. We then show that for a function : R ⁿR that is symmetric in each coordinate and increasing on (0, )ⁿ, E((S₁,...,S_n)¦S_n = s) is even and increasing in ¦s¦. Here S₁,...,S_n are partial sums with independent symmetric PF summands. Application is made to sequential tests that minimize the maximum expected sample size when the model is a one-parameter exponential family generated by a symmetric PF density.Work supported by NSF grants MPS 72-05082 AO2 and MCS 75-23344     

Computing a longest common subsequence for a set of strings

The known 2-string LCS problem is generalized to finding a Longest Common Subsequence (LCS) for a set of strings. A new, general approach that systematically enumerates common subsequences is proposed for the solution. Assuming a finite symbol set, it is shown that the presented scheme requires a preprocessing time that grows linearly with the total length of the input strings and a processing time that grows linearly with (K), the number of strings, and () the number of matches among them. The only previous algorithm for the generalized LCS problem takesO(K·|S ₁|·|S ₂|·...|S _k |) execution time, where |S _i | denotes the length of the stringS _i . Since typically is a very small percentage of |S ₁|·|S ₂|·...·|S _k |, the proposed method may be considered to be much more efficient than the straightforward dynamic programming approach.     

A constructive method for the solution of the stability problem

Summary In this paper it is shown that the problem of solving the Liapounov matrix equationSM +M ^T S = –I is greatly simplified when the given real matrixM is in upper Hessenberg form. The solution is obtained as a linear combinationS = p _i S _i ofn linearly independent symmetric matricesS _i , whereS _i M +M ^T S _i =2D _i and p _i D _i = –1/2I. Explicit formulae are given for the elements of theS _i , andD _i while determination of thep _i requires the solution of ann ×n linear system.     

Algorithms for non-uniform size data placement on parallel disks

We study an optimization problem that arises in the context of data placement in a multimedia storage system. We are given a collection of M multimedia objects (data items) that need to be assigned to a storage system consisting of N disks d₁,d₂,…,d_N. We are also given sets U₁,U₂,…,U_M such that U_i is the set of clients seeking the ith data item. Data item i has size s_i. Each disk d_j is characterized by two parameters, namely, its storage capacity C_j which indicates the maximum total size of data items that may be assigned to it, and a load capacity L_j which indicates the maximum number of clients that it can serve. The goal is to find a placement of data items to disks and an assignment of clients to disks so as to maximize the total number of clients served, subject to the capacity constraints of the storage system.We study this data placement problem for homogeneous storage systems where all the disks are identical. We assume that all disks have a storage capacity of k and a load capacity of L. Previous work on this problem has assumed that all data items have unit size, in other words s_i=1 for all i. Even for this case, the problem is NP-hard. For the case where s_i{1,…,Δ} for some constant Δ, we develop a polynomial time approximation scheme (PTAS). This result is obtained by developing two algorithms, one that works for constant k and one that works for arbitrary k. The algorithm for arbitrary k guarantees that a solution where at least -fraction of all clients are assigned to a disk (under certain assumptions). In addition we develop an algorithm for which we can prove tight bounds when s_i{1,2}. In fact, we can show that a -fraction of all clients can be assigned (under certain natural assumptions), regardless of the input distribution.     

Radii of convexity and close-to-convexity of certain integral representations

Strict upper bounds are determined for ¦s(z)¦, ¦Re s(z)¦, and ¦Im s(z) ¦ in the class of functions s(z)=a _nzⁿ+a_n+1zⁿ⁺¹+... (n¹) regular in ¦z¦<1 and satisfying the condition ¦u (₁) –u (₂) ¦K¦ ₁- ₂¦, where U()=Re s (eⁱ ), K>0, and ₁ and ₂ are arbitrary real numbers. These bounds are used in the determination of radii of convexity and close-to-convexity of certain integral representations.Translated from Matematicheskie Zametki, Vol. 7, No. 5, pp. 581–592, May, 1970.The author wishes to thank L. A. Aksent'ev for his guidance in this work.     

m-Systems and Partial m-Systemsof Polar Spaces

LetP be a finite classical polar space of rankr, withr 2. A partialm-systemM ofP, with 0 m r - 1, is any set (₁), ₂,..., _k ofk ( 0) totally singularm-spaces ofP such that no maximal totally singular space containing _i has a point in common with (_{1 2} ... _k) — _i,i = 1, 2,...,k. In a previous paper an upper bound for ¦M¦ was obtained (Theorem 1). If ¦M¦ = , thenM is called anm-system ofP. Form = 0 them-systems are the ovoids ofP; form =r - 1 them-systems are the spreads ofP. In this paper we improve in many cases the upper bound for the number of elements of a partialm-system, thus proving the nonexistence of several classes ofm-systems.Dedicated to Hanfried Lenz on the occasion of his 80th birthday     

The capacity of a channel with arbitrarily varying channel probability functions and binary output alphabet

Summary Let X={1,..., a} be the input alphabet and Y={1,2} be the output alphabet. Let X ^t =X and Y ^t =Y for t=1,2,..., X _n = X ^t and Y _n = Y ^t . Let S be any set, C=={w(·¦·¦)s)¦sS} be a set of (a×2) stochastic matrices w(··¦s), and S ^t=S, t=1,..., n. For every s _n =(s ¹,...,s ⁿ ) S ^t define P(·¦·¦s _n)= w(y ^t ¦x ^t ¦s ^t ) for every x _n=x ¹, , x ⁿX _n and every y _n=(y ¹, , y ⁿ)Y _n. Consider the channel C _n ={P(·¦·¦)s _n )¦s _n S _n } with matrices (·¦·¦s), varying arbitrarily from letter to letter. The authors determine the capacity of this channel when a) neither sender nor receiver knows s _n, b) the sender knows s _n, but the receiver does not, and c) the receiver knows s _n, but the sender does not.Research of both authors supported by the U.S. Air Force under Grant AF-AFOSR-68-1472 to Cornell University.     

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.