Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIncreasing paths in edge-ordered graphs: the hypercube and random graphs
322
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
An edge-ordering of a graph $G=(V,E)$ is a bijection $phi:Eto{1,2,...,|E|}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,...,e_k$ is an increasing path if it is a path in $G$ which satisfies $phi(e_i)<phi(e_j)$ for all $i<j$. For a graph $G$, let $f(G)$ be the largest integer $ell$ such that every edge-ordering of $G$ contains an increasing path of length $ell$. The parameter $f(G)$ was first studied for $G=K_n$ and has subsequently been studied for other families of graphs. This paper gives bounds on $f$ for the hypercube and the random graph $G(n,p)$.
rate research
Read More
An edge-ordered graph is a graph with a total ordering of its edges. A path $P=v_1v_2ldots v_k$ in an edge-ordered graph is called increasing if $(v_iv_{i+1}) > (v_{i+1}v_{i+2})$ for all $i = 1,ldots,k-2$; it is called decreasing if $(v_iv_{i+1}) < (v_{i+1}v_{i+2})$ for all $i = 1,ldots,k-2$. We say that $P$ is monotone if it is increasing or decreasing. A rooted tree $T$ in an edge-ordered graph is called monotone if either every path from the root of to a leaf is increasing or every path from the root to a leaf is decreasing. Let $G$ be a graph. In a straight-line drawing $D$ of $G$, its vertices are drawn as different points in the plane and its edges are straight line segments. Let $overline{alpha}(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing path of length $overline{alpha}(G)$. Let $overline{tau}(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing complete binary tree of size $overline{tau}(G)$. In this paper we show that $overline alpha(K_n) = Omega(loglog n)$, $overline alpha(K_n) = O(log n)$, $overline tau(K_n) = Omega(loglog log n)$ and $overline tau(K_n) = O(sqrt{n log n})$.
We show that for $dge d_0(epsilon)$, with high probability, the random graph $G(n,d/n)$ contains an induced path of length $(3/2-epsilon)frac{n}{d}log d$. This improves a result obtained independently by Luczak and Suen in the early 90s, and answers a question of Fernandez de la Vega. Along the way, we generalize a recent result of Cooley, Draganic, Kang and Sudakov who studied the analogous problem for induced matchings.
We investigate the number of 4-edge paths in graphs with a fixed number of vertices and edges. An asymptotically sharp upper bound is given to this quantity. The extremal construction is the quasi-star or the quasi-clique graph, depending on the edge density. An easy lower bound is also proved. This answer resembles the classic theorem of Ahlswede and Katona about the maximal number of 2-edge paths, and a recent theorem of Kenyon, Radin, Ren and Sadun about k-edge stars.
We study some percolation problems on the complete graph over $mathbf N$. In particular, we give sharp sufficient conditions for the existence of (finite or infinite) cliques and paths in a random subgraph. No specific assumption on the probability, such as independency, is made. The main tools are a topological version of Ramsey theory, exchangeability theory and elementary ergodic theory.
In 2006, Barat and Thomassen posed the following conjecture: for each tree $T$, there exists a natural number $k_T$ such that, if $G$ is a $k_T$-edge-connected graph and $|E(G)|$ is divisible by $|E(T)|$, then $G$ admits a decomposition into copies of $T$. This conjecture was verified for stars, some bistars, paths of length $3$, $5$, and $2^r$ for every positive integer $r$. We prove that this conjecture holds for paths of any fixed length.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
