Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSubgraphs of weakly quasi-random oriented graphs
174
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We show that a number of conditions on oriented graphs, all of which are satisfied with high probability by randomly oriented graphs, are equivalent. These equivalences are similar to those given by Chung, Graham and Wilson in the case of unoriented graphs, and by Chung and Graham in the case of tournaments. Indeed, our main theorem extends to the case of a general underlying graph G the main result of Chung and Graham which corresponds to the case that G is complete. One interesting aspect of these results is that exactly two of the four orientations of a four-cycle can be used for a quasi-randomness condition, i.e., if the number of appearances they make in D is close to the expected number in a random orientation of the same underlying graph, then the same is true for every small oriented graph H
We study Hamiltonicity in random subgraphs of the hypercube $mathcal{Q}^n$. Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of $mathcal{Q}^n$ according to a uniformly chosen random ordering. Then, with high probability, as soon as the graph produced by this process has minimum degree $2k$, it contains $k$ edge-disjoint Hamilton cycles, for any fixed $kinmathbb{N}$. Secondly, we obtain a perturbation result: if $Hsubseteqmathcal{Q}^n$ satisfies $delta(H)geqalpha n$ with $alpha>0$ fixed and we consider a random binomial subgraph $mathcal{Q}^n_p$ of $mathcal{Q}^n$ with $pin(0,1]$ fixed, then with high probability $Hcupmathcal{Q}^n_p$ contains $k$ edge-disjoint Hamilton cycles, for any fixed $kinmathbb{N}$. In particular, both results resolve a long standing conjecture, posed e.g. by Bollobas, that the threshold probability for Hamiltonicity in the random binomial subgraph of the hypercube equals $1/2$. Our techniques also show that, with high probability, for all fixed $pin(0,1]$ the graph $mathcal{Q}^n_p$ contains an almost spanning cycle. Our methods involve branching processes, the Rodl nibble, and absorption.
Kuhn, Osthus and Taraz showed that for each gamma>0 there exists C such that any n-vertex graph with minimum degree gamma n contains a planar subgraph with at least 2n-C edges. We find the optimum value of C for all gamma<1/2 and sufficiently large n.
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.
A theory of orientation on gain graphs (voltage graphs) is developed to generalize the notion of orientation on graphs and signed graphs. Using this orientation scheme, the line graph of a gain graph is studied. For a particular family of gain graphs with complex units, matrix properties are established. As with graphs and signed graphs, there is a relationship between the incidence matrix of a complex unit gain graph and the adjacency matrix of the line graph.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
