共查询到20条相似文献,搜索用时 15 毫秒
1.
Christos Pelekis 《Graphs and Combinatorics》2016,32(4):1521-1544
Suppose you can colour n biased coins with n colours, all coins having the same bias. It is forbidden to colour both sides of a coin with the same colour, but all other colourings are allowed. Let X be the number of different colours after a toss of the coins. We present a method to obtain an upper bound on a median of X. Our method is based on the analysis of the probability distribution of the number of vertices with even in-degree in graphs whose edges are given random orientations. Our analysis applies to the distribution of the number of vertices with odd degree in random sub-graphs of fixed graphs. It turns out that there are parity restrictions on the random variables that are under consideration. Hence, in order to present our result, we introduce a class of Bernoulli random variables whose total number of successes is of fixed parity and are closely related to Poisson trials conditional on the event that their outcomes have fixed parity. 相似文献
2.
A graph with a trivial automorphism group is said to be rigid. Wright proved (Acta Math 126(1) (1971), 1–9) that for a random graph is rigid whp (with high probability). It is not hard to see that this lower bound is sharp and for with positive probability is nontrivial. We show that in the sparser case , it holds whp that G's 2‐core is rigid. We conclude that for all p, a graph in is reconstructible whp. In addition this yields for a canonical labeling algorithm that almost surely runs in polynomial time with o(1) error rate. This extends the range for which such an algorithm is currently known (T. Czajka and G. Pandurangan, J Discrete Algorithms 6(1) (2008), 85–92). 相似文献
3.
It is shown that every probability measure on the interval [0, 1] gives rise
to a unique infinite random graph g on vertices
{v1,
v2, . . .}
and a sequence of random graphs gn on vertices
{v1, . . . ,
vn}
such that
.
In particular,
for Bernoulli graphs with
stable property Q,
can be strengthened to: probability space (, F, P),
set of infinite graphs
G(Q) ,
F with property Q such
that
.AMS Subject Classification: 05C80, 05C62. 相似文献
4.
A. Krajka 《Acta Appl Math》2007,96(1-3):327-338
Let
be a probability space with a nonatomic measure P and let (S,ρ) be a separable complete metric space. Let {N
n
,n≥1} be an arbitrary sequence of positive-integer valued random variables. Let {F
k
,k≥1} be a family of probability laws and let X be some random element defined on
and taking values in (S,ρ).
In this paper we present necessary and sufficient conditions under which one can construct an array of random elements {X
n,k
,n,k≥1} defined on the same probability space and taking values in (S,ρ), and such that
, and moreover
as n→∞. Furthermore, we consider the speed of convergence
to X as n→∞.
相似文献
5.
In this paper, we prove the following theorems. (i) Let G bea graph of minimum degree 5. If G is embeddable in a surface and satisfies (5)|V(G)|+6()0, then G is edge reconstructible.(ii) Any graph of minimum degree 4 that triangulates a surfaceis edge reconstructible. (iii) Any graph which triangulatesa surface of characteristic 0 is edge reconstructible. 相似文献
7.
Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple
algorithm introduced by Steger and Wormald [10] and prove that it produces an asymptotically uniform random regular graph
in a polynomial time. Precisely, for fixed d and n with d = O(n1/3−ε), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd2). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality
by the second author.
The algorithm works for relatively large d in practical (quadratic) time and can be used to derive many properties of uniform random regular graphs.
* Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship. 相似文献
8.
We introduce a new class of countably infinite random geometric graphs, whose vertices V are points in a metric space, and vertices are adjacent independently with probability p ? (0, 1){p \in (0, 1)} if the metric distance between the vertices is below a given threshold. For certain choices of V as a countable dense set in
\mathbbRn{\mathbb{R}^n} equipped with the metric derived from the L
∞-norm, it is shown that with probability 1 such infinite random geometric graphs have a unique isomorphism type. The isomorphism
type, which we call GR
n
, is characterized by a geometric analogue of the existentially closed adjacency property, and we give a deterministic construction
of GR
n
. In contrast, we show that infinite random geometric graphs in
\mathbbR2{\mathbb{R}^{2}} with the Euclidean metric are not necessarily isomorphic. 相似文献
10.
Edge Colorings of Embedded Graphs 总被引:2,自引:0,他引:2
In his paper, we discuss under what conditions graphs embedded in a surface Σ will be class one.
Received: August 14, 1997 Revised: April 15, 1998 相似文献
11.
12.
13.
14.
Acta Mathematicae Applicatae Sinica, English Series - With applications in communication networks, the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the... 相似文献
15.
d -regular graph G, let M be chosen uniformly at random from the set of all matchings of G, and for let be the probability that M does not cover x.
We show that for large d, the 's and the mean μ and variance of are determined to within small tolerances just by d and (in the case of μ and ) :
Theorem. For any d-regular graph G,
(a)
, so that ,
(b)
,
where the rates of convergence depend only on d.
Received: April 12, 1996 相似文献
16.
Vassilis G. Papanicolaou Effie G. Papageorgiou Dimitris C. Lepipas 《Methodology and Computing in Applied Probability》2012,14(2):285-297
Consider a stochastic process that lives on n-semiaxes joined at the origin. On each ray it behaves as one dimensional Brownian Motion and at the origin it chooses a ray
uniformly at random (Kirchhoff condition). The principal results are the computation of the exit probabilities and certain
other probabilistic quantities regarding exit and occupation times. 相似文献
17.
18.
Let {X
n} be a sequence of i.i.d. random variables and let {k} be a sequence of random indexes. We study the problem of the existence of non-degenerated asymptotic distribution for min{X
1,..., X
n}. 相似文献
19.
孙林 《数学的实践与认识》2015,(3):195-201
设图G是嵌入到欧拉示性数χ(∑)≥0的曲面上的图,χ′(G)和△(G)分别表示图G的边色数和最大度.将证明如果G满足以下条件:1)△(G)≥5;2)图中3-圈和4-圈不相邻;3)图G中没有5-圈的一次剖分,则有χ′(G)=△(G). 相似文献