Probability set functions

A probability set function is interpretable as a probability distribution on binary sequences of fixed length. Cumulants of probability set functions enjoy particularly simple properties which make them more manageable than cumulants of general random variables. We derive some identities satisfied by cumulants of probability set functions which we believe to be new. Probability set functions may be expanded in terms of their cumulants. We derive an expansion which allows the construction of examples of probability set functions whose cumulants are arbitrary, restricted only by their absolute values. It is known that this phenomenon cannot occur for continuous probability distributions. Some particular examples of probability set functions are considered, and their cumulants are computed, leading to a conjecture on the upper bound of the values of cumulants. Moments of probability set functions determined by arithmetical conditions are computed in a final example.Dedicated to our friend, W.A. Beyer. Financial support for this work was derived from the U.S.D.O.E. Human Genome Project, through the Center for Human Genome Studies at Los Alamos National Laboratory, and also through the Center for Nonlinear Studies, Los Alamos National Laboratory, LANL report LAUR-97-323.     

Decomposition of submodular functions

A decomposition theory for submodular functions is described. Any such function is shown to have a unique decomposition consisting of indecomposable functions and certain highly decomposable functions, and the latter are completely characterized. Applications include decompositions of hypergraphs based on edge and vertex connectivity, the decomposition of matroids based on three-connectivity, the Gomory—Hu decomposition of flow networks, and Fujishige’s decomposition of symmetric submodular functions. Efficient decomposition algorithms are also discussed.     

Random walks on quasisymmetric functions

Conditions are provided under which an endomorphism on quasisymmetric functions gives rise to a left random walk on the descent algebra which is also a lumping of a left random walk on permutations. Spectral results are also obtained. Several important random walks are now realized this way: Stanley's QS-distribution results from endomorphisms given by evaluation maps, a-shuffles result from the ath convolution power of the universal character, and the Tchebyshev operator of the second kind introduced recently by Ehrenborg and Readdy yields traditional riffle shuffles. A conjecture of Ehrenborg regarding the spectra for a family of random walks on ab-words is proven. A theorem of Stembridge from the theory of enriched P-partitions is also recovered as a special case.     

Threshold functions

It is shown that every non-trivial monotone increasing property of subsets of a set has a threshold function. This generalises a number of classical results in the theory of random graphs. First author supported by NSF grant MCS 8104854     

On a problem of spencer

LetX ₁, ...,X _n be events in a probability space. Let ϱ_i be the probabilityX _i occurs. Let ϱ be the probability that none of theX _i occur. LetG be a graph on [n] so that for 1 ≦i≦n X _i is independent of ≈X _j ‖(i, j)∉G≈. Letf(d) be the sup of thosex such that if ϱ₁, ..., ϱ _n ≦x andG has maximum degree ≦d then ϱ>0. We showf(1)=1/2,f(d)=(d−1) ^d−1 d ^−d ford≧2. Hence df(d)=1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for ϱ in terms of the ϱ _i andG.     

The diameter of random regular graphs

We give asymptotic upper and lower bounds for the diameter of almost everyr-regular graph onn vertices (n → ∞).     

Exact Distribution of the Occurrence Number for K-tuples Over an Alphabet of Non-Equal Probability Letters

A nucleotide sequence can be considered as a realization of the non-equal-probability independently and identically distributed (niid) model. In this paper we derive the exact distribution of the occurrence number for each K-tuple with respect to the niid model by means of the Goulden-Jackson cluster method. An application of the probability function to get exact expectation curves [9] is presented, accompanied by comparison between the exact approach and the approximate solution.Received October 31, 2004     

Cones of alternating and cut submodular set functions

We describe facets of the cones of alternating set functions and cut submodular set functions generated by directed and undirected graphs and by uniform even hypergraphs. This answers a question asked by L. Lovász at the Bonn Mathematical Programming Conference in 1982. We show that there is a network flow algorithm for minimizing a hypergraph cut set function.     

Sets pooling designs

Pooling desings have previously been used for the efficient identification of distinguished elements of a finite setU. Group testing underlies these designs: For any , a binary result is obtainable, indicating whether or not the number of distinguished elements included inS is zero. The current generalization of pooling designs will enable the efficient identification of distinguished subsets of a finite setU. In this case, for any , a binary result is obtainable, indicating whether or not the number of distinguished subsets included inS is zero. Such designs are called sets pooling designs, comprising standard pooling designs in the special case where all the distinguished subsets are elements. The new designs are similar to the standard designs but are subject to new constraints because the set of subsets included inS is its power set. To illustrate the feasibility of constructing sets pooling designs, random, non-adaptive designs are investigated for the special case where all distinguished subsets have the same size. An optimum probability for including an object in a pool is approximated as a function of the size and number of distinguished subsets, adopting the criterion of minimizing the average number of non-distinguished subsets whose status would not be resolved by the pooling design. Deterministic and adaptive designs are also described.This work was supported by the US Department of Energy under contract W-7405-ENG-36, through a Laboratory Directed Research and Development Grant at Los Alamos National Laboratory.     

A note on global pth powers of rigid analytic functions

Assume that K is a perfect field of characteristic p>0 that is complete with respect to an ultrametric valuation, and let X be a rigid analytic variety over K. Suppose that X is smooth and connected with respect to its Grothendieck topology. Let f be a (global) function on X the differential of which vanishes locally at some point of X; then f is the pth power of a (global) function.     

Harmonic functions on Walsh’s Brownian motion

We examine a variation of two-dimensional Brownian motion introduced by Walsh that can be described as Brownian motion on the spokes of a (rimless) bicycle wheel. We construct the process by randomly assigning angles to excursions of reflecting Brownian motion. Hence, Walsh’s Brownian motion behaves like one-dimensional Brownian motion away from the origin, but differently at the origin as it is immediately sent off in random directions. Given the similarity, we characterize harmonic functions as linear functions on the rays satisfying a slope-averaging property. We also classify superharmonic functions as concave functions on the rays satisfying extra conditions.     

ON α,β DESTRUCTIBLE GRAPHS

ABSTRACT

A connected simple graph G or order v is said to be α,β destructible if α,β are integral factors of v and an α-set of edges, E', exists whose removal from G isolates exactly the vertices in a β-set, V'. Aspects of α,β destructions of graphs considered include associated reconstruction problems, unique α,β destructibility, annihilability and proper division sequences of numbers associated with paths.     

A Fatou theorem for α-harmonic functions

We study functions which are harmonic in the upper half space with respect to (−Δ)^α/2, 0<α<2. We prove a Fatou theorem when the boundary function is L^p-Hölder continuous of order β and βp>1. We give examples to show this condition is sharp.     

An arctic circle theorem for Groves

In earlier work, Jockusch, Propp, and Shor proved a theorem describing the limiting shape of the boundary between the uniformly tiled corners of a random tiling of an Aztec diamond and the more unpredictable ‘temperate zone’ in the interior of the region. The so-called arctic circle theorem made precise a phenomenon observed in random tilings of large Aztec diamonds.Here we examine a related combinatorial model called groves. Created by Carroll and Speyer as combinatorial interpretations for Laurent polynomials given by the cube recurrence, groves have observable frozen regions which we describe precisely via asymptotic analysis of a generating function. Our approach also provides another way to prove the arctic circle theorem for Aztec diamonds.     

Noncommutative symmetric functions and an amazing matrix

We present a simple way to derive the results of Diaconis and Fulman [P. Diaconis, J. Fulman, Foulkes characters, Eulerian idempotents, and an amazing matrix, arXiv:1102.5159] in terms of noncommutative symmetric functions.     

On an isomorphism problem on the closed-set lattice of a graph

Let (G) and V(G) be, respectively, the closed-set lattice and the vertex set of a graph G. Any lattice isomorphism : V(G)(G) induces a bijection : V(G)V(G) such that for each x in V(G), (x)=x' in V(G') iff ({x})={x'}. A graph G is strongly sensitive if for any graph G' and any lattice isomorphism : (G)(G), the bijection induced by is a graph isomorphism of G onto G'. In this paper we present some sufficient conditions for graphs to be strongly sensitive and prove in particular that all C ₄-free graphs and all covering graphs of finite lattices are strongly sensitive.     

Traces of oscillating functions

We show that the trace of an indefinitely oscillating function on a subspace of ^d is not always indefinitely oscillating. In the periodic case, the number of oscillations of the trace depends on the regularity of the function. In the general case, we exhibit a definitive counter-example.     

Matrices with prescribed row,column and block sums

The main result of the paper is Theorem 1. It concerns the sets of integral symmetric matrices with given block partition and prescribed row, column and block sums. It is shown that by interchanges preserving these sums we can pass from any two matrices, one from each set, to the other two ones falling close together as much as possible. One of the direct corollaries of Theorem 1 is substantiating the fact that any realization ofr-graphical integer-pair sequence can be obtained from any other one byr-switchings preserving edge degrees. This result is also of interest in connection with the problem of determinings-complete properties. In the special cases Theorem 1 includes a number of well-known results, some of which are presented.