Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEmbedding products of graphs into Euclidean spaces
303
0
0.0
(
0
)
Authors
Mikhail Skopenkov
Ask ChatGPT about the research
No Arabic abstract
For any collection of graphs we find the minimal dimension d such that the product of these graphs is embeddable into the d-dimensional Euclidean space. In particular, we prove that the n-th powers of the Kuratowsky graphs are not embeddable into the 2n-dimensional Euclidean space. This is a solution of a problem of Menger from 1929. The idea of the proof is the reduction to a problem from so-called Ramsey link theory: we show that any embedding of L into the (2n-1)-dimensional sphere, where L is the join of n copies of a 4-point set, has a pair of linked (n-1)-dimensional spheres.
rate research
Read More
We will construct differential forms on the embedding spaces Emb(R^j,R^n) for n-j>=2 using configuration space integral associated with 1-loop graphs, and show that some linear combinations of these forms are closed in some dimensions. There are other dimensions in which we can show the closedness if we replace Emb(R^j,R^n) by fEmb(R^j,R^n), the homotopy fiber of the inclusion Emb(R^j,R^n) -> Imm(R^j,R^n). We also show that the closed forms obtained give rise to nontrivial cohomology classes, evaluating them on some cycles of Emb(R^j,R^n) and fEmb(R^j,R^n). In particular we obtain nontrivial cohomology classes (for example, in H^3(Emb(R^2,R^5))) of higher degrees than those of the first nonvanishing homotopy groups.
We show that a relatively hyperbolic group quasi-isometrically embeds in a product of finitely many trees if the peripheral subgroups do, and we provide an estimate on the minimal number of trees needed. Applying our result to the case of 3-manifolds, we show that fundamental groups of closed 3-manifolds have linearly controlled asymptotic dimension at most 8. To complement this result, we observe that fundamental groups of Haken 3-manifolds with non-empty boundary have asymptotic dimension 2.
An embedding of a metric graph $(G, d)$ on a closed hyperbolic surface is emph{essential}, if each complementary region has a negative Euler characteristic. We show, by construction, that given any metric graph, its metric can be rescaled so that it admits an essential and isometric embedding on a closed hyperbolic surface. The essential genus $g_e(G)$ of $(G, d)$ is the lowest genus of a surface on which such an embedding is possible. In the next result, we establish a formula to compute $g_e(G)$. Furthermore, we show that for every integer $ggeq g_e(G)$, $(G, d)$ admits such an embedding (possibly after a rescaling of $d$) on a surface of genus $g$. Next, we study minimal embeddings where each complementary region has Euler characteristic $-1$. The maximum essential genus $g_e^{max}(G)$ of $(G, d)$ is the largest genus of a surface on which the graph is minimally embedded. Finally, we describe a method explicitly for an essential embedding of $(G, d)$, where $g_e(G)$ and $g_e^{max}(G)$ are realized.
For controller design for systems on manifolds embedded in Euclidean space, it is convenient to utilize a theory that requires a single global coordinate system on the ambient Euclidean space rather than multiple local charts on the manifold or coordinate-free tools from differential geometry. In this article, we apply such a theory to design model predictive tracking controllers for systems whose dynamics evolve on manifolds and illustrate its efficacy with the fully actuated rigid body attitude control system.
The $k$-leaf power graph $G$ of a tree $T$ is a graph whose vertices are the leaves of $T$ and whose edges connect pairs of leaves at unweighted distance at most~$k$ in $T$. Recognition of the $k$-leaf power graphs for $k geq 7$ is still an open problem. In this paper, we provide two algorithms for this problem for sparse leaf power graphs. Our results shows that the problem of recognizing these graphs is fixed-parameter tractable when parameterized both by $k$ and by the degeneracy of the given graph. To prove this, we first describe how to embed the leaf root of a leaf power graph into a product of the graph with a cycle graph. We bound the treewidth of the resulting product in terms of $k$ and the degeneracy of $G$. The first presented algorithm uses methods based on monadic second-order logic (MSO$_2$) to recognize the existence of a leaf power as a subgraph of the product graph. Using the same embedding in the product graph, the second algorithm presents a dynamic programming approach to solve the problem and provide a better dependence on the parameters.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
