Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHorizontal visibility graph of a random restricted growth sequence
166
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study the distributional properties of horizontal visibility graphs associated with random restrictive growth sequences and random set partitions of size $n.$ Our main results are formulas expressing the expected degree of graph nodes in terms of simple explicit functions of a finite collection of Stirling and Bernoulli numbers.
rate research
Read More
We call $i$ a fixed point of a given sequence if the value of that sequence at the $i$-th position coincides with $i$. Here, we enumerate fixed points in the class of restricted growth sequences. The counting process is conducted by calculation of generating functions and leveraging a probabilistic sampling method.
The behavior of a certain random growth process is analyzed on arbitrary regular and non-regular graphs. Our argument is based on the Expander Mixing Lemma, which entails that the results are strongest for Ramanujan graphs, which asymptotically maximize the spectral gap. Further, we consider ErdH{o}s--Renyi random graphs and compare our theoretical results with computational experiments on flip graphs of point configurations. The latter is relevant for enumerating triangulations.
We consider the generalized game Lights Out played on a graph and investigate the following question: for a given positive integer $n$, what is the probability that a graph chosen uniformly at random from the set of graphs with $n$ vertices yields a universally solvable game of Lights Out? When $n leq 11$, we compute this probability exactly by determining if the game is universally solvable for each graph with $n$ vertices. We approximate this probability for each positive integer $n$ with $n leq 87$ by applying a Monte Carlo method using 1,000,000 trials. We also perform the analogous computations for connected graphs.
The random reversal graph offers new perspectives, allowing to study the connectivity of genomes as well as their most likely distance as a function of the reversal rate. Our main result shows that the structure of the random reversal graph changes dramatically at $lambda_n=1/binom{n+1}{2}$. For $lambda_n=(1-epsilon)/binom{n+1}{2}$, the random graph consists of components of size at most $O(nln(n))$ a.s. and for $(1+epsilon)/binom{n+1}{2}$, there emerges a unique largest component of size $sim wp(epsilon) cdot 2^ncdot n$!$ a.s.. This giant component is furthermore dense in the reversal graph.
We prove an asymptotic formula for the number of orientations with given out-degree (score) sequence for a graph $G$. The graph $G$ is assumed to have average degrees at least $n^{1/3 + varepsilon}$ for some $varepsilon > 0$, and to have strong mixing properties, while the maximum imbalance (out-degree minus in-degree) of the orientation should be not too large. Our enumeration results have applications to the study of subdigraph occurrences in random orientations with given imbalance sequence. As one step of our calculation, we obtain new bounds for the maximum likelihood estimators for the Bradley-Terry model of paired comparisons.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
