Packing directed circuits

We prove a conjecture of Younger, that for every integern0 there exists an integert0 such that for every digraphG, eitherG hasn vertex-disjoint directed circuits, orG can be made acyclic by deleting at mostt vertices.Research partially supported by DONET ECHM contract CHRXCT930090.Research partially supported by DIMACS, by NSF grant DMS-9401981 and by ONR grant N00014-92-J-1965, and partially performed under a consulting agreement with Bellcore.Research partially supported by DIMACS, by Université de Paris VI, by NSF grant DMS-9303761 and by ONR grant N00014-93-1-0325, and partially performed under a consulting agreement with Bellcore.     

The spectral representation of stable processes: Harmonizability and regularity

Summary We show that symmetric -stable moving average processes are not harmonizable. However, we show that a concept of generalized spectrum holds for allL _p -bounded processes O<p<-2. In capep=2, generalized spectrum is a measure and the classical representation follows. For strongly harmonizable symmetric -stable processes we derive necessary and sufficient conditions for the regularity and the singularity for 0<2, using known results on the invariant subspaces. We also get Cramér-Wold decomposition for the case 0<2.Supported by CPBP01. 02.Supported by ONR N00014-85-K-0150     

Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem

We provide positive and negative results concerning the standard method of identifying a hidden subgroup of a nonabelian group using a quantum computer.* Supported in part by NSF grants CCR-9820931 and CCR-0208929. Supported in part by NSF CAREER grant 0049092, the NSF Institute for Quantum Information, the Charles Lee Powell Foundation, and the Mathematical Sciences Research Institute. Supported in part by an NSF Mathematical Sciences Postdoctoral Research Fellowship and NSF grant DMS-0301320.§ Supported in part by DARPA QUIST grant F30602-01-2-0524, ARO grant DAAD19-03-1-0082, and NSF ITR grant CCR-0121555.     

Blowup for the heat equation with a noise term

Summary In this paper we study blow up of the equation , where is a two-dimensional white noise field and where Dirichlet boundary conditions are enforced. It is known that if <3/2, then the solution exists for all time; in this paper we show that if is much larger than 3/2, then the solution blows up in finite time with positive probability. We prove this by considering how peaks in the solution propagate. If a peak of high mass forms, we rescale the equation and divide the mass of the peak into a collection of peaks of smaller mass, and these peaks evolve almost independently. In this way we compare the evolution ofu to a branching process. Large peaks are regarded as particles in this branching process. Offspring are peaks which are higher by some factor. We show that the expected number of offspring is greater than one when is much larger than 3/2, and thus the branching process survives with positive probability, corresponding to blowup in finite time.Supported by NSF grant DMS-9021508, NSA grant MDA904-910-H-0034, and ARO Grant MSI DAAL03-91-C-0027Supported by ONR grant N00014-91-J-1526.     

Decomposing Berge Graphs Containing No Proper Wheel, Long Prism Or Their Complements

In this paper we show that, if G is a Berge graph such that neither G nor its complement contains certain induced subgraphs, named proper wheels and long prisms, then either G is a basic perfect graph( a bipartite graph, a line graph of a bipartite graph or the complement of such graphs) or it has a skew partition that cannot occur in a minimally imperfect graph. This structural result implies that G is perfect. This work was supported in part by NSF grant DMI-0352885 and ONR grant N00014-03-1-0188.     

Projective plane and Möbius band obstructions

LetS be a compact surface with possibly non-empty boundary S and letG be a graph. LetK be a subgraph ofG embedded inS such that SK. Anembedding extension ofK toG is an embedding ofG inS which coincides onK with the given embedding ofK. Minimal obstructions for the existence of embedding extensions are classified in cases whenS is the projective plane or the Möbius band (for several canonical choices ofK). Linear time algorithms are presented that either find an embedding extension, or return a nice obstruction for the existence of extensions.Supported in part by the Ministry of Science and Technology of Slovenia, Research Project P1-0210-101-94.     

Explicit matchings in the middle levels of the Boolean lattice

New classes of explicit matchings for the bipartite graph (k) consisting of the middle two levels of the Boolean lattice on 2k+1 elements are constructed and counted. This research is part of an ongoing effort to show that (k) is Hamiltonian.Supported by Office of Naval Research contract N00014-85K-0494.Supported by National Science Foundation grant DMS-8041281.     

Graph Connectivity After Path Removal

Let G be a graph and u, v be two distinct vertices of G. A u—v path P is called nonseparating if G—V(P) is connected. The purpose of this paper is to study the number of nonseparating u—v path for two arbitrary vertices u and v of a given graph. For a positive integer k, we will show that there is a minimum integer (k) so that if G is an (k)-connected graph and u and v are two arbitrary vertices in G, then there exist k vertex disjoint paths P ₁[u,v], P ₂[u,v], . . ., P _k [u,v], such that G—V (P _i [u,v]) is connected for every i (i = 1, 2, ..., k). In fact, we will prove that (k) 22k+2. It is known that (1) = 3.. A result of Tutte showed that (2) = 3. We show that (3) = 6. In addition, we prove that if G is a 5-connected graph, then for every pair of vertices u and v there exists a path P[u, v] such that G—V(P[u, v]) is 2-connected.* Supported by NSF grant No. DMS-0070059 Supported by ONR grant N00014-97-1-0499 Supported by NSF grant No. 9531824     

Universally signable graphs

In a graph, a chordless cycle of length greater than three is called a hole. Let be a {0, 1} vector whose entries are in one-to-one correspondence with the holes of a graphG. We characterize graphs for which, for all choices of the vector , we can pick a subsetF of the edge set ofG such that |F H| H (mod 2), for all holesH ofG and |F T| 1 for all trianglesT ofG. We call these graphsuniversally signable. The subsetF of edges is said to be labelledodd. All other edges are said to be labelledeven. Clearly graphs with no holes (triangulated graphs) are universally signable with a labelling of odd on all edges, for all choices of the vector . We give a decomposition theorem which leads to a good characterization of graphs that are universally signable. This is a generalization of a theorem due to Hajnal and Surányi [3] for triangulated graphs.This work was supported in part by NSF grants DMI-9424348 DMS-9509581 and ONR grant N00014-89-J-1063. Ajai Kapoor was also supported by a grant from Gruppo Nazionale Delle Ricerche-CNR. We also acknowledge the support of Laboratoire ARTEMIS, Université Joseph Fourier, Grenoble.     

Light traffic heuristic for anM/G/1 queue with limited inventory

Motivated by solving a stylized location problem, we develop a light traffic heuristic for anM/G/1 queue with limited inventory that gives rise to a closed form expression for average delay in terms of basic system parameters. Simulation experiments show that the heuristic works well. The inventory operates as follows: the inventory level drops by one unit after each service completion and whenever it drops to a pre-specified levelu, an order is placed with replenishment time exp(). Upon replenishment the inventory is restocked to a pre-specified levels and any arrivals when there is no inventory are placed in queue. Suggestions are given to cover the more general case of a New Better than Used (NBU) replenishment time distribution. Applications to inventory management problems are also discussed.The research was supported in part by ONR Contract N00014-90-J-1649, NSF Contract DDM-8922712 and the Center for Telecommunications Research under NSF grant CDR 84-21402.     

Modular intersection graphs

A graphG = (V, E) is a modular intersection graph on a finite setU if there is a family of subsetsS = {S _xx V} ofU and positive integerst < m such thatxy is an edge ofG if and only if |S _x S_y| (modm) t. Modular representations of various classes of graphs and studied as well as some related parameters.Research supported by Grant N00014-89-J-1643 from the Office of Naval Research.     

Non-intersection exponents for Brownian paths

Summary LetX andY be independent 3-dimensional Brownian motions,X(0)=(0,0,0),Y(0)=(1,0,0) and letp _r =P(X[0,r] Y[0,r]=). Then the non-intersection exponent exists and is equal to a similar non-intersection exponent for random walks. Analogous results hold inR ² and for more than 2 paths.Supported in part by NSF grant DMS 8702620Supported by NSF grant DMS 8702879 and an Alfred P. Sloan Research Fellowship     

Extremal eigenvalue problems for composite membranes,II

Given an open bounded connected set R ^N and a prescribed amount of two homogeneous materials of different density, for smallk we characterize the distribution of the two materials in that extremizes thekth eigenvalue of the resulting clamped membrane. We show that these extremizers vary continuously with the proportion of the two constituents. The characterization of the extremizers in terms of level sets of associated eigenfunctions provides geometric information on their respective interfaces. Each of these results generalizes toN dimensions the now classical one-dimensional work of M. G. Krein.The work of the first author was supported in part by NSF Grant DMS-8201719 (A. Manitius, P. I.), an IBM fellowship, a GE teaching incentive, and DARPA Contract F49620-87-C-0065. That of the second author was supported in part by ONR Grant N00014-84-5-516, AFOSR Grant AFOSR-86-0180, and NSF Grant DMS-8713722.     

Optimal intensity control of a multi-class queue

We study a mixed problem of optimal scheduling and input and output control of a single server queue with multi-classes of customers. The model extends the classical optimal scheduling problem by allowing the general point processes as the arrival and departure processes and the control of the arrival and departure intensities. The objective of our scheduling and control problem is to minimize the expected discounted inventory cost over an infinite horizon, and the problem is formulated as an intensity control. We find the well-knownc is the optimal solution to our problem.Supported in part by NSF under grant ECS-8658157, by ONR under contract N00014-84-K-0465, and by a grant from AT&T Bell Laboratories.The work was done while the author was a postdoctoral fellow in the Division of Applied Sciences, Harvard University, Cambridge, Massachusetts 02138.     

The Domination Parameters of Cubic Graphs

Let ir(G), (G), i(G), ₀(G), (G) and IR(G) be the irredundance number, the domination number, the independent domination number, the independence number, the upper domination number and the upper irredundance number of a graph G, respectively. In this paper we show that for any nonnegative integers k₁, k₂, k₃, k₄, k₅ there exists a cubic graph G satisfying the following conditions: (G) – ir(G) k₁, i(G) – (G) k₂, ₀(G) – i(G) > k₃, (G) – ₀(G) – k₄, and IR(G) – (G) – k₅. This result settles a problem posed in [9].Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093).Supported by RUTCOR.     

On the structure of certain excursions of a Markov process

Summary Let X be a Markov process and M a homogeneous random set. For t0, we set G _t=Sup{st: sM}. The stochastic dependence between the past and the future of G _Tis investigated for certain stopping times T. This gives some insight to recent results of Getoor concerning the excursion straddling t and the first excursion exceeding a in length.This research was supported in part by NSF grant MCS76-8023     

Quadratic convergence in interval arithmetic,part I

Several procedures in interval arithmetic have been shown to have errorO(w ²), wherew is the width of the data intervals. In this paper we will give a general discussion of this quadratic convergence. Our results will allow us to give some systematic proofs of quadratic convergence.Supported in part by NSF grant GJ-797.     

A counterexample in the theory of random orders

We show that the 0–1 law fails in random orders of fixed dimension k, k3. In particular, we give an example of a first-order sentence , in the language of partial orders, which cannot have limiting probability 0 or 1 among random orders of dimension 3.Research supported by ONR grant N00014-85-K-0769     

Preservation and distortion of area in finitely presented groups

IfK=G where is a tame automorphism of the 1-relator groupG, then the combinatorial area of loops in a Cayley graph ofG is undistorted in a Cayley graph ofK. Examples of distortion of area in fibres of fibrations over the circle are given and a notion of exponent of area distortion is introduced and studied. The inclusion of a finitely generated abelian subgroup in the fundamental group of a compact 3-manifold does not distort area.Partially supported by NSF grant DMS-9200433.     

Triangle Factors In Sparse Pseudo-Random Graphs

The goal of the paper is to initiate research towards a general, Blow-up Lemma type embedding statement for pseudo-random graphs with sublinear degrees. In particular, we show that if the second eigenvalue of a d-regular graph G on 3n vertices is at most cd ³/n ² log n, for some sufficiently small constant c > 0, then G contains a triangle factor. We also show that a fractional triangle factor already exists if < 0.1d ²/n. The latter result is seen to be best possible up to a constant factor, for various values of the degree d = d(n).* Supported by a USA-Israeli BSF grant, by a grant from the Israel Science Foundation and by a Bergmann Memorial Award. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Research supported in part by NSF grant DMS 99-70270 and by the joint Berlin/Zurich graduate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH Zürich.