Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAdjacency Graphs of Polyhedral Surfaces
126
0
0.0
(
0
)
Added by
Alexander Wolff
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in $mathbb{R}^3$. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains $K_5$, $K_{5,81}$, or any nonplanar $3$-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, $K_{4,4}$, and $K_{3,5}$ can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (1983), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable $n$-vertex graphs is in $Omega(n log n)$. From the non-realizability of $K_{5,81}$, we obtain that any realizable $n$-vertex graph has $O(n^{9/5})$ edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.
rate research
Read More
Reeb graphs are structural descriptors that capture shape properties of a topological space from the perspective of a chosen function. In this work we define a combinatorial metric for Reeb graphs of orientable surfaces in terms of the cost necessary to transform one graph into another by edit operations. The main contributions of this paper are the stability property and the optimality of this edit distance. More precisely, the stability result states that changes in the functions, measured by the maximum norm, imply not greater changes in the corresponding Reeb graphs, measured by the edit distance. The optimality result states that our edit distance discriminates Reeb graphs better than any other metric for Reeb graphs of surfaces satisfying the stability property.
In 1960, Hoffman and Singleton cite{HS60} solved a celebrated equation for square matrices of order $n$, which can be written as $$ (kappa - 1) I_n + J_n - A A^{rm T} = A$$ where $I_n$, $J_n$, and $A$ are the identity matrix, the all one matrix, and a $(0,1)$--matrix with all row and column sums equal to $kappa$, respectively. If $A$ is an incidence matrix of some configuration $cal C$ of type $n_kappa$, then the left-hand side $Theta(A):= (kappa - 1)I_n + J_n - A A^{rm T}$ is an adjacency matrix of the non--collinearity graph $Gamma$ of $cal C$. In certain situations, $Theta(A)$ is also an incidence matrix of some $n_kappa$ configuration, namely the neighbourhood geometry of $Gamma$ introduced by Lef`evre-Percsy, Percsy, and Leemans cite{LPPL}. The matrix operator $Theta$ can be reiterated and we pose the problem of solving the generalised Hoffman--Singleton equation $Theta^m(A)=A$. In particular, we classify all $(0,1)$--matrices $M$ with all row and column sums equal to $kappa$, for $kappa = 3,4$, which are solutions of this equation. As a by--product, we obtain characterisations for incidence matrices of the configuration $10_3F$ in Kantors list cite{Kantor} and the $17_4$ configuration $#1971$ in Betten and Bettens list cite{BB99}.
We prove that any finite polyhedral manifold in 3D can be continuously flattened into 2D while preserving intrinsic distances and avoiding crossings, answering a 19-year-old open problem, if we extend standard folding models to allow for countably infinite creases. The most general cases previously known to be continuously flattenable were convex polyhedra and semi-orthogonal polyhedra. For non-orientable manifolds, even the existence of an instantaneous flattening (flat folded state) is a new result. Our solution extends a method for flattening semi-orthogonal polyhedra: slice the polyhedron along parallel planes and flatten the polyhedral strips between consecutive planes. We adapt this approach to arbitrary nonconvex polyhedra by generalizing strip flattening to nonorthogonal corners and slicing along a countably infinite number of parallel planes, with slices densely approaching every vertex of the manifold. We also show that the area of the polyhedron that needs to support moving creases (which are necessary for closed polyhedra by the Bellows Theorem) can be made arbitrarily small.
It is well known that spectral Tur{a}n type problem is one of the most classical {problems} in graph theory. In this paper, we consider the spectral Tur{a}n type problem. Let $G$ be a graph and let $mathcal{G}$ be a set of graphs, we say $G$ is textit{$mathcal{G}$-free} if $G$ does not contain any element of $mathcal{G}$ as a subgraph. Denote by $lambda_1$ and $lambda_2$ the largest and the second largest eigenvalues of the adjacency matrix $A(G)$ of $G,$ respectively. In this paper we focus on the characterization of graphs without short odd cycles according to the adjacency eigenvalues of the graphs. Firstly, an upper bound on $lambda_1^{2k}+lambda_2^{2k}$ of $n$-vertex ${C_3,C_5,ldots,C_{2k+1}}$-free graphs is established, where $k$ is a positive integer. All the corresponding extremal graphs are identified. Secondly, a sufficient condition for non-bipartite graphs containing an odd cycle of length at most $2k+1$ in terms of its spectral radius is given. At last, we characterize the unique graph having the maximum spectral radius among the set of $n$-vertex non-bipartite graphs with odd girth at least $2k+3,$ which solves an open problem proposed by Lin, Ning and Wu [Eigenvalues and triangles in graphs, Combin. Probab. Comput. 30 (2) (2021) 258-270].
Ever since the first observation of Bose-Einstein condensation in the nineties, ultracold quantum gases have been the subject of intense research, providing a unique tool to understand the behavior of matter governed by the laws of quantum mechanics. Ultracold bosonic atoms loaded in an optical lattice are usually described by the Bose-Hubbard model or a variant of it. In addition to the common insulating and superfluid phases, other phases (like density waves and supersolids) may show up in the presence of a short-range interparticle repulsion and also depending on the geometry of the lattice. We herein explore this possibility, using the graph of a convex polyhedron as lattice and playing with the coordination of nodes to promote the wanted finite-size ordering. To accomplish the job we employ the method of decoupling approximation, whose efficacy is tested in one case against exact diagonalization. We report zero-temperature results for two Catalan solids, the tetrakis hexahedron and the pentakis dodecahedron, for which a thorough ground-state analysis reveals the existence of insulating phases with polyhedral order and a widely extended supersolid region. The key to this outcome is the unbalance in coordination between inequivalent nodes of the graph. The predicted phases can be probed in systems of ultracold atoms using programmable holographic optical tweezers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
