共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
3.
Simone Franchini 《Stochastic Processes and their Applications》2017,127(10):3372-3411
We consider a generalized two-color Polya urn (black and white balls) first introduced by Hill et al. (1980), where the urn composition evolves as follows: let , and denote by the fraction of black balls after step , then at step a black ball is added with probability and a white ball is added with probability . Originally introduced to mimic attachment under imperfect information, this model has found applications in many fields, ranging from Market Share modeling to polymer physics and biology.In this work we discuss large deviations for a wide class of continuous urn functions . In particular, we prove that this process satisfies a Sample-Path Large Deviations principle, also providing a variational representation for the rate function. Then, we derive a variational representation for the limit where is the number of black balls at time , and use it to give some insight on the shape of . Under suitable assumptions on we are able to identify the optimal trajectory. We also find a non-linear Cauchy problem for the Cumulant Generating Function and provide an explicit analysis for some selected examples. In particular we discuss the linear case, which embeds the Bagchi–Pal Model [6], giving the exact implicit expression for in terms of the Cumulant Generating Function. 相似文献
4.
Sergei Bezrukov Dalibor Fronček Steven J. Rosenberg Petr Kovář 《Discrete Mathematics》2008,308(2-3):319-323
5.
In 1962, Erd?s proved that if a graph with vertices satisfies where the minimum degree and , then it is Hamiltonian. For , let , where “” is the “join” operation. One can observe and is not Hamiltonian. As contains induced claws for , a natural question is to characterize all 2-connected claw-free non-Hamiltonian graphs with the largest possible number of edges. We answer this question completely by proving a claw-free analog of Erd?s’ theorem. Moreover, as byproducts, we establish several tight spectral conditions for a 2-connected claw-free graph to be Hamiltonian. Similar results for the traceability of connected claw-free graphs are also obtained. Our tools include Ryjá?ek’s claw-free closure theory and Brousek’s characterization of minimal 2-connected claw-free non-Hamiltonian graphs. 相似文献
6.
Let be integers with , and set and . Because is quadratic in , there exists a such that A theorem by Erd?s states that for , any -vertex nonhamiltonian graph with minimum degree has at most edges, and for the unique sharpness example is simply the graph . Erd?s also presented a sharpness example for each .We show that if and a -connected, nonhamiltonian -vertex graph with has more than edges, then is a subgraph of . Note that whenever . 相似文献
7.
8.
9.
Let be a set of at least two vertices in a graph . A subtree of is a -Steiner tree if . Two -Steiner trees and are edge-disjoint (resp. internally vertex-disjoint) if (resp. and ). Let (resp. ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) -Steiner trees in , and let (resp. ) be the minimum (resp. ) for ranges over all -subset of . Kriesell conjectured that if for any , then . He proved that the conjecture holds for . In this paper, we give a short proof of Kriesell’s Conjecture for , and also show that (resp. ) if (resp. ) in , where . Moreover, we also study the relation between and , where is the line graph of . 相似文献
10.
The slow-coloring game is played by Lister and Painter on a graph . On each round, Lister marks a nonempty subset of the uncolored vertices, scoring points. Painter then gives a color to a subset of that is independent in . The game ends when all vertices are colored. Painter and Lister want to minimize and maximize the total score, respectively. The best score that each player can guarantee is the sum-color cost of , written . The game is an online variant of online sum list coloring.We prove , where is the independence number, and we study when equality holds in the bounds. We compute for graphs with . Among -vertex trees, we prove that is minimized by the star and maximized by the path. We also study . 相似文献
11.
David Gilat Isaac Meilijson Laura Sacerdote 《Stochastic Processes and their Applications》2018,128(6):1849-1856
For a martingale starting at with final variance , and an interval , let be the normalized length of the interval and let be the normalized distance from the initial point to the lower endpoint of the interval. The expected number of upcrossings of by is at most if and at most otherwise. Both bounds are sharp, attained by Standard Brownian Motion stopped at appropriate stopping times. Both bounds also attain the Doob upper bound on the expected number of upcrossings of for submartingales with the corresponding final distribution. Each of these two bounds is at most , with equality in the first bound for . The upper bound on the length covered by during upcrossings of an interval restricts the possible variability of a martingale in terms of its final variance. This is in the same spirit as the Dubins & Schwarz sharp upper bound on the expected maximum of above , the Dubins & Schwarz sharp upper bound on the expected maximal distance of from , and the Dubins, Gilat & Meilijson sharp upper bound on the expected diameter of . 相似文献
12.
Marcel Herzog Patrizia Longobardi Mercede Maj 《Journal of Pure and Applied Algebra》2018,222(7):1628-1642
Denote the sum of element orders in a finite group G by and let denote the cyclic group of order n. Suppose that G is a non-cyclic finite group of order n and q is the least prime divisor of n. We proved that and . The first result is best possible, since for each , k odd, there exists a group G of order n satisfying and the second result implies that if G is of odd order, then . Our results improve the inequality obtained by H. Amiri, S.M. Jafarian Amiri and I.M. Isaacs in 2009, as well as other results obtained by S.M. Jafarian Amiri and M. Amiri in 2014 and by R. Shen, G. Chen and C. Wu in 2015. Furthermore, we obtained some -based sufficient conditions for the solvability of G. 相似文献
13.
Stefan Steinerberger 《Indagationes Mathematicae》2018,29(5):1167-1178
A sequence on the torus is said to exhibit Poissonian pair correlation if the local gaps behave like the spacings of a Poisson random variable, i.e. We show that being close to Poissonian pair correlation for few values of is enough to deduce global regularity statements: if, for some , a set of points satisfies then the discrepancy of the set satisfies . We also show that distribution properties are reflected in the global deviation from the Poissonian pair correlation where the lower bound is conditioned on . The proofs use a connection between exponential sums, the heat kernel on
and spatial localization. Exponential sum estimates are obtained as a byproduct. We also describe a connection to diaphony and several open problems. 相似文献
14.
A matching in a 3-uniform hypergraph is a set of pairwise disjoint edges. A -matching in a 3-uniform hypergraph is a matching of size . Let be a partition of vertices such that and . Denote by the 3-uniform hypergraph with vertex set consisting of all those edges which contain at least two vertices of . Let be a 3-uniform hypergraph of order such that for any two adjacent vertices . In this paper, we prove contains a -matching if and only if is not a subgraph of . 相似文献
15.
16.
17.
18.
Let and denote the maximum degree and the Laplacian spectral radius of a tree , respectively. In this paper we prove that for two trees and on vertices, if and , then , and the bound “” is the best possible. We also prove that for two trees and on vertices with perfect matchings, if and , then . 相似文献
19.
The Turán number is the maximum number of edges in any -vertex graph that does not contain a subgraph isomorphic to . A wheel is a graph on vertices obtained from a by adding one vertex and making adjacent to all vertices of the . We obtain two exact values for small wheels: Given that is already known, this paper completes the spectrum for all wheels up to 7 vertices. In addition, we present the construction which gives us the lower bound in general case. 相似文献