Shunsuke Maeda, Yusuke Kaneko, Hideaki Muramatsu
et al.
Phylogenetic networks are used to represent the evolutionary history of species. They are versatile when compared to traditional phylogenetic trees, as they capture more complex evolutionary events such as hybridization and horizontal gene transfer. Distance-based methods such as the Neighbor-Net algorithm are widely used to compute phylogenetic networks from data. However, the output is necessarily an undirected graph, posing a great challenge to deduce the direction of genetic flow in order to infer the true evolutionary history. Recently, Huber et al. investigated two different computational problems relevant to orienting undirected phylogenetic networks into directed ones. In this paper, we consider the problem of orienting an undirected binary network into a tree-child network. We give some necessary conditions for determining the tree-child orientability, such as a tight upper bound on the size of tree-child orientable graphs, as well as many interesting examples. In addition, we introduce new families of undirected phylogenetic networks, the jellyfish graphs and ladder graphs, that are orientable but not tree-child orientable. We also prove that any ladder graph can be made tree-child orientable by adding extra leaves, and describe a simple algorithm for orienting a ladder graph to a tree-child network with the minimum number of extra leaves. We pose many open problems as well.
Linyi Chen, Grant Crider-Phillips, Braeden Reinoso
et al.
We investigate when a Legendrian knot in standard contact $\mathbb{R}^3$ has a non-orientable exact Lagrangian filling. We prove analogs of several results in the orientable setting, develop new combinatorial obstructions to fillability, and determine when several families of knots have such fillings. In particular, we determine completely when an alternating knot (and more generally a plus-adequate knot) is decomposably non-orientably fillable, and classify the fillability of most torus and 3-strand pretzel knots. We also describe rigidity phenomena of decomposable non-orientable fillings, including finiteness of the possible normal Euler numbers of fillings, and the minimization of crosscap numbers of fillings, obtaining results which contrast in interesting ways with the smooth setting.
Given a connected and bridgeless graph $G$, let $\mathscr{D}(G)$ be the family of strong orientations of $G$. The orientation number of $G$ is defined to be $\bar{d}(G):=min\{d(D)|D\in \mathscr{D}(G)\}$, where $d(D)$ is the diameter of the digraph $D$. In this paper, we focus on the orientation number of complete tripartite graphs. We prove a conjecture raised by Rajasekaran and Sampathkumar. Specifically, for $q\ge p\ge 3$, if $\bar{d}(K(2,p,q))=2$, then $q\le{{p}\choose{\lfloor{p/2}\rfloor}}$. We also present some sufficient conditions on $p$ and $q$ for $\bar{d}(K(p,p,q))=2$.
Minoru Eto, Adam Peterson, Fidel I. Schaposnik Massolo
et al.
The dynamics of both global and local vortices with non-Abelian orientational moduli is investigated in detail. Head-on collisions of these vortices are numerically simulated for parallel, anti-parallel and orthogonal internal orientations where we find interesting dynamics of the orientational moduli. A detailed study of the inter-vortex force is provided and a phase diagram separating Abelian and non-Abelian vortex types is constructed. Some results on scatterings with non-zero impact parameter and multi-vortex collisions are included.
Bipolar orientations of planar maps have recently attracted some interest in combinatorics, probability theory and theoretical physics. Plane bipolar orientations with $n$ edges are known to be counted by the $n$th Baxter number $b(n)$, which can be defined by a linear recurrence relation with polynomial coefficients. Equivalently, the associated generating function $\sum_n b(n)t^n$ is D-finite. In this paper, we address a much refined enumeration problem, where we record for every $r$ the number of faces of degree $r$. When these degrees are bounded, we show that the associated generating function is given as the constant term of a multivariate rational series, and thus is still D-finite. We also provide detailed asymptotic estimates for the corresponding numbers. The methods used earlier to count all plane bipolar orientations, regardless of their face degrees, do not generalize easily to record face degrees. Instead, we start from a recent bijection, due to Kenyon et al., that sends bipolar orientations onto certain lattice walks confined to the first quadrant. Due to this bijection, the study of bipolar orientations meets the study of walks confined to a cone, which has been extremely active in the past 15 years. Some of our proofs rely on recent developments in this field, while others are purely bijective. Our asymptotic results also involve probabilistic arguments.
In the present paper we consider preserving orientation Morse-Smale diffeomorphisms on surfaces. Using the methods of factorization and linearizing neighborhoods we prove that such diffeomorphisms have a finite number of orientable heteroclinic orbits.
Given a digraph $D$ with $m $ arcs, a bijection $τ: A(D)\rightarrow \{1, 2, \ldots, m\}$ is an antimagic labeling of $D$ if no two vertices in $D$ have the same vertex-sum, where the vertex-sum of a vertex $u $ in $D$ under $τ$ is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. We say $(D, τ)$ is an antimagic orientation of a graph $G$ if $D$ is an orientation of $G$ and $τ$ is an antimagic labeling of $D$. Motivated by the conjecture of Hartsfield and Ringel from 1990 on antimagic labelings of graphs, Hefetz, Mütze, and Schwartz in 2010 initiated the study of antimagic orientations of graphs, and conjectured that every connected graph admits an antimagic orientation. This conjecture seems hard, and few related results are known. However, it has been verified to be true for regular graphs and biregular bipartite graphs. In this paper, we prove that every connected graph $G$ on $n\ge9$ vertices with maximum degree at least $n-5$ admits an antimagic orientation.
Mohammad Dehghani Soltani, Ardimas Andi Purwita, Iman Tavakkolnia
et al.
Most studies on optical wireless communications (OWCs) have neglected the effect of random orientation in their performance analysis due to the lack of a proper model for the random orientation. Our recent empirical-based research illustrates that the random orientation follows a Laplace distribution for a static user equipment (UE). In this paper, we analyze the device orientation and assess its importance on system performance. The reliability of an OWC channel highly depends on the availability and alignment of line-of-sight (LOS) links. In this study, the effect of receiver orientation including both polar and azimuth angles on the LOS channel gain are analyzed. The probability of establishing a LOS link is investigated and the probability density function (PDF) of signal-to-noise ratio (SNR) for a randomly-oriented device is derived. By means of the PDF of SNR, the bit-error ratio (BER) of DC-biased optical orthogonal frequency division multiplexing (DCO-OFDM) in additive white Gaussian noise (AWGN) channels is evaluated. A closed-form approximation for the BER of UE with random orientation is presented which shows a good match with Monte-Carlo simulation results. Furthermore, the impact of the UE's random motion on the BER performance has been assessed. Finally, the effect of random orientation on the average signal-to-interference-plus-noise ratio (SINR) in a multiple access points (APs) scenario is investigated.
An oriented hypergraph is an oriented incidence structure that generalizes and unifies graph and hypergraph theoretic results by examining its locally signed graphic substructure. In this paper we obtain a combinatorial characterization of the coefficients of the characteristic polynomials of oriented hypergraphic Laplacian and adjacency matrices via a signed hypergraphic generalization of basic figures of graphs. Additionally, we provide bounds on the determinant and permanent of the Laplacian matrix, characterize the oriented hypergraphs in which the upper bound is sharp, and demonstrate that the lower bound is never achieved.
The construction of integer linking numbers of closed curves in a three-dimensional manifold usually appeals to the orientation of this manifold. We discuss how to avoid it constructing similar homotopy invariants of links in non-orientable manifolds.
These notes fill in results about oriented percolation that are required for the paper [3] ("Forward clusters for degenerate random environments"). Since these are essentially modifications of results found in other sources (but adapted to the model we particularly need), there is no intention to publish these.
A Hopf hypersurface in a (para-)Kaehler manifold is a real hypersurface for which one of the principal directions of the second fundamental form is the (para-)complex dual of the normal vector. We consider particular Hopf hypersurfaces in the space of oriented geodesics of a non-flat space form of dimension greater than 2. For spherical and hyperbolic space forms, the oriented geodesic space admits a canonical Kaehler-Einstein and para-Kaehler-Einstein structure, respectively, so that a natural notion of a Hopf hypersurface exists. The particular hypersurfaces considered are formed by the oriented geodesics that are tangent to a given convex hypersurface in the underlying space form. We prove that a tangent hypersurface is Hopf in the space of oriented geodesics with respect to this canonical (para-)Kaehler structure iff the underlying convex hypersurface is totally umbilic and non-flat. In the case of 3 dimensional space forms, however, there exists a second canonical complex structure which can also be used to define Hopf hypersurfaces. We prove that in this dimension, the tangent hypersurface of a convex hypersurface in the space form is always Hopf with respect to this second complex structure.
We determine positive-dimensional G-periodic proper subvarieties of an n-dimensional normal projective variety X under the action of an abelian group G of maximal rank n-1 and of positive entropy. The motivation of the paper is to understand the obstruction for X to be G-equivariant birational to the quotient variety of an abelian variety modulo the action of a finite group.
The exchange graph of a 2-acyclic quiver is the graph of mutation-equivalent quivers whose edges correspond to mutations. When the quiver admits a nondegenerate Jacobi-finite potential, the exchange graph admits a natural acyclic orientation called the oriented exchange graph, as shown by Brüstle and Yang. The oriented exchange graph is isomorphic to the Hasse diagram of the poset of functorially finite torsion classes of a certain finite dimensional algebra. We prove that lattices of torsion classes are semidistributive lattices, and we use this result to conclude that oriented exchange graphs with finitely many elements are semidistributive lattices. Furthermore, if the quiver is mutation-equivalent to a type A Dynkin quiver or is an oriented cycle, then the oriented exchange graph is a lattice quotient of a lattice of biclosed subcategories of modules over the cluster-tilted algebra, generalizing Reading's Cambrian lattices in type A. We also apply our results to address a conjecture of Brüstle, Dupont, and Pérotin on the lengths of maximal green sequences.
We study a parabolic differential equation whose solution represents the atom dislocation in a crystal for a general type of Peierls-Nabarro model with possibly long range interactions and an external stress. Differently from the previous literature, we treat here the case in which such dislocation is not the superpositions of transitions all occurring with the same orientations (i.e. opposite orientations are allowed as well).
The discovery of a two-dimensional (2D) electron gas at the (110)-oriented LaAlO3/SrTiO3 in- terface provided us with the opportunity to probe the effect of crystallographic orientation and the ensuing electronic reconstructions on interface properties beyond the conventional (001)-orientation. At temperatures below 200 mK, we have measured 2D superconductivity with a spatial extension significantly larger (d approx. 24 - 30 nm) than previously reported for (001)-oriented LaAlO3/SrTiO3 interfaces (d approx. 10 nm). The more extended superconductivity brings about the absence of violation of the Pauli paramagnetic limit for the upper critical fields, signaling the distinctive nature of the electronic structure of the (110)-oriented interface with respect to their (001)-counterparts
We consider the problem of sampling from the uniform distribution on the set of Eulerian orientations of subgraphs of the triangular lattice. Although it is known that this can be achieved in polynomial time for any graph, the algorithm studied here is more natural in the context of planar Eulerian graphs. We analyse the mixing time of a Markov chain on the Eulerian orientations of a planar graph which moves between orientations by reversing the edges of directed faces. Using path coupling and the comparison method we obtain a polynomial upper bound on the mixing time of this chain for any solid subgraph of the triangular lattice. By considering the conductance of the chain we show that there exist subgraphs with holes for which the chain will always take an exponential amount of time to converge. Finally, as an additional justification for studying a Markov chain on the set of Eulerian orientations of planar graphs, we show that the problem of counting Eulerian orientations remains #P-complete when restricted to planar graphs. A preliminary version of this work appeared as an extended abstract in the 2nd Algorithms and Complexity in Durham workshop.