Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMaking spanning graphs
122
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We prove that for each $Dge 2$ there exists $c>0$ such that whenever $ble cbig(tfrac{n}{log n}big)^{1/D}$, in the $(1:b)$ Maker-Breaker game played on $E(K_n)$, Maker has a strategy to guarantee claiming a graph $G$ containing copies of all graphs $H$ with $v(H)le n$ and $Delta(H)le D$. We show further that the graph $G$ guaranteed by this strategy also contains copies of any graph $H$ with bounded maximum degree and degeneracy at most $tfrac{D-1}{2}$. This lower bound on the threshold bias is sharp up to the $log$-factor when $H$ consists of $tfrac{n}{3}$ vertex-disjoint triangles or $tfrac{n}{4}$ vertex-disjoint $K_4$-copies.
rate research
Read More
We show that, in almost every $n$-vertex random directed graph process, a copy of every possible $n$-vertex oriented cycle will appear strictly before a directed Hamilton cycle does, except of course for the directed cycle itself. Furthermore, given an arbitrary $n$-vertex oriented cycle, we determine the sharp threshold for its appearance in the binomial random directed graph. These results confirm, in a strong form, a conjecture of Ferber and Long.
In 2001, Komlos, Sarkozy and Szemeredi proved that, for each $alpha>0$, there is some $c>0$ and $n_0$ such that, if $ngeq n_0$, then every $n$-vertex graph with minimum degree at least $(1/2+alpha)n$ contains a copy of every $n$-vertex tree with maximum degree at most $cn/log n$. We prove the corresponding result for directed graphs. That is, for each $alpha>0$, there is some $c>0$ and $n_0$ such that, if $ngeq n_0$, then every $n$-vertex directed graph with minimum semi-degree at least $(1/2+alpha)n$ contains a copy of every $n$-vertex oriented tree whose underlying maximum degree is at most $cn/log n$. As with Komlos, Sarkozy and Szemeredis theorem, this is tight up to the value of $c$. Our result improves a recent result of Mycroft and Naia, which requires the oriented trees to have underlying maximum degree at most $Delta$, for any constant $Delta$ and sufficiently large $n$. In contrast to the previous work on spanning trees in dense directed or undirected graphs, our methods do not use Szemeredis regularity lemma.
We extend a recent argument of Kahn, Narayanan and Park (Proceedings of the AMS, to appear) about the threshold for the appearance of the square of a Hamilton cycle to other spanning structures. In particular, for any spanning graph, we give a sufficient condition under which we may determine its threshold. As an application, we find the threshold for a set of cyclically ordered copies of $C_4$ that span the entire vertex set, so that any two consecutive copies overlap in exactly one edge and all overlapping edges are disjoint. This answers a question of Frieze. We also determine the threshold for edge-overlapping spanning $K_r$-cycles.
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.
Networks with a high degree of symmetry are useful models for parallel processor networks. In earlier papers, we defined several global communication tasks (universal exchange, universal broadcast, universal summation) that can be critical tasks when complex algorithms are mapped to parallel machines. We showed that utilizing the symmetry can make network optimization a tractable problem. In particular, we showed that Cayley graphs have the desirable property that certain routing schemes starting from a single node can be transferred to all nodes in a way that does not introduce conflicts. In this paper, we define the concept of spanning factorizations and show that this property can also be used to transfer routing schemes from a single node to all other nodes. We show that all Cayley graphs and many (perhaps all) vertex transitive graphs have spanning factorizations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
