On z-analogue of Stepanov-Lomonosov-Polesskii inequality

详细信息    查看全文

• 作者：Boris Pittel
• 关键词：Random graphs ; Connectedness ; Directed ; Enumeration ; Martingale ; Bounds
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：November, 2013
• 年：2013
• 卷：103
• 期：6
• 页码：679-688
• 全文大小：246 K

文摘

Stepanov始s inequality and its various extensions provide an upper bound for connectedness probability for a Bernoulli-type random subgraph of a given graph. We have found an analogue of this bound for the expected value of the connectedness-event indicator times a positive z raised to the number of edges in the random subgraph. We demonstrate the power of this bound by a quick derivation of a relatively sharp bound for the number of the spanning connected, sparsely edged, subgraphs of a high-degree regular graph.