A concentration result with application to subgraph count
From MaRDI portal
Abstract: Let H = (V,E) be a k-uniform hypergraph with a vertex set V and an edge set E. Let V_p be constructed by taking every vertex in V independently with probability p. Let X be the number of edges in E that are contained in V_p. We give a condition that guarantees the concentration of X within a small interval around its mean. The applicability of this result is demonstrated by deriving new sub-Gaussian tails for the number of copies of small complete and complete bipartite graphs in the binomial random graph, extending results of Ruci'nski and Vu.
Recommendations
Cites work
- A large deviation result on the number of small subgraphs of a random graph
- Concentration of non‐Lipschitz functions and applications
- Divide and conquer martingales and the number of triangles in a random graph
- On the concentration of multivariate polynomials with small expectation
- Poisson approximation for large deviations
- Sub-Gaussian tails for the number of triangles in G( n, p)
- The infamous upper tail
- Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
- Upper tails for subgraph counts in random graphs
- When are small subgraphs of a random graph normally distributed?
Cited in
(7)- Concentration for Poisson \(U\)-statistics: subgraph counts in random geometric graphs
- Upper tails for arithmetic progressions in random subsets
- Supersaturation for subgraph counts
- On the missing log in upper tail estimates
- Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
- The deletion method for upper tail estimates
- Hölder-type inequalities and their applications to concentration and correlation bounds
This page was built for publication: A concentration result with application to subgraph count
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3119051)
