A note on the growth of topological Sidon sets

We give an estimate for the number of elements in the intersection of topological Sidon sets inR ⁿ with compact convex subsets and deduce a necessary and sufficient conditions for an orbit of a linear transformation ofR ⁿ to be a topological Sidon set.     

Semiconvergence in distribution of random closed sets with application to random optimization problems

The paper considers upper semicontinuous behavior in distribution of sequences of random closed sets. Semiconvergence in distribution will be described via convergence in distribution of random variables with values in a suitable topological space. Convergence statements for suitable functions of random sets are proved and the results are employed to derive stability statements for random optimization problems where the objective function and the constraint set are approximated simultaneously. The author is grateful to two anonymous referees for helpful suggestions.     

An identity on the maximum of a set of random variables

It is shown that if X₁, X₂, …, X_n are symmetric random variables and max(X₁, …, X_n)⁺ = max(0, X₁, …, X_n), then E[max(X₁,…,X_n)⁺]=[max(X₁,X₁,+X₂,+X₁,+X₃,…X₁,+X_n)⁺], and in the case of independent identically distributed symmetric random variables, E[max(X₁, X₂)⁺] = E[(X₁)⁺] + (1/2)E[(X₁ + X₂)⁺], so that for independent standard normal random variables, E[max(X₁, X₂)⁺] = (1/√2π)[1 + (1/√2)].     

On the size of the algebraic difference of two random Cantor sets

In this paper we consider some families of random Cantor sets on the line and investigate the question whether the condition that the sum of Hausdorff dimension is larger than one implies the existence of interior points in the difference set of two independent copies. We prove that this is the case for the so called Mandelbrot percolation. On the other hand the same is not always true if we apply a slightly more general construction of random Cantor sets. We also present a complete solution for the deterministic case. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On the maximum number of copies of H in graphs with given size and order

We study the maximum number $ex\left(n,e,H\right)$ of copies of a graph $H$ in graphs with a given number of vertices and edges. We show that for any fixed graph $H,ex\left(n,e,H\right)$ is asymptotically realized by the quasi‐clique provided that the edge density is sufficiently large. We also investigate a variant of this problem, when the host graph is bipartite.     

The maximum number of maximal independent sets in unicyclic connected graphs

In this paper, we determine the maximum number of maximal independent sets in a unicyclic connected graph. We also find a class of graphs achieving this maximum value.     

The size Ramsey number of short subdivisions of bounded degree graphs

For graphs G and F, write if any coloring of the edges of G with colors yields a monochromatic copy of the graph F. Suppose is obtained from a graph S with s vertices and maximum degree d by subdividing its edges h times (that is, by replacing the edges of S by paths of length h + 1). We prove that there exists a graph G with no more than edges for which holds, provided that . We also extend this result to the case in which Q is a graph with maximum degree d on q vertices with the property that every pair of vertices of degree greater than 2 are distance at least h + 1 apart. This complements work of Pak regarding the size Ramsey number of “long subdivisions” of bounded degree graphs.     

The mean number of sites visited by a pinned random walk

This paper concerns the number Z _n of sites visited up to time n by a random walk S _n having zero mean and moving on the d-dimensional square lattice Z ^d . Asymptotic evaluation of the conditional expectation of Z _n given that S ₀ = 0 and S _n = x is carried out under 2 + δ moment conditions (0 ≤ δ ≤ 2) in the cases d = 2, 3. It gives an explicit form of the leading term and reasonable estimates of the remainder term (depending on δ) valid uniformly in each parabolic region of (x, n). In the case x = 0 the problem has been studied for the simple random walk and its analogue for Brownian motion; the estimates obtained here are finer than or comparable to those found in previous works. Supported in part by Monbukagakusho grand-in-aid no. 15540109.     

A note on the maximum number of triangles in a C5-free graph

We prove that the maximum number of triangles in a -free graph on vertices is at most , improving an estimate of Alon and Shikhelman.     

Moments of an exponential functional of random walks and permutations with given descent sets

The exponential functional of simple, symmetric random walks with negative drift is an infinite polynomial Y = 1 + ξ₁ + ξ₁ξ₂ + ξ₁ξ₂ξ₃ + ⋯ of independent and identically distributed non-negative random variables. It has moments that are rational functions of the variables μ _k = E(ξ ^k ) < 1 with universal coefficients. It turns out that such a coefficient is equal to the number of permutations with descent set defined by the multiindex of the coefficient. A recursion enumerates all numbers of permutations with given descent sets in the form of a Pascal-type triangle. This revised version was published online in August 2006 with corrections to the Cover Date.     

The ζ(2) limit in the random assignment problem

The random assignment (or bipartite matching) problem asks about A_n=min_π ∑c(i, π(i)), where (c(i, j)) is a n×n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations π. Mézard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EA_n→ζ(2)=π²/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ζ(2) limit and of the conjectured limit distribution of edge‐costs and their rank‐orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost‐optimal matching coincides with the optimal matching except on a small proportion of edges. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 381–418, 2001     

The Frobenius problem, sums of powers of integers, and recurrences for the Bernoulli numbers

In the Frobenius problem with two variables, one is given two positive integers a and b that are relative prime, and is concerned with the set of positive numbers NR that have no representation by the linear form ax+by in nonnegative integers x and y. We give a complete characterization of the set NR, and use it to establish a relation between the power sums over its elements and the power sums over the natural numbers. This relation is used to derive new recurrences for the Bernoulli numbers.     

An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm

A random recursive tree on n vertices is either a single isolated vertex (for n=1) or is a vertex v_n connected to a vertex chosen uniformly at random from a random recursive tree on n−1 vertices. Such trees have been studied before [R. Smythe, H. Mahmoud, A survey of recursive trees, Theory of Probability and Mathematical Statistics 51 (1996) 1-29] as models of boolean circuits. More recently, Barabási and Albert [A. Barabási, R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509-512] have used modifications of such models to model for the web and other “power-law” networks.A minimum (cardinality) dominating set in a tree can be found in linear time using the algorithm of Cockayne et al. [E. Cockayne, S. Goodman, S. Hedetniemi, A linear algorithm for the domination number of a tree, Information Processing Letters 4 (1975) 41-44]. We prove that there exists a constant d?0.3745… such that the size of a minimum dominating set in a random recursive tree on n vertices is dn+o(n) with probability approaching one as n tends to infinity. The result is obtained by analysing the algorithm of Cockayne, Goodman and Hedetniemi.     

The problem of identification of parameters by the distribution of the maximum random variable

Suppose that X₁, X₂,…, X_n are independently distributed according to certain distributions. Does the distribution of the maximum of {X₁, X₂,…, X_n} uniquely determine their distributions? In the univariate case, a general theorem covering the case of Cauchy random variables is given here. Also given is an affirmative answer to the above question for general bivariate normal random variables with non-zero correlations. Bivariate normal random variables with nonnegative correlations were considered earlier in this context by T. W. Anderson and S. G. Ghurye.     

About the ratio of the size of a maximum antichain to the size of a maximum level in finite partially ordered sets

LetP be a finite partially ordered set. The lengthl(x) of an elementx ofP is defined by the maximal number of elements, which lie in a chain withx at the top, reduced by one. Letw(P) (d(P)) be the maximal number of elements ofP which have the same length (which form an antichain). Further let . The numbers and as well as all partially ordered sets for which these maxima are attained are determined.     

co-radiant集的等价表示及其在向量优化问题中的应用

作为特殊的抽象凸(凹)集,radiant集和co-radiant集在抽象凸分析和多目标优化问题理论中发挥着重要作用.首先建立radiant集co-radiant集的等价刻画,从而推导出它们的重要性质.然后,将重要性质应用到向量优化问题近似解的刻画中,得到关于近似解集的等价刻画.     

A scaling limit for the length of the longest cycle in a sparse random digraph

We discuss the length of the longest directed cycle in the sparse random digraph , constant. We show that for large there exists a function such that a.s. The function where is a polynomial in . We are only able to explicitly give the values , although we could in principle compute any .