Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA limit theorem for the $1$st Betti number of layer-$1$ subgraphs in random graphs
179
0
0.0
(
0
)
Added by
Minghao Tian
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We initiate the study of local topology of random graphs. The high level goal is to characterize local motifs in graphs. In this paper, we consider what we call the layer-$r$ subgraphs for an input graph $G = (V,E)$: Specifically, the layer-$r$ subgraph at vertex $u in V$, denoted by $G_{u; r}$, is the induced subgraph of $G$ over vertex set $Delta_{u}^{r}:= left{v in V: d_G(u,v) = r right}$, where $d_G$ is shortest-path distance in $G$. Viewing a graph as a 1-dimensional simplicial complex, we then aim to study the $1$st Betti number of such subgraphs. Our main result is that the $1$st Betti number of layer-$1$ subgraphs in ErdH{o}s--Renyi random graphs $G(n,p)$ satisfies a central limit theorem.
rate research
Read More
We consider bootstrap percolation and diffusion in sparse random graphs with fixed degrees, constructed by configuration model. Every node has two states: it is either active or inactive. We assume that to each node is assigned a nonnegative (integer) threshold. The diffusion process is initiated by a subset of nodes with threshold zero which consists of initially activated nodes, whereas every other node is inactive. Subsequently, in each round, if an inactive node with threshold $theta$ has at least $theta$ of its neighbours activated, then it also becomes active and remains so forever. This is repeated until no more nodes become activated. The main result of this paper provides a central limit theorem for the final size of activated nodes. Namely, under suitable assumptions on the degree and threshold distributions, we show that the final size of activated nodes has asymptotically Gaussian fluctuations.
It is an intriguing question to see what kind of information on the structure of an oriented graph $D$ one can obtain if $D$ does not contain a fixed oriented graph $H$ as a subgraph. The related question in the unoriented case has been an active area of research, and is relatively well-understood in the theory of quasi-random graphs and extremal combinatorics. In this paper, we consider the simplest cases of such a general question for oriented graphs, and provide some results on the global behavior of the orientation of $D$. For the case that $H$ is an oriented four-cycle we prove: in every $H$-free oriented graph $D$, there is a pair $A,Bssq V(D)$ such that $e(A,B)ge e(D)^{2}/32|D|^{2}$ and $e(B,A)le e(A,B)/2$. We give a random construction which shows that this bound on $e(A,B)$ is best possible (up to the constant). In addition, we prove a similar result for the case $H$ is an oriented six-cycle, and a more precise result in the case $D$ is dense and $H$ is arbitrary. We also consider the related extremal question in which no condition is put on the oriented graph $D$, and provide an answer that is best possible up to a multiplicative constant. Finally, we raise a number of related questions and conjectures.
Focusing on coupling between edges, we generalize the relationship between the normalized graph Laplacian and random walks on graphs by devising an appropriate normalization for the Hodge Laplacian -- the generalization of the graph Laplacian for simplicial complexes -- and relate this to a random walk on edges. Importantly, these random walks are intimately connected to the topology of the simplicial complex, just as random walks on graphs are related to the topology of the graph. This serves as a foundational step towards incorporating Laplacian-based analytics for higher-order interactions. We demonstrate how to use these dynamics for data analytics that extract information about the edge-space of a simplicial complex that complements and extends graph-based analysis. Specifically, we use our normalized Hodge Laplacian to derive spectral embeddings for examining trajectory data of ocean drifters near Madagascar and also develop a generalization of personalized PageRank for the edge-space of simplicial complexes to analyze a book co-purchasing dataset.
A classical result by Rado characterises the so-called partition-regular matrices $A$, i.e. those matrices $A$ for which any finite colouring of the positive integers yields a monochromatic solution to the equation $Ax=0$. We study the {sl asymmetric} random Rado problem for the (binomial) random set $[n]_p$ in which one seeks to determine the threshold for the property that any $r$-colouring, $r geq 2$, of the random set has a colour $i in [r]$ admitting a solution for the matrical equation $A_i x = 0$, where $A_1,ldots,A_r$ are predetermined partition-regular matrices pre-assigned to the colours involved. We prove a $1$-statement for the asymmetric random Rado property. In the symmetric setting our result retrieves the $1$-statement of the {sl symmetric} random Rado theorem established in a combination of results by Rodl and Rucinski~cite{RR97} and by Friedgut, Rodl and Schacht~cite{FRS10}. We conjecture that our $1$-statement in fact unveils the threshold for the asymmetric random Rado property, yielding a counterpart to the so-called {em Kohayakawa-Kreuter conjecture} concerning the threshold for the asymmetric random Ramsey problem in graphs. We deduce the aforementioned $1$-statement for the asymmetric random Rado property after establishing a broader result generalising the main theorem of Friedgut, Rodl and Schacht from~cite{FRS10}. The latter then serves as a combinatorial framework through which $1$-statements for Ramsey-type problems in random sets and (hyper)graphs alike can be established in the asymmetric setting following a relatively short combinatorial examination of certain hypergraphs. To establish this framework we utilise a recent approach put forth by Mousset, Nenadov and Samotij~cite{MNS18} for the Kohayakawa-Kreuter conjecture.
The bandwidth theorem [Mathematische Annalen, 343(1):175--205, 2009] states that any $n$-vertex graph $G$ with minimum degree $(frac{k-1}{k}+o(1))n$ contains all $n$-vertex $k$-colourable graphs $H$ with bounded maximum degree and bandwidth $o(n)$. In [arXiv:1612.00661] a random graph analogue of this statement is proved: for $pgg (frac{log n}{n})^{1/Delta}$ a.a.s. each spanning subgraph $G$ of $G(n,p)$ with minimum degree $(frac{k-1}{k}+o(1))pn$ contains all $n$-vertex $k$-colourable graphs $H$ with maximum degree $Delta$, bandwidth $o(n)$, and at least $C p^{-2}$ vertices not contained in any triangle. This restriction on vertices in triangles is necessary, but limiting. In this paper we consider how it can be avoided. A special case of our main result is that, under the same conditions, if additionally all vertex neighbourhoods in $G$ contain many copies of $K_Delta$ then we can drop the restriction on $H$ that $Cp^{-2}$ vertices should not be in triangles.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
