The Number of Seymour Vertices in Random Tournaments and Digraphs

Seymour’s distance two conjecture states that in any digraph there exists a vertex (a “Seymour vertex”) that has at least as many neighbors at distance two as it does at distance one. We explore the validity of probabilistic statements along lines suggested by Seymour’s conjecture, proving that almost surely there are a “large” number of Seymour vertices in random tournaments and “even more” in general random digraphs.     

Quasi-random hypergraphs

We introduce an equivalence class of varied properties for hypergraphs. Any hypergraph possessing any one of these properties must of necessity possess them all. Since almost all random hypergraphs share these properties, we term these properties quasi-random. With these results, it becomes quite easy to show that many natural explicit constructions result in hypergraphs which imitate random hypergraphs in a variety of ways.     

Rectangular random matrices, related convolution

We characterize asymptotic collective behavior of rectangular random matrices, the sizes of which tend to infinity at different rates. It appears that one can compute the limits of all noncommutative moments (thus all spectral properties) of the random matrices we consider because, when embedded in a space of larger square matrices, independent rectangular random matrices are asymptotically free with amalgamation over a subalgebra. Therefore, we can define a “rectangular-free convolution”, which allows to deduce the singular values of the sum of two large independent rectangular random matrices from the individual singular values. This convolution is linearized by cumulants and by an analytic integral transform, that we called the “rectangular R-transform”.     

Generalizations of tournaments: A survey

We survey results concerning various generalizations of tournaments. The reader will see that tournaments are by no means the only class of directed graphs with a very rich structure. We describe, among numerous other topics mostly related to paths and cycles, results on hamiltonian paths and cycles. The reader will see that although these problems are polynomially solvable for all of the classes described, they can be highly nontrivial, even for these “tournament-like” digraphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 171–202, 1998     

More on quasi-random graphs,subgraph counts and graph limits

We study some properties of graphs (or, rather, graph sequences) defined by demanding that the number of subgraphs of a given type, with vertices in subsets of given sizes, approximatively equals the number expected in a random graph. It has been shown by several authors that several such conditions are quasi-random, but that there are exceptions. In order to understand this better, we investigate some new properties of this type. We show that these properties too are quasi-random, at least in some cases; however, there are also cases that are left as open problems, and we discuss why the proofs fail in these cases.The proofs are based on the theory of graph limits; and on the method and results developed by Janson (2011), this translates the combinatorial problem to an analytic problem, which then is translated to an algebraic problem.     

“Procedural” values for cooperative games

This paper introduces a new notion of a “procedural” value for cooperative TU games. A procedural value is determined by an underlying procedure of sharing marginal contributions to coalitions formed by players joining in random order. We consider procedures under which players can only share their marginal contributions with their predecessors in the ordering, and study the set of all resulting values. The most prominent procedural value is, of course, the Shapley value obtaining under the simplest procedure of every player just retaining his entire marginal contribution. But different sharing rules lead to other interesting values, including the “egalitarian solution” and the Nowak and Radzik “solidarity value”. All procedural values are efficient, symmetric and linear. Moreover, it is shown that these properties together with two very natural monotonicity postulates characterize the class of procedural values. Some possible modifications and generalizations are also discussed. In particular, it is shown that dropping one of monotonicity axioms is equivalent to allowing for sharing marginal contributions with both predecessors and successors in the ordering.     

Maximal product of primes whose sum is bounded

A modification of a scheme of allocating a random number of particles to cells is considered in which particles are allocated according to some multinomial scheme “in groups” with a random number of particles in each. The asymptotic properties of the distribution of the number of trials (allocated “groups” of particles) needed to fill a given number of cells are investigated.     

Complete balanced Howell rotations for 8k+5 teams

Complete balanced Howell rotations are mathematical designs for highly structured paired-comparison experiments. They have been widely used in bridge tournaments, and many special cases are applicable to round-robin tournaments for all kinds of sports. In this paper we construct complete balanced Howell rotations of 8k + 5 teams, for 8k + 5 a prime power greater than 5. We also show that “table balanced” complete balanced Howell rotations for 8k + 5 teams do not exist unless 8k + 5 is the sum of two squares of integers.     

Hypergraphs,Quasi-randomness,and Conditions for Regularity

Haviland and Thomason and Chung and Graham were the first to investigate systematically some properties of quasi-random hypergraphs. In particular, in a series of articles, Chung and Graham considered several quite disparate properties of random-like hypergraphs of density 1/2 and proved that they are in fact equivalent. The central concept in their work turned out to be the so called deviation of a hypergraph. They proved that having small deviation is equivalent to a variety of other properties that describe quasi-randomness. In this paper, we consider the concept of discrepancy for k-uniform hypergraphs with an arbitrary constant density d (0<d<1) and prove that the condition of having asymptotically vanishing discrepancy is equivalent to several other quasi-random properties of $\text{H}$, similar to the ones introduced by Chung and Graham. In particular, we prove that the correct “spectrum” of the s-vertex subhypergraphs is equivalent to quasi-randomness for any s⩾2k. Our work may be viewed as a continuation of the work of Chung and Graham, although our proof techniques are different in certain important parts.     

The phase transition in inhomogeneous random graphs

The “classical” random graph models, in particular G(n,p), are “homogeneous,” in the sense that the degrees (for example) tend to be concentrated around a typical value. Many graphs arising in the real world do not have this property, having, for example, power‐law degree distributions. Thus there has been a lot of recent interest in defining and studying “inhomogeneous” random graph models. One of the most studied properties of these new models is their “robustness”, or, equivalently, the “phase transition” as an edge density parameter is varied. For G(n,p), p = c/n, the phase transition at c = 1 has been a central topic in the study of random graphs for well over 40 years. Many of the new inhomogeneous models are rather complicated; although there are exceptions, in most cases precise questions such as determining exactly the critical point of the phase transition are approachable only when there is independence between the edges. Fortunately, some models studied have this property already, and others can be approximated by models with independence. Here we introduce a very general model of an inhomogeneous random graph with (conditional) independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p = c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real‐world graphs. Our model includes as special cases many models previously studied. We show that, under one very weak assumption (that the expected number of edges is “what it should be”), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze. We also consider other properties of the model, showing, for example, that when there is a giant component, it is “stable”: for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n). © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 31, 3–122, 2007     

On local characterizations of Hamiltonian tournaments

We characterize the hamiltonian tournaments that admits exactly one spanning cycle and the hamiltonian tournaments with the least number of 3-cycles by their hamiltonian subtournaments which have the same properties respectively.     

Quasi-randomness and the distribution of copies of a fixed graph

We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices.     

On the differentiability of a class of stationary gaussian processes

For a stationary Gaussian process either almost all sample paths are almost everywhere differentiable or almost all sample paths are almost nowhere differentiable. In this paper it is shown by means of an example involving a random lacunary trigonometric series that “almost everywhere differentiable” and “almost nowhere differentiable” cannot in general be replaced by “everywhere differentiable” and “nowhere differentiable”, respectively.     

A simple algorithm for tighter exact upper confidence bounds with rare attributes in finite universes

When attributes are rare and few or none are observed in the selected sample from a finite universe, sampling statisticians are increasingly being challenged to use whatever methods are available to declare with high probability or confidence that the universe is near or completely attribute-free. This is especially true when the attribute is undesirable. Approximations such as those based on normal theory are frequently inadequate with rare attributes. For simple random sampling without replacement, an appropriate probability distribution for statistical inference is the hypergeometric distribution. But even with the hypergeometric distribution, the investigator is limited from making claims of attribute-free with high confidence unless the sample size is quite large using nonrandomized techniques. For students in statistical theory, this short article seeks to revive the question of the relevance of randomized methods. When comparing methods for construction of confidence bounds in discrete settings, randomization methods are useful in fixing like confidence levels and hence facilitating the comparisons. Under simple random sampling, this article defines and presents a simple algorithm for the construction of exact “randomized” upper confidence bounds which permit one to possibly report tighter bounds than those exact bounds obtained using “nonrandomized” methods. A general theory for exact randomized confidence bounds is presented in Lehmann (1959, p. 81), but Lehmann's development requires more mathematical development than is required in this application. Not only is the development of these “randomized” bounds in this paper elementary, but their desirable properties and their link with the usual nonrandomized bounds are easy to see with the presented approach which leads to the same results as would be obtained using the method of Lehmann.     

Search heuristics and the influence of non-perfect randomness: examining Genetic Algorithms and Simulated Annealing

Simulated Annealing and Genetic Algorithms are important methods to solve discrete optimization problems and are often used to find approximate solutions for diverse NP-complete problems. They depend on randomness to change their current configuration and transition to a new state. In Simulated Annealing, the random choice influences the construction of the new state as well as the acceptance of that new state. In Genetic Algorithms, selection, mutation and crossover depend on random choices. We experimentally investigate the robustness of the two generic search heuristics when using pseudorandom numbers of limited quality. To this end, we conducted experiments with linear congruential generators of various period lengths, a Mersenne Twister with artificially reduced period lengths as well as quasi-random numbers as the source of randomness. Both heuristics were used to solve several instances of the Traveling Salesman Problem in order to compare optimization results. Our experiments show that both Simulated Annealing and the Genetic Algorithm produce inferior solutions when using random numbers with small period lengths or quasi-random numbers of inappropriate dimension. The influence on Simulated Annealing, however, is more severe than on Genetic Algorithms. Interestingly, we found that when using diverse quasi-random sequences, the Genetic Algorithm outperforms its own results using quantum random numbers.     

Generalized self-adjustment method for statistical mechanics of composite materials

A new method is developed for the statistical mechanics of composite materials — the generalized selfadjustment method — which makes it possible to reduce the problem of predicting effective elastic properties of composites with random structures to the solution of two simpler “averaged” problems of an inclusion with transitional layers in a medium with the desired effective elastic properties. The inhomogeneous elastic properties and dimensions of the transitional layers take into account both the “approximate” order of mutual positioning, and also the variation in the dimensions and elastics properties of inclusions through appropriate special averaged indicator functions of the random structure of the composite. A numerical calculation of averaged indicator functions and effective elastic characteristics is performed by the generalized self-adjustment method for a unidirectional fiberglass on the basis of various models of actual random structures in the plane of isotropy.     

A generalized real-valued measure of the inequality associated with a fuzzy random variable

Fuzzy random variables have been introduced by Puri and Ralescu as an extension of random sets. In this paper, we first introduce a real-valued generalized measure of the “relative variation” (or inequality) associated with a fuzzy random variable. This measure is inspired in Csiszár's f-divergence, and extends to fuzzy random variables many well-known inequality indices. To guarantee certain relevant properties of this measure, we have to distinguish two main families of measures which will be characterized. Then, the fundamental properties are derived, and an outstanding measure in each family is separately examined on the basis of an additive decomposition property and an additive decomposability one. Finally, two examples illustrate the application of the study in this paper.     

Generalized steinhaus graphs

A generalized Steinhaus graph of order n and type s is a graph with n vertices whose adjacency matrix (a_i,j) satisfies the relation where 2 ≦i≦n?1, i + s(i ? 1 ≦ j ≦ n, c_r,i,j ? {0,1} for all 0 ≦ r ≦ s(i) ?1 and c_s(i)?1,i,j = 1. The values of s(i) and c_r,i,j are fixed but arbitrary. Generalized Steinhaus graphs in which each edge has probability ½ are considered. In an article by A. Blass and F. Harary [“Properties of Almost All Graphs and Complexes,” Journal of Graph Theory, Vol. 3 (1976), pp. 225–240], a collection of first-order axioms are given from which any first-order property in graph theory or its negation can be deduced. We show that almost all generalized Steinhaus graphs satisfy these axioms. Thus the first-order theory of random generalized Steinhaus graphs is identical with the theory of random graphs. Quasi-random properties of graphs are described by F. R. K. Chung, R. L. Graham, and R. M. Wilson, [“Quasi-Random Graphs,” Combinatorica, Vol. 9 (1989), pp. 345–362]. We conclude by demonstrating that almost all generalized Steinhaus graphs obey Property 2 and hence all equivalent quasi-random properties. © 1996 John Wiley & Sons, Inc.     

The geometry of III-conditioning

Numerous problems in numerical analysis, including matrix inversion, eigen-value calculations, and polynomial zero finding, share the following property: the difficulty of solving a given problem is large when the distance from that problem to the nearest “ill-posed” one is small. For example, the closer a matrix is to the set of noninvertible matrices, the larger its condition number with respect to inversion. We show that the sets of ill-posed problems for matrix inversion, eigen-problems, and polynomial zero finding all have a common algebraic and geometric structure which lets us compute the probability distribution of the distance from a “random” problem to the set. From this probability distribution we derive, for example, the distribution of the condition number of a random matrix. We examine the relevance of this theory to the analysis and construction of numerical algorithms destined to be run in finite precision arithmetic.