-
Separating the edges of a graph by cycles and by subdivisions of $K_4$
Authors:
Fábio Botler,
Tássio Naia
Abstract:
A separating system of a graph $G$ is a family $\mathcal{S}$ of subgraphs of $G$ for which the following holds: for all distinct edges $e$ and $f$ of $G$, there exists an element in $\mathcal{S}$ that contains $e$ but not $f$. Recently, it has been shown that every graph of order $n$ admits a separating system consisting of $19n$ paths [Bonamy, Botler, Dross, Naia, Skokan, Separating the Edges of…
▽ More
A separating system of a graph $G$ is a family $\mathcal{S}$ of subgraphs of $G$ for which the following holds: for all distinct edges $e$ and $f$ of $G$, there exists an element in $\mathcal{S}$ that contains $e$ but not $f$. Recently, it has been shown that every graph of order $n$ admits a separating system consisting of $19n$ paths [Bonamy, Botler, Dross, Naia, Skokan, Separating the Edges of a Graph by a Linear Number of Paths, Adv. Comb., October 2023], improving the previous almost linear bound of $\mathrm{O}(n\log^\star n)$ [S. Letzter, Separating paths systems of almost linear size, Trans. Amer. Math. Soc., to appear], and settling conjectures posed by Balogh, Csaba, Martin, and Pluhár and by Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan.
We investigate a natural generalization of these results to subdivisions of cliques, showing that every graph admits both a separating system consisting of $41n$ edges and cycles, and a separating system consisting of $82 n$ edges and subdivisions of $K_4$.
△ Less
Submitted 2 July, 2024;
originally announced July 2024.
-
Separating the edges of a graph by a linear number of paths
Authors:
Marthe Bonamy,
Fábio Botler,
François Dross,
Tássio Naia,
Jozef Skokan
Abstract:
Recently, Letzter proved that any graph of order $n$ contains a collection $\mathcal{P}$ of $O(n\log^\star n)$ paths with the following property: for all distinct edges $e$ and $f$ there exists a path in $\mathcal{P}$ which contains $e$ but not $f$. We improve this upper bound to $19 n$, thus answering a question of G.O.H. Katona and confirming a conjecture independently posed by Balogh, Csaba, Ma…
▽ More
Recently, Letzter proved that any graph of order $n$ contains a collection $\mathcal{P}$ of $O(n\log^\star n)$ paths with the following property: for all distinct edges $e$ and $f$ there exists a path in $\mathcal{P}$ which contains $e$ but not $f$. We improve this upper bound to $19 n$, thus answering a question of G.O.H. Katona and confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhár and by Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan. Our proof is elementary and self-contained.
△ Less
Submitted 10 October, 2023; v1 submitted 20 January, 2023;
originally announced January 2023.
-
Directed graphs with lower orientation Ramsey thresholds
Authors:
Gabriel Ferreira Barros,
Bruno Pasqualotto Cavalar,
Yoshiharu Kohayakawa,
Guilherme Oliveira Mota,
Tássio Naia
Abstract:
We investigate the threshold $p_{\vec H}=p_{\vec H}(n)$ for the Ramsey-type property $G(n,p)\to \vec H$, where $G(n,p)$ is the binomial random graph and $G\to\vec H$ indicates that every orientation of the graph $G$ contains the oriented graph $\vec H$ as a subdigraph. Similarly to the classical Ramsey setting, the upper bound $p_{\vec H}\leq Cn^{-1/m_2(\vec H)}$ is known to hold for some constant…
▽ More
We investigate the threshold $p_{\vec H}=p_{\vec H}(n)$ for the Ramsey-type property $G(n,p)\to \vec H$, where $G(n,p)$ is the binomial random graph and $G\to\vec H$ indicates that every orientation of the graph $G$ contains the oriented graph $\vec H$ as a subdigraph. Similarly to the classical Ramsey setting, the upper bound $p_{\vec H}\leq Cn^{-1/m_2(\vec H)}$ is known to hold for some constant $C=C(\vec H)$, where $m_2(\vec H)$ denotes the maximum $2$-density of the underlying graph $H$ of $\vec H$. While this upper bound is indeed the threshold for some $\vec H$, this is not always the case. We obtain examples arising from rooted products of orientations of sparse graphs (such as forests, cycles and, more generally, subcubic $\{K_3,K_{3,3}\}$-free graphs) and arbitrarily rooted transitive triangles.
△ Less
Submitted 17 June, 2024; v1 submitted 13 November, 2022;
originally announced November 2022.
-
Seymour's Second Neighborhood Conjecture for orientations of (pseudo)random graphs
Authors:
Fábio Botler,
Phablo F. S. Moura,
Tássio Naia
Abstract:
Seymour's Second Neighborhood Conjecture (SNC) states that every oriented graph contains a vertex whose second neighborhood is as large as its first neighborhood. We investigate the SNC for orientations of both binomial and pseudo random graphs, verifying the SNC asymptotically almost surely (a.a.s.)
(i) for all orientations of $G(n,p)$ if $\limsup_{n\to\infty} p < 1/4$; and
(ii) for a uniform…
▽ More
Seymour's Second Neighborhood Conjecture (SNC) states that every oriented graph contains a vertex whose second neighborhood is as large as its first neighborhood. We investigate the SNC for orientations of both binomial and pseudo random graphs, verifying the SNC asymptotically almost surely (a.a.s.)
(i) for all orientations of $G(n,p)$ if $\limsup_{n\to\infty} p < 1/4$; and
(ii) for a uniformly-random orientation of each weakly $(p,A\sqrt{np})$-bijumbled graph of order $n$ and density $p$, where $p=Ω(n^{-1/2})$ and $1-p = Ω(n^{-1/6})$ and $A>0$ is a universal constant independent of both $n$ and $p$.
We also show that a.a.s. the SNC holds for almost every orientation of $G(n,p)$. More specifically, we prove that a.a.s.
(iii) for all $\varepsilon > 0$ and $p=p(n)$ with $\limsup_{n\to\infty} p \le 2/3-\varepsilon$, every orientation of $G(n,p)$ with minimum outdegree $Ω_\varepsilon(\sqrt{n})$ satisfies the SNC; and
(iv) for all $p=p(n)$, a random orientation of $G(n,p)$ satisfies the SNC.
△ Less
Submitted 11 November, 2022;
originally announced November 2022.
-
Trees and tree-like structures in dense digraphs
Authors:
Richard Mycroft,
Tássio Naia
Abstract:
We prove that every oriented tree on $n$ vertices with bounded maximum degree appears as a spanning subdigraph of every directed graph on $n$ vertices with minimum semidegree at least $n/2+\mathrm{o}(n)$. This can be seen as a directed graph analogue of a well-known theorem of Komlós, Sárközy and Szemerédi. Our result for trees follows from a more general result, allowing the embedding of arbitrar…
▽ More
We prove that every oriented tree on $n$ vertices with bounded maximum degree appears as a spanning subdigraph of every directed graph on $n$ vertices with minimum semidegree at least $n/2+\mathrm{o}(n)$. This can be seen as a directed graph analogue of a well-known theorem of Komlós, Sárközy and Szemerédi. Our result for trees follows from a more general result, allowing the embedding of arbitrary orientations of a much wider class of spanning "tree-like" structures, such as a collection of at most $\mathrm{o}(n^{1/4})$ vertex-disjoint cycles and subdivisions of graphs $H$ with $|H|< n^{(\log n)^{-1/2}}$ in which each edge is subdivided at least once.
△ Less
Submitted 16 December, 2020;
originally announced December 2020.
-
Orientation Ramsey thresholds for cycles and cliques
Authors:
Gabriel Ferreira Barros,
Bruno Pasqualotto Cavalar,
Yoshiharu Kohayakawa,
Tássio Naia
Abstract:
If $G$ is a graph and $\vec H$ is an oriented graph, we write $G\to \vec H$ to say that every orientation of the edges of $G$ contains $\vec H$ as a subdigraph. We consider the case in which $G=G(n,p)$, the binomial random graph. We determine the threshold $p_{\vec H}=p_{\vec H}(n)$ for the property $G(n,p)\to \vec H$ for the cases in which $\vec H$ is an acyclic orientation of a complete graph or…
▽ More
If $G$ is a graph and $\vec H$ is an oriented graph, we write $G\to \vec H$ to say that every orientation of the edges of $G$ contains $\vec H$ as a subdigraph. We consider the case in which $G=G(n,p)$, the binomial random graph. We determine the threshold $p_{\vec H}=p_{\vec H}(n)$ for the property $G(n,p)\to \vec H$ for the cases in which $\vec H$ is an acyclic orientation of a complete graph or of a cycle.
△ Less
Submitted 15 December, 2020;
originally announced December 2020.
-
Unavoidable trees in tournaments
Authors:
Richard Mycroft,
Tássio Naia
Abstract:
An oriented tree $T$ on $n$ vertices is unavoidable if every tournament on $n$ vertices contains a copy of $T$. In this paper we give a sufficient condition for $T$ to be unavoidable, and use this to prove that almost all labelled oriented trees are unavoidable, verifying a conjecture of Bender and Wormald. We additionally prove that every tournament on $n + o(n)$ vertices contains a copy of every…
▽ More
An oriented tree $T$ on $n$ vertices is unavoidable if every tournament on $n$ vertices contains a copy of $T$. In this paper we give a sufficient condition for $T$ to be unavoidable, and use this to prove that almost all labelled oriented trees are unavoidable, verifying a conjecture of Bender and Wormald. We additionally prove that every tournament on $n + o(n)$ vertices contains a copy of every oriented tree $T$ on $n$ vertices with polylogarithmic maximum degree, improving a result of Kühn, Mycroft and Osthus.
△ Less
Submitted 12 September, 2016;
originally announced September 2016.
