The random assignment (or bipartite matching) problem asks about A, min(pi) Sigma (n)(i=1) c(i, pi (i)), where (c(i, j)) is a n x n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is ...
详细信息
The random assignment (or bipartite matching) problem asks about A, min(pi) Sigma (n)(i=1) c(i, pi (i)), where (c(i, j)) is a n x n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations pi. Mezard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EA(n) --> zeta (2) = pi (2)/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Herl we construct the optimal matching on the infinite tree. This yields a rigorous proof of the zeta (2) limit and of the conjectured limit distribution od 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. (C) 2001 John Wiley & Sons, Inc.
This paper examines a problem in enumerative and asymptotic combinatorics involving the classical structure of integer compositions. What is sought is an analysis on average and in distribution of the length of the lo...
详细信息
This paper examines a problem in enumerative and asymptotic combinatorics involving the classical structure of integer compositions. What is sought is an analysis on average and in distribution of the length of the longest run of consecutive equal parts in a composition of size n. The problem was posed by Herbert Wilf at the Analysis of Algorithms conference in July 2009 (see arXiv:0906.5196). (C) 2014 Elsevier B.V. All rights reserved.
Given a subset W of an abelian group G, a subset C is called an additive complement for W if W + C = G;if, moreover, no proper subset of C has this property, then we say that C is a minimal complement for W. It is nat...
详细信息
Given a subset W of an abelian group G, a subset C is called an additive complement for W if W + C = G;if, moreover, no proper subset of C has this property, then we say that C is a minimal complement for W. It is natural to ask which subsets C can arise as minimal complements for some W. We show that in a finite abelian group G, every non-empty subset C of size vertical bar C vertical bar <= 2(2)/(3)vertical bar G vertical bar(1/3)/((3e log vertical bar G vertical bar)(2/3) is a minimal complement for some W. As a corollary, we deduce that every finite non-empty subset of an infinite abelian group is a minimal complement. We also derive several analogous results for "dual" problems about maximal supplements. (C) 2020 Elsevier Inc. All rights reserved.
We prove a Fortuin-Kasteleyn-Ginibre-type inequality for the lattice of compositions of the integer n with at most r parts. As an immediate application we get a wide generalization of the classical Alexandrov-Fenchel ...
详细信息
We prove a Fortuin-Kasteleyn-Ginibre-type inequality for the lattice of compositions of the integer n with at most r parts. As an immediate application we get a wide generalization of the classical Alexandrov-Fenchel inequality for mixed volumes and of Teissier's inequality for mixed covolumes. (C) 2016 Elsevier Inc. All rights reserved.
This paper presents works of the Kiev school of theoretical cryptography that are carried out mainly during the last two decades in the fields of cryptographic methods of information security, cryptanalysis, and relat...
详细信息
This paper presents works of the Kiev school of theoretical cryptography that are carried out mainly during the last two decades in the fields of cryptographic methods of information security, cryptanalysis, and related mathematical disciplines.
One of the fundamental invariants connecting algebra and geometry is the degree of an ideal. In this paper we derive the probabilistic behavior of degree with respect to the versatile Erdos-Renyi-type model for random...
详细信息
One of the fundamental invariants connecting algebra and geometry is the degree of an ideal. In this paper we derive the probabilistic behavior of degree with respect to the versatile Erdos-Renyi-type model for random monomial ideals. We study the staircase structure associated to a monomial ideal, and show that in the random case the shape of the staircase diagram is approximately hyperbolic, and this behavior is robust across several random models. Since the discrete volume under this staircase is related to the summatory higher-order divisor function studied in number theory, we use this connection and our control over the shape of the staircase diagram to derive the asymptotic degree of a random monomial ideal. Another way to compute the degree of a monomial ideal is with a standard pair decomposition. This paper derives bounds on the number of standard pairs of a random monomial ideal indexed by any subset of the ring variables. The standard pairs indexed by maximal subsets give a count of degree, as well as being a more nuanced invariant of the random monomial ideal.
We investigate properties of random mappings whose core is composed of derangements as opposed to permutations. Such mappings arise as the natural framework for studying the Screaming Toes game described, for example,...
详细信息
We investigate properties of random mappings whose core is composed of derangements as opposed to permutations. Such mappings arise as the natural framework for studying the Screaming Toes game described, for example, by Peter Cameron. This mapping differs from the classical case primarily in the behaviour of the small components, and a number of explicit results are provided to illustrate these differences.
The Entropy/Influence conjecture, raised by Friedgut and Kalai (1996)[9[, seeks to relate two different measures of concentration of the Fourier coefficients of a Boolean function. Roughly saying, it claims that if th...
详细信息
The Entropy/Influence conjecture, raised by Friedgut and Kalai (1996)[9[, seeks to relate two different measures of concentration of the Fourier coefficients of a Boolean function. Roughly saying, it claims that if the Fourier spectrum is "smeared out", then the Fourier coefficients are concentrated on "high" levels. In this note we generalize the conjecture to biased product measures on the discrete cube. (C) 2012 Published by Elsevier B.V.
Since the early 20005 physicists have developed an ingenious but non-rigorous formalism called the cavity method to put forward precise conjectures on phase transitions in random problems (Mezard et al., 2002 [37]). T...
详细信息
Since the early 20005 physicists have developed an ingenious but non-rigorous formalism called the cavity method to put forward precise conjectures on phase transitions in random problems (Mezard et al., 2002 [37]). The cavity method predicts that the satisfiability threshold in the random k-SAT problem is r(k-SAT) = 2(k) in 2 - 1/2 (1 + ln2) + epsilon(k), with lim(k ->infinity) epsilon(k) = 0 (Mertens et al., 2006 [35]). This paper contains a proof of the conjecture. (C) 2015 Elsevier Inc. All rights reserved.
In this paper, we apply the Turan sieve and the simple sieve developed by R. Murty and the first author to study problems in random graph theory. In particular, we obtain upper and lower bounds on the probability of a...
详细信息
In this paper, we apply the Turan sieve and the simple sieve developed by R. Murty and the first author to study problems in random graph theory. In particular, we obtain upper and lower bounds on the probability of a graph on n vertices having diameter 2 (or diameter 3 in the case of bipartite graphs) with edge probability p where the edges are chosen independently. An interesting feature revealed in these results is that the Turan sieve and the simple sieve "almost completely" complement each other. As a corollary to our result, we note that the probability of a random graph having diameter 2 approaches 1 as n? oo for constant edge probability p = 1/2.
暂无评论