The stable fixtures problem—A many-to-many extension of stable roommates

We study a many-to-many generalisation of the well-known stable roommates problem in which each participant seeks to be matched with a number of others. We present a linear-time algorithm that determines whether a stable matching exists, and if so, returns one such matching.     

An improved upper bound on the density of universal random graphs

We give a polynomial time randomized algorithm that, on receiving as input a pair (H, G) of n‐vertex graphs, searches for an embedding of H into G. If H has bounded maximum degree and G is suitably dense and pseudorandom, then the algorithm succeeds with high probability. Our algorithm proves that, for every integer and a large enough constant C = C_d, as , asymptotically almost all graphs with n vertices and at least edges contain as subgraphs all graphs with n vertices and maximum degree at most d. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 2014     

Existence of a double random integral with respect to stable measures

In this paper, the authors study a double random integral of the form ∫₀¹∫₀¹f(s,t) M(ds) M(dt), where M(0,t) is a stable process with independent increments. Basically, the Wiener approach is used, and the existence of the above integral is established for a wide class of functions f.     

On the greedy algorithm with random costs

We consider hereditary systems (such as matroids) where the underlying elements have independent random costs, and investigate the cost of the base picked by the greedy algorithm.     

An upper bound for the expected number of real zeros of a random polynomial

Suppose that the n + 1 coefficients of a polynomial of degree n are independent normally distributed random variables with mean 0 and variance 1. We prove that the expected number of real zeros of this polynomial is less than $\text{(}\text{2}\text{π}\text{)}\text{log}\text{n + 1.116}$, and that the constant may be reduced to 1.113 if n is even.     

A greedy algorithm for finding a large 2‐matching on a random cubic graph

A 2‐matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2‐matching U is the number of edges in U and this is at least where n is the number of vertices of G and κ denotes the number of components. In this article, we analyze the performance of a greedy algorithm 2greedy for finding a large 2‐matching on a random 3‐regular graph. We prove that with high probability, the algorithm outputs a 2‐matching U with .     

On the structure of stable random walks

We show that the Cauchy random walk on the line, and the Gaussian random walk on the plane are similar as infinite measure preserving transformations.     

Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs

In this paper we analyze the expected time complexity of the auction algorithm for the matching problem on random bipartite graphs. We first prove that if for every non‐maximum matching on graph G there exist an augmenting path with a length of at most 2l + 1 then the auction algorithm converges after N ? l iterations at most. Then, we prove that the expected time complexity of the auction algorithm for bipartite matching on random graphs with edge probability and c > 1 is w.h.p. This time complexity is equal to other augmenting path algorithms such as the HK algorithm. Furthermore, we show that the algorithm can be implemented on parallel machines with processors and shared memory with an expected time complexity of . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 384–395, 2016     

Infinitely Divisible Limit Processes for the Ewens Sampling Formula

The Ewens sampling formula in population genetics can be viewed as a probability measure on the group of permutations of a finite set of integers. Functional limit theory for processes defined through partial sums of dependent variables with respect to the Ewens sampling formula is developed. Using techniques from probabilistic number theory, it is shown that, under very general conditions, a partial sum process weakly converges in a function space if and only if the corresponding process defined through sums of independent random variables weakly converges. As a consequence of this result, necessary and sufficient conditions for weak convergence to a stable process are established. A counterexample showing that these conditions are not necessary for the one-dimensional convergence is presented. Very few results on the necessity part are known in the literature.     

An upper bound for the diameter of a polytope

The distance between two vertices of a polytope is the minimum number of edges in a path joining them. The diameter of a polytope is the greatest distance between two vertices of the polytope. We show that if P is a d-dimensional polytope with n facets, then the diameter of P is at most $\text{1}\text{3}\text{2}{}^{\mathrm{d?3}}\text{(n?d+}\text{5}\text{2}\text{)}$.     

On the singularity probability of discrete random matrices

Let n be a large integer and Mn be an n by n complex matrix whose entries are independent (but not necessarily identically distributed) discrete random variables. The main goal of this paper is to prove a general upper bound for the probability that Mn is singular. For a constant 0<p<1 and a constant positive integer r, we will define a property p-bounded of exponent r. Our main result shows that if the entries of Mn satisfy this property, then the probability that Mn is singular is at most (p1/r+on(1)). All of the results in this paper hold for any characteristic zero integral domain replacing the complex numbers. In the special case where the entries of Mn are “fair coin flips” (taking the values +1,−1 each with probability 1/2), our general bound implies that the probability that Mn is singular is at most , improving on the previous best upper bound of , proved by Tao and Vu [Terence Tao, Van Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007) 603-628]. In the special case where the entries of Mn are “lazy coin flips” (taking values +1,−1 each with probability 1/4 and value 0 with probability 1/2), our general bound implies that the probability that Mn is singular is at most , which is asymptotically sharp. Our method is a refinement of those from [Jeff Kahn, János Komlós, Endre Szemerédi, On the probability that a random ±1-matrix is singular, J. Amer. Math. Soc. 8 (1) (1995) 223-240; Terence Tao, Van Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007) 603-628]. In particular, we make a critical use of the structure theorem from [Terence Tao, Van Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007) 603-628], which was obtained using tools from additive combinatorics.     

On uniqueness of the spectral representation of stable processes

In this paper we show that any two spectral representations of a symmetric stable process may differ only by a change of variable and a parameter-independent multiplier. Our result can immediately be used either to distinguish or to identify stable processes from various classes of interest. A characterization of stationary stable processes is also provided.Research partially supported by AFOSR Contract No. 90-0168.     

On the expected number of linear complementarity cones intersected by random and semi-random rays

Lemke's algorithm for the linear complementarity problem follows a ray which leads from a certain fixed point (traditionally, the point (1,, 1)^T) to the point given in the problem. The problem also induces a set of 2 ⁿ cones, and a question which is relevant to the probabilistic analysis of Lemke's algorithm is to estimate the expected number of times a (semi-random) ray intersects the boundary between two adjacent cones. When the problem is sampled from a spherically symmetric distribution this number turns out to be exponential. For ann-dimensional problem the natural logarithm of this number is equal to ln()n+o(n), where is approximately 1.151222. This number stands in sharp contrast with the expected number of cones intersected by a ray which is determined by two random points (call itrandom). The latter is only (n/2)+1. The discrepancy between linear behavior (under the random assumption) and exponential behavior (under the semi-random assumption) has implications with respect to recent analyses of the average complexity of the linear programming problem. Surprisingly, the semi-random case is very sensitive to the fixed point of the ray, even when that point is confined to the positive orthant. We show that for points of the form (, ²,, ⁿ )^T the expected number of facets of cones cut by a semi-random ray tends to 1/8n ²+3/8n when tends to zero.This work was done while the author was visiting Stanford University and XEROX-PARC and was supported in part by the National Science Foundation under grants MCS-8300984, ECS-8218181 and ECS-8121741.     

An upper bound on the expectation of simplicial functions of multivariate random variables

We introduce an upper bound on the expectation of a special class of sublinear functions of multivariate random variables defined over the entire Euclidean space without an independence assumption. The bound can be evaluated easily requiring only the solution of systems of linear equations thus permitting implementations in high-dimensional space. Only knowledge on the underlying distribution means and second moments is necessary. We discuss pertinent techniques on dominating general sublinear functions by using simpler sublinear and polyhedral functions and second order quadratic functions.     

An improved probability bound for the Approximate S-Lemma

The purpose of this note is to give a probability bound on symmetric matrices to improve an error bound in the Approximate S-Lemma used in establishing levels of conservatism results for approximate robust counterparts.     

An upper bound for the minimum rank of a graph

For a graph G of order n, the minimum rank of G is defined to be the smallest possible rank over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. We prove an upper bound for minimum rank in terms of minimum degree of a vertex is valid for many graphs, including all bipartite graphs, and conjecture this bound is true over for all graphs, and prove a related bound for all zero-nonzero patterns of (not necessarily symmetric) matrices. Most of the results are valid for matrices over any infinite field, but need not be true for matrices over finite fields.     

An improved bound for the strong chromatic number

Let η > 0 be given. Then there exists d₀ = d₀(η) such that the following holds. Let G be a finite graph with maximum degree at most d ≥ d₀ whose vertex set is partitioned into classes of size α d, where α≥ 11/4 + η. Then there exists a proper coloring of G with αd colors in which each class receives all αd colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:148–158, 2008     

An upper bound for the k-domination number of a graph

The k-domination number of a graph G, γk(G), is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k, then γk(G) ≤ kp/(k + 1).     

An upper bound for the path number of a graph

The path number of a graph G, denoted p(G), is the minimum number of edge-disjoint paths covering the edges of G. Lovász has proved that if G has u odd vertices and g even vertices, then p(G) ≤ 1/2 u + g - 1 ≤ n - 1, where n is the total number of vertices of G. This paper clears up an error in Lovász's proof of the above result and uses an extension of his construction to show that p(G) ≤ 1/2 u + [3/4g] ≤ [3/4n].