检索结果-内蒙古大学图书馆

Extending Wormald's differential equation method to one-sided bounds

combinatorics PROBABILITY AND COMPUTING 2025年

作者： Bennett, Patrick Macrury, Calum Western Michigan Univ Dept Math Kalamazoo MI 49008 USA Columbia Univ Grad Sch Business New York NY USA

In this note, we formulate a 'one-sided' version of Wormald's differential equation method. In the standard 'two-sided' method, one is given a family of random variables that evolve over time and which satisfy some conditions, including a tight estimate of the expected change in each variable over one-time step. These estimates for the expected one-step changes suggest that the variables ought to be close to the solution of a certain system of differential equations, and the standard method concludes that this is indeed the case. We give a result for the case where instead of a tight estimate for each variable's expected one-step change, we have only an upper bound. Our proof is very simple and is flexible enough that if we instead assume tight estimates on the variables, then we recover the conclusion of the standard differential equation method.

关键词： Differential equation method dynamic concentration probabilistic combinatorics random processes

来源：评论

学校读者我要写书评

暂无评论

Global Offensive Alliances and Groupies in Heterogeneous Random Graphs

引用

METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY 2025年第1期27卷 1-14页

作者： Shang, Yilun Northumbria Univ Dept Comp & Informat Sci Newcastle NE1 8ST England

A vertex subset S of a graph G is a global offensive alliance if every non-member v of S has at least as many neighbors inside S as outside S in the closed neighborhood of v. The global offensive alliance number gamma G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma _G$$\end{document} is the cardinality of a minimal global offensive alliance. A vertex is a groupie if its degree is not less than the mean of the degrees of its neighbors. The number of groupies in G is denoted by eta G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\eta _G$$\end{document}. In this paper, we study these two sort of orthogonal concepts over a heterogenous random graph G obtained by including each edge e from a complete graph Kn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_n$$\end{document} of order n with an individual probability pn(e)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_n(e)$$\end{document} independently. For a complete t-ary tree T with height 2, gamma T=eta T=t\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma _T=\eta _T=t$$\end{document}. In the random graph sett

关键词： Global offensive alliance Random graph Groupie Neighbor probabilistic combinatorics

来源：评论

学校读者我要写书评

暂无评论

The "Power of Few" Phenomenon: The Sparse Case

引用

RANDOM STRUCTURES & ALGORITHMS 2025年第1期66卷

作者： Tran, Baolinh Vu, Van Yale Univ Dept Math New Haven CT 06520 USA

The "majority dynamics" process on a social network begins with an initial phase, where the individuals are split into two competing parties, Red and Blue. Every day, everyone updates their affiliation to match the majority among those of their friends. While studying this process on Erd & ouml;s-R & eacute;nyi G(n,p)$$ G\left(n,p\right) $$ random graph (with constant density), the authors discovered the "Power of Few" phenomenon, showing that a very small advantage to one side already guarantees that everybody will unanimously join that side after just a few days with overwhelming probability. For example, when p=1/2$$ p=1/2 $$, then 10 extra members guarantee this unanimity with a 90% chance, regardless of the value of n$$ n $$. In this article, we study this phenomenon for sparse random graphs. It is clear that below the connectivity threshold, the phenomenon ceases to hold, as the isolated vertices never change their colors. We show that it holds for every density above the threshold. To make the process more realistic, we also assume that individuals can randomly activate their accounts to post their opinions and observe their neighbors (just as we do on social media). We prove that the phenomenon is robust under this assumption. To motivate further research, we also state a number of open questions with supportive numerical experiments.

关键词： majority dynamics percolation probabilistic combinatorics probabilistic graph theory random graphs

来源：评论

学校读者我要写书评

暂无评论

Markov chains generating random permutations and set partitions

引用

STOCHASTIC PROCESSES AND THEIR APPLICATIONS 2024年 178卷

作者： Stark, Dudley Queen Mary Univ London London E1 4NS England

The Chinese Restaurant Process may be considered to be a Markov chain which generates permutations on n elements proportionally to absorption probabilities theta(| pi |) , theta > 0 , where |pi| is the number of cycles of permutation pi . We prove a theorem which provides a way of finding Markov chains, restricted to directed graphs called arborescences, and with given absorption probabilities. We find transition probabilities for the Chinese Restaurant Process arborescence with variable absorption probabilities. The method is applied to an arborescence constructing set partitions, resulting in an analogue of the Chinese Restaurant Process for set partitions. We also apply our method to an arborescence for the Feller Coupling Process. We show how to modify the Chinese Restaurant Process, its set partition analogue, and the Feller Coupling Process to generate derangements and set partitions having no blocks of size one.

关键词： Chinese Restaurant Process Feller coupling Absorbing Markov chain probabilistic combinatorics

来源：评论

学校读者我要写书评

暂无评论

Logarithmically Larger Deletion Codes of All Distances

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第1期70卷 125-130页

作者： Alon, Noga Bourla, Gabriela Graham, Ben He, Xiaoyu Kravitz, Noah Princeton Univ Dept Math Princeton NJ 08544 USA Tel Aviv Univ Sch Math Sci IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

The deletion distance between two binary words u, v E {0, 1}(n) is the smallest k such that u and v share a common subsequence of length n-k. A set C of binary words of length n is called a k-deletion code if every pair of distinct words in C has deletion distance greater than k. In 1965, Levenshtein initiated the study of deletion codes by showing that, for k > 1 fixed and n going to infinity, a k-deletion code C subset of {0, 1}(n) of maximum size satisfies Omega(k)(2(n)/n(2k)) <= |C| <= O-k(2(n)/n(k)). We make the first asymptotic improvement to these bounds by showing that there exist k-deletion codes with size at least Omega(k)(2(n) log n/n(2k)). Our proof is inspired by Jiang and Vardy's improvement to the classical Gilbert-Varshamov bounds. We also establish several related results on the number of longest common subsequences and shortest common supersequences of a pair of words with given length and deletion distance.

关键词： Codes Mathematics Electronic mail Standards Indexes Upper bound Synchronization Deletion codes longest common subsequence probabilistic combinatorics

来源：评论

学校读者我要写书评

暂无评论

Dense subgraphs in random graphs

引用

DISCRETE APPLIED MATHEMATICS 2019年 260卷 66-74页

作者： Balister, Paul Bollobas, Bela Sahasrabudhe, Julian Veremyev, Alexander Univ Memphis Dept Math Sci Memphis TN 38152 USA Univ Cambridge Dept Pure Math & Math Stat Cambridge CB3 0WB England London Inst Math Sci 35a South St London W1K 2XF England Inst Nacl Matemat Pura & Aplicada IMPA Estr Dona Castorina110 Jardim Bot BR-22460320 Rio De Janeiro RJ Brazil Univ Cambridge Peterhouse Cambridge CB2 1RD England Univ Cent Florida Ind Engn & Management Syst Orlando FL 32816 USA

For a constant gamma is an element of[0, 1] and a graph G, let omega(gamma) (G) be the largest integer k for which there exists a k-vertex subgraph of G with at least gamma((k)(2)) edges. We show that if 0 < p < gamma < 1 then omega(gamma) (G(n, p)) is concentrated on a set of two integers. More precisely, with alpha(gamma, p) = gamma log gamma/p + (1 - gamma) log 1-gamma/1-p, we show that omega(gamma) (G(n), (p)) is one of the two integers closest to 2/alpha(gamma, p)(log n -log log n+log e alpha(gamma, p)/2)+1/2, with high probability. While this situation .P) parallels that of cliques in random graphs, a new technique is required to handle the more complicated ways in which these "quasi-cliques" may overlap. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Cliques Random Graphs probabilistic combinatorics Dense Clusters Networks in Sociometry Erdos-Renyi Random Graph Binomial Random Graph

来源：评论

学校读者我要写书评

暂无评论

The Feller Coupling for random derangements

引用

STOCHASTIC PROCESSES AND THEIR APPLICATIONS 2022年 150卷 1139-1164页

作者： Da Silva, Poly H. Jamshidpey, Arash Tavare, Simon Columbia Univ Dept Stat 1255 Amsterdam Ave New York NY 10027 USA Columbia Univ Dept Math 2990 Broadway New York NY 10027 USA Columbia Univ Irving Inst Canc Dynam Suite 6011190 Amsterdam AveSchermerhorn Hall New York NY 10027 USA

We study derangements of {1, 2, ... , n} under the Ewens distribution with parameter theta. We give basic properties of derangements, such as the moments and marginal distributions of the cycle counts, the number of cycles, and asymptotic distributions for large n, and we construct, for any given n, a {0, 1}-valued non-homogeneous Markov chain eta(<-(n)) with the property that the counts of lengths of spacings between the 1s have the same distribution as the cycle counts of the random derangement of size n. Unlike the Feller Coupling, this chain does not couple realizations for different values of n - the chain must be rerun to get derangements of other sizes. To resolve this issue we construct another {0, 1}-valued Markov chain eta whose law coincides with that of the Feller Coupling conditional on no consecutive 1s. The distribution of eta, the so-called "Feller Coupling for random derangements ", arises as the weak limit as n & RARR;& INFIN;of the distributions of eta(<-(n)). Consequently, the asymptotic behavior of finite random derangements may be studied via this coupling. The rate of convergence of eta(<-(n)) to eta is studied via an estimate of their total variation distance. We provide extensive comparisons of these methods, and show that the Markov chain methods generate derangements in time independent of theta for a given n and linear in the size of the derangement. (c) 2021 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/4.0/).

关键词： Feller Coupling Simulation Poisson approximation Poisson-Dirichlet and GEM distributions probabilistic combinatorics

来源：评论

学校读者我要写书评

暂无评论

A bipartite version of the Erdos-McKay conjecture

引用

combinatorics PROBABILITY & COMPUTING 2023年第3期32卷 465-477页

作者： Long, Eoin Ploscaru, Laurentiu Univ Birmingham Sch Math Birmingham W Midlands England

An old conjecture of Erdos and McKay states that if all homogeneous sets in an n-vertex graph are of order O(log n) then the graph contains induced subgraphs of each size from {0, 1,..., Omega(n(2))}. We prove a bipartite analogue of the conjecture: if all balanced homogeneous sets in an nxn bipartite graph are of order O(log n), then the graph contains induced subgraphs of each size from {0, 1,..., Omega(n(2))}.

关键词： Ramsey theory homogeneous sets edge sizes probabilistic combinatorics

来源：评论

学校读者我要写书评

暂无评论

Distribution of Descents in Matchings

引用

ANNALS OF combinatorics 2019年第1期23卷 73-87页

作者： Kim, Gene B. Univ Southern Calif Dept Math Los Angeles CA 90089 USA

The distribution of descents in certain conjugacy classes of Sn has been previously studied, and it is shown that its moments have interesting properties. This paper provides a bijective proof of the symmetry of the descents and major indices of matchings (also known as fixed point free involutions) and uses a generating function approach to prove an asymptotic normality theorem for the number of descents in matchings.

关键词： Enumerative combinatorics probabilistic combinatorics Central limit theorem

来源：评论

学校读者我要写书评

暂无评论

Rigorous analysis of a randomised number field sieve

引用

JOURNAL OF NUMBER THEORY 2018年 187卷 92-159页

作者： Lee, Jonathan D. Venkatesan, Ramarathnam Univ Oxford Math Inst Oxford England Microsoft Res Redmond Redmond WA USA Microsoft Res India Bengaluru India

Factorisation of integers n is of number theoretic and cryptographic significance. The Number Field Sieve (NFS) introduced circa 1990, is still the state of the art algorithm, but no rigorous proof that it halts or generates relationships is known. We propose and analyse an explicitly randomised variant. For each n, we show that these randomised variants of the NFS and Coppersmith's multiple polynomial sieve find congruences of squares in expected times matching the best-known heuristic estimates. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Factoring probabilistic combinatorics Additive number theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：