Search

Motivated by the notion of chip-firing on the dual graph of a planar graph, we consider `integral flow chip-firing' on an arbitrary graph $G$. The chip-firing rule is governed by ${\mathcal L}^*(G)$, the dual Laplacian of $G$ determined by choosing a basis for the lattice of integral flows on $G$. We show that any graph admits such a basis so that ${\mathcal L}^*(G)$ is an $M$-matrix, leading to a firing rule on these basis elements that is avalanche finite. This follows from a more general result on bases of integral lattices that may be of independent interest. Our results provide a notion of $z$-superstable flow configurations that are in bijection with the set of spanning trees of $G$. We show that for planar graphs, as well as for the graphs $K_5$ and $K_{3,3}$, one can find such a flow M-basis that consists of cycles of the underlying graph. We consider the question for arbitrary graphs and address some open questions., Comment: 18 pages, 4 figures; v2: typos fixed, other minor changes; v3: title change, author name corrected, some changes in terminology, other corrections and minor revisions incorporating comments from referees

A catacondensed benzenoid system (resp. benzenoid chain) is a benzenoid system whose inner dual graph is a tree (resp. a path). The Tutte polynomial of a graph is a two-variable polynomial whose evaluations at various points are equivalent to the exact solutions of many counting problems. In this paper, we introduce a graph vector at a given edge which related to the Tutte polynomial. Based on this concept and by three classes transfer matrices, we get the reduction formula for Tutte polynomial of any catacondensed benzenoid system. Moreover, the number of spanning trees for any catacondensed benzenoid system is also determined via a product of $$(2\times 2)$$ matrices with entries in N. As a by-product, we study the extremum problem of the number of spanning trees over the set of cataconsed hexagonal systems with one branched hexagon.

In this article, a new idea of interval-valued m-polar fuzzy (IVmPF) graph is introduced and investigated some of it’s properties. Here, IVmPF multiset, interval-valued m-polar fuzzy (IVmPF) multi graph are presented. IVmPF planar value of an interval-valued m-polar fuzzy (IVmPF) planar graph along with degree of planarity value is also introduced to measure the planarity value of an interval-valued m-polar fuzzy (IVmPF) graph. Some related terms like complete IVmPF graph, strong IVmPF graph, strong edges, faces of IVmPF planar graph are presented. In this paper, IVmPF dual graph is also described which is closely related to IVmPF planar graph. Some important properties are studied on IVmPF dual graph. Lastly, a real life application on IVmPF planar graph has been discussed to show its practicability.

A lucasene is a hexagon chain that is similar to a fibonaccene, an L -fence is a poset the Hasse diagram of which is isomorphic to the directed inner dual graph of the corresponding lucasene. A new class of cubes, which named after matchable Lucas cubes according to the number of its vertices (or elements), are a series of directed or undirected Hasse diagrams of filter lattices of L -fences. The basic properties and several classes of polynomials, e.g. rank generating functions, cube polynomials and degree sequence polynomials, of matchable Lucas cubes are obtained. Some special conclusions on binomial coefficients and Lucas triangle are given.

Let P be a cubic 3-connected bipartite plane graph having a 2-factor which consists only of facial 4-cycles, and suppose that $$P^{*}$$P∗ is the dual graph. We show that P has at least $$3^{\left\lceil \frac{2|P^{*}|}{\varDelta ^{2}{(P^{*})}}\right\rceil }$$32|P∗|Δ2(P∗) different Hamilton cycles.

We compare one-dimensional representations for the isotopy stable dynamics of homeomorphisms in two dimensions. We consider the skeleton graph representative, which captures periodic behaviour, and the homotopy graph representative which captures homo-/heteroclinic behaviour. The main result of this paper is to show that the dual to the skeleton graph representative is the homotopy graph representative of the inverse map. This gives a strong link between different methods for computing the dynamics.

Maximal minors of Kasteleyn sign matrices on planar bipartite graphs in the disk count dimer configurations with prescribed boundary conditions, and the weighted version of such matrices provides a natural parametrization of the totally non--negative part of real Grassmannians (see Refs. [54,43,44,58,7]). In this paper we provide a geometric interpretation of such variant of Kasteleyn theorem: a signature is Kasteleyn if and only if it is geometric in the sense of Ref. [5]. We apply this geometric characterization to explicitly solve the associated system of relations and provide a new proof that the parametrization of positroid cells induced by Kasteleyn weighted matrices coincides with that of Postnikov boundary measurement map. Finally we use Kasteleyn system of relations to associate algebraic geometric data to KP multi-soliton solutions. Indeed the KP wave function solves such system of relations at the nodes of the spectral curve if the dual graph of the latter represents the soliton data. Therefore the construction of the divisor is automatically invariant, and finally it coincides with that in Refs. [4,6] for the present class of graphs., Comment: 47 pages, many figures; V2 and V3: minor modifications

Let [Formula: see text] be a plane graph with a set of faces [Formula: see text] and [Formula: see text] be a (not necessarily proper) vertex [Formula: see text]-coloring. [Formula: see text] is called polychromatic if all [Formula: see text] colors appear on the vertices of its boundary for each face (also the outer-face) [Formula: see text]. The polychromatic number of [Formula: see text] is the largest number of colors [Formula: see text] such that [Formula: see text] admits a polychromatic [Formula: see text]-coloring. In the paper, we consider a class of plane graphs [Formula: see text] with minimum face size [Formula: see text], in each of which every pair of faces have at most [Formula: see text] common incident vertices, and show that the polychromatic number for each [Formula: see text] is at least [Formula: see text]. When [Formula: see text], the result improves a known lower bound.

Nonnegative Matrix Factorization (NMF) has received great attention in the era of big data, owing to its roles in efficiently reducing data dimension and producing feature-based data representation. In this paper, we first propose two new NMF optimization models, called an orthogonal dual graph regularized nonnegative matrix factorization (ODGNMF) method and its modified version: an orthogonal dual graph regularized nonnegative matrix tri-factorization (ODGNMTF) method. Compared with the existing models, our models can preserve the geometrical structures of data manifold and feature manifold by constructing two graphs, and ensure the orthogonality of factor matrices such that they have better NMF performance. Then, two efficient algorithms are developed to solve the models, and the convergence theory of the algorithms is established. Numerical tests by applying our algorithms to mine randomly generated data sets and well-known public databases demonstrate that ODGNMF and ODGNMTF have better numerical performance than the state-of-the-art algorithms in view of computational cost, robustness, sensitivity and sparseness.

Let Γ be a triangulation of a connected closed 2-dimensional (not necessarily orientable) surface. Using zigzags (closed left–right walks), for every face of Γ we define the z -monodromy which acts on the oriented edges of this face. There are precisely 7 types of z -monodromies. We consider the following two cases: (M1) the z -monodromy is identity, (M2) the z -monodromy is the consecutive passing of the oriented edges. Our main result is the following: the subgraphs of the dual graph Γ ∗ formed by edges whose z -monodromies are of types (M1) and (M2), respectively, both are forests. We apply this statement to the connected sum of z -knotted triangulations.

In this paper, we describe a physical problem, based on electromagnetic fields, whose topological constraints are two-dimensional versions of Kirchhoff’s laws, involving 2-simplicial complexes embedded in $${\mathfrak {R}}^3$$ rather than graphs. The topological constraints are on flux and mmf vectors, which we show satisfy a ‘generalized Tellegen’s Theorem,’ i.e., that they constitute complementary orthogonal vector spaces analogous to voltage and current spaces for ordinary graph-based electrical circuits. We show that the problem of solving this two-dimensional electrical circuit reduces to that of solving an ordinary resistive electrical circuit that can be regarded as dual to it. We present a linear time algorithm for constructing, the above mentioned, dual electrical network. This algorithm is based on the construction of a triangle adjacency graph of the original embedded 2-simplicial complex. This graph contains the information of the order in which we encounter the triangles incident at an edge, when we rotate say clockwise with respect to the orientation of the edge. The triangle adjacency graph is processed through a ‘sliding’ algorithm which simulates sliding on the surfaces of the triangles, moving from one triangle to another which shares an edge with it but which also is adjacent with respect to the embedding of the complex in $${\mathfrak {R}}^3$$. The connectedness information provided by this algorithm is used to construct, in linear time on the size of the 2-simplicial complex, its dual graph.

The geometry of integer continued fractions and in particular, simple continued fractions has been recorded by exploring the underlying relationship | a d − b c | = 1 for a , b , c , d integers as it arises in the Farey tessellation of the hyperbolic plane H 2 and the array of Ford circles in the upper-half of the real plane R 2 . Simple continued fractions may also be represented as a path on a graph whose vertices are reduced rationals and on a dual graph with vertices that are the Farey triangles in the tessellation of H 2 under the modular group. This paper produces an analogue of the above results for Gaussian integer continued fractions by examining the condition | α γ − β δ | = 1 for α , β , γ , δ Gaussian integers. Through this exploration it is possible to extend the concept of Farey neighbors to Gaussian rationals, introduce Farey sum sets, and establish the Farey tessellation of H 3 by Farey octahedrons under the action of the Picard groups without reference to the fundamental domains of the groups. A geodesic algorithm to extract a Gaussian integer continued fraction for complex numbers is introduced that is a geometrical analogue of the simple continued fraction for real numbers.

Let $$F_q$$ be a finite field of q elements, $$\mathbb {V}$$ an n-dimensional vector space over $$F_q$$, and $$\mathbb {V}^*$$ the dual space of $$\mathbb {V}$$, i.e., the vector space of all linear function over $$\mathbb {V}$$. The graph $$\hbox {DG}(\mathbb {V})$$, called the dual graph of $$\mathbb {V}$$, is defined to be a bipartite graph, whose vertex set is partitioned into two coloring sets, respectively, consisting of all one-dimensional subspaces of $$\mathbb {V}$$ and all one-dimensional subspaces of $$\mathbb {V}^*$$, and there is an undirected edge between an one-dimensional subspace [v] of $$\mathbb {V}$$ and an one-dimensional subspace [f] of $$\mathbb {V}^*$$ if and only if $$f(v) = 0$$. In this paper, the domination number, independence number, diameter and girth of $$\hbox {DG}(\mathbb {V})$$ are, respectively, determined; some automorphisms of $$\hbox {DG}(\mathbb {V})$$ are introduced, and such a graph is proved to be distance transitive.

A cyclic quotient singularity of type p2∕pq − 1 (0 < q < p, (p, q) = 1)) has a smoothing whose Milnor fibre is a \(\mathbb Q\)HD, or rational homology disk (i.e., the Milnor number is 0). In the 1980s, we discovered additional examples of such singularities: three triply-infinite and six singly-infinite families, all weighted homogeneous. Later work of Stipsicz, Szabo, Bhupal, and the author proved that these were the only weighted homogeneous examples. In his UNC PhD thesis, our student Jacob Fowler completed the analytic classification of these singularities, and counted the number of smoothings in each case, except for types \(\mathcal W\), \(\mathcal N\), and \(\mathcal M\). In this paper, we describe his results, and settle these remaining cases; there is a unique \(\mathbb Q\)HD smoothing component except in the cases of an obvious symmetry of the resolution dual graph. The method involves study of configurations of rational curves on projective rational surfaces.

Nonnegative matrix factorization (NMF) is a classical low-rank approximation method of data matrix, which decomposes a high-dimensional data matrix into two nonnegative low-rank matrices, namely basis matrix and coefficient matrix. In order to capture the local geometric structure of original dataset, manifold learning methods are incorporated into NMF framework. Motivated by recent progress in dual graph regularization, by considering the geometric structures of both the data manifold and the feature manifold, Orthogonal Dual-graph NMF (ODNMF) algorithms were proposed, which imposed orthogonality constraints on basis matrix or coefficient matrix. Since the projection directions were mutually orthogonal, the representation power of data samples was enhanced, thus ODNMF methods are more robust for data clustering. The extensive experimental results on UCI, text and face image data sets have demonstrated the superiority of the proposed methods.

In recent years, single-cell RNA sequencing (scRNA-seq) technology has made significant progress in many fields and become an important means to study cell dynamics. How to effectively mine valuable biological information from these sequencing data is a topic worthy of researching. In this paper, two new methods based on traditional principal component analysis (PCA) are proposed and used to scRNA-seq data. The first method named dual graph regularized PCA (DGPPCA) is based on Frobenius-norm and $\mathrm{L}_{2,\mathrm{p}}$-norm constraints, and the method named the dual graph-regularization PCA (DG2PPCA) is based on the nonconvex proximal $\mathrm{L}_{\mathrm{p}}$-norm $(0\lt p\lt 1)$ and the $\mathrm{L}_{2,\mathrm{p}}$-norm constraints. We apply these two new methods to five scRNA-seq datasets, and perform bi-clustering on genes and samples at the same time. Extensive experiments are conducted to explore the influence of the combination of different norm constraints in the two optimization models based on dual Graph regularized PCA. The visual experimental results confirmed the effectiveness of these two methods.

Arising from structural graph theory, treewidth has become a focus of study in fixed-parameter tractable algorithms in various communities including combinatorics, integer-linear programming, and numerical analysis. Many NP-hard problems are known to be solvable in $\widetilde{O}(n \cdot 2^{O(\mathrm{tw})})$ time, where $\mathrm{tw}$ is the treewidth of the input graph. Analogously, many problems in P should be solvable in $\widetilde{O}(n \cdot \mathrm{tw}^{O(1)})$ time; however, due to the lack of appropriate tools, only a few such results are currently known. [Fom+18] conjectured this to hold as broadly as all linear programs; in our paper, we show this is true: Given a linear program of the form $\min_{Ax=b,\ell \leq x\leq u} c^{\top} x$, and a width-$\tau$ tree decomposition of a graph $G_A$ related to $A$, we show how to solve it in time $$\widetilde{O}(n \cdot \tau^2 \log (1/\varepsilon)),$$ where $n$ is the number of variables and $\varepsilon$ is the relative accuracy. Combined with recent techniques in vertex-capacitated flow [BGS21], this leads to an algorithm with $\widetilde{O}(n \cdot \mathrm{tw}^2 \log (1/\varepsilon))$ run-time. Besides being the first of its kind, our algorithm has run-time nearly matching the fastest run-time for solving the sub-problem $Ax=b$ (under the assumption that no fast matrix multiplication is used). We obtain these results by combining recent techniques in interior-point methods (IPMs), sketching, and a novel representation of the solution under a multiscale basis similar to the wavelet basis.

Given a point configuration A, we uncover a connection between polynomial-reproducing spline spaces over subsets of conv(A) and fine zonotopal tilings of the zonotope Z(V) associated to the corresponding vector configuration. This link directly generalizes a known result on Delaunay configurations and naturally encompasses, due to its combinatorial character, the case of repeated and affinely dependent points in A. We prove the existence of a general iterative construction process for such spaces. Finally, we turn our attention to regular fine zonotopal tilings, specializing our previous results and exploiting the adjacency graph of the tiling to propose a set of practical algorithms for the construction and evaluation of the associated spline functions., Revised version March 2021

This survey may be seen as an introduction to the use of toric and tropical geometry in the analysis of plane curve singularities, which are germs (C, o) of complex analytic curves contained in a smooth complex analytic surface S. The embedded topological type of such a pair (S, C) is usually defined to be that of the oriented link obtained by intersecting C with a sufficiently small oriented Euclidean sphere centered at the point o, defined once a system of local coordinates (x, y) was chosen on the germ (S, o). If one works more generally over an arbitrary algebraically closed field of characteristic zero, one speaks instead of the combinatorial type of (S, C). One may define it by looking either at the Newton-Puiseux series associated to C relative to a generic local coordinate system (x, y), or at the set of infinitely near points which have to be blown up in order to get the minimal embedded resolution of the germ (C, o) or, thirdly, at the preimage of this germ by the resolution. Each point of view leads to a different encoding of the combinatorial type by a decorated tree: an Eggers-Wall tree, an Enriques diagram, or a weighted dual graph. The three trees contain the same information, which in the complex setting is equivalent to the knowledge of the embedded topological type. There are known algorithms for transforming one tree into another. In this paper we explain how a special type of two-dimensional simplicial complex called a lotus allows to think geometrically about the relations between the three types of trees. Namely, all of them embed in a natural lotus, their numerical decorations appearing as invariants of it. This lotus is constructed from the finite set of Newton polygons created during any process of resolution of (C, o) by successive toric modifications.

A now classical construction due to Kato and Nakayama attaches a topological space (the "Betti realization") to a log scheme over $\mathbf{C}$. We show that in the case of a log smooth degeneration over the standard log disc, this construction allows one to recover the topology of the germ of the family from the log special fiber alone. We go on to give combinatorial formulas for the monodromy and the $d^2$ differentials acting on the nearby cycle complex in terms of the log structures. We also provide variants of these results for the Kummer etale topology. In the case of curves, these data are essentially equivalent to those encoded by the dual graph of a semistable degeneration, including the monodromy pairing and the Picard-Lefschetz formula., Comment: 76 pages, 1 figure

This paper deals with the invariant $$R_X$$ called the RR-correction term, which appears in the Riemann–Roch and Numerical Adjunction Formulas for normal surface singularities. Typically, $$R_X=\delta ^\text {top}_X-\delta ^\text {an}_X$$ decomposes as difference of topological and analytical local invariants of its singularities. The invariant $$\delta ^\text {top}_X$$ is well understood and depends only on the dual graph of a good resolution. The purpose of this paper is to give a new interpretation for $$\delta ^\text {an}_X$$ , which in the case of cyclic quotient singularities can be explicitly computed via generic divisors. We also include two types of applications: one is related to the McKay decomposition of reflexive modules in terms of special reflexive modules in the context of the McKay correspondence. The other application answers two questions posed by Blache (Abh Math Semin Univ Hambg 65:307–340, 1995) on the asymptotic behavior of the invariant $$R_X$$ of the pluricanonical divisor.

Given an algebraic variety X defined over an algebraically closed field, we study the space RZ(X,x) consisting of all the valuations of the function field of X which are centered in a closed point x of X. We concentrate on its homeomorphism type. We prove that, when x is a regular point, this homeomorphism type only depends on the dimension of X. If x is a singular point of a normal surface, we show that it only depends on the dual graph of a good resolution of (X,x) up to some precise equivalence. This is done by studying the relation between RZ(X,x) and the normalized non-Archimedean link of x in X coming from the point of view of Berkovich geometry. We prove that their behavior is the same., 31 pages

Illusie has suggested that one should think of the classifying group of $M_X^{gp}$-torsors on a logarithmically smooth curve $X$ over a standard logarithmic point as a logarithmic analogue of the Picard group of $X$. This logarithmic Picard group arises naturally as a quotient of the algebraic Picard group by lifts of the chip firing relations of the associated dual graph. We connect this perspective to Baker and Norine's theory of ranks of divisors on a finite graph, and to Amini and Baker's metrized complexes of curves. Moreover, we propose a definition of a combinatorial rank for line bundles on $X$ and prove that an analogue of the Riemann-Roch formula holds for our combinatorial rank. Our proof proceeds by carefully describing the relationship between the logarithmic Picard group on a logarithmic curve and the Picard group of the associated metrized complex. This approach suggests a natural categorical framework for metrized complexes, namely the category of logarithmic curves., 15 pages, minor changes. Final version to appear in Mathematische Zeitschrift

The theory of Newton–Okounkov bodies attaches a convex body to a line bundle on a variety equipped with a flag of subvarieties. This convex body encodes the asymptotic properties of sections of powers of the line bundle. In this article, we study Newton–Okounkov bodies for schemes defined over discrete valuation rings. We give the basic properties and then focus on the case of toric schemes and semistable curves. We provide a description of the Newton–Okounkov bodies for semistable curves in terms of the Baker–Norine theory of linear systems on graphs, finding a connection with tropical geometry. We do this by introducing an intermediate object, the Newton–Okounkov linear system of a divisor on a curve. We prove that it is equal to the set of effective elements of the real Baker–Norine linear system of the specialization of that divisor on the dual graph of the curve. As a bonus, we obtain an asymptotic algebraic geometric description of the Baker–Norine linear system.

The Clar number of a (hydro)carbon molecule, introduced by Clar (The aromatic sextet, 1972), is the maximum number of mutually disjoint resonant hexagons in the molecule. Calculating the Clar number can be formulated as an optimization problem on 2-connected plane graphs. Namely, it is the maximum number of mutually disjoint even faces a perfect matching can simultaneously alternate on. It was proved by Abeledo and Atkinson (Linear Algebra Appl 420(2):441–448, 2007) that the Clar number can be computed in polynomial time if the plane graph has even faces only. We prove that calculating the Clar number in general 2-connected plane graphs is $$\mathsf {NP}$$ -hard. We also prove $$\mathsf {NP}$$ -hardness of the maximum independent set problem for 2-connected plane graphs with odd faces only, which may be of independent interest. Finally, we give an exact algorithm that determines the Clar number of a given 2-connected plane graph. The algorithm has a polynomial running time if the length of the shortest odd join in the planar dual graph is fixed, which gives an efficient algorithm for some fullerene classes, such as carbon nanotubes.

In the paper Combinatorica 33(2) (2013) 231–252, Huggett and Moffatt characterized all bipartite partial duals of a plane graph in terms of oriented circuits in its medial graph. An open problem posed in their paper is the characterization of Eulerian partial duals of plane graphs. In this article, we solve this problem by considering half-edge orientations of medial graphs.

A sliding camera in an orthogonal polygon P —that is, a polygon all of whose edges are axis-parallel—is a point guard g that travels back and forth along an axis-parallel line segment s inside P . A point p in P is guarded by g if and only if there exists a point q on s such that line segment pq is normal to s and contained in P . In the minimum sliding cameras (MSC) problem, the objective is to guard P with the minimum number of sliding cameras. We give a dynamic programming algorithm that solves the MSC problem exactly on monotone orthogonal polygons in O ( n ) time, improving the 2-approximation algorithm of Katz and Morgenstern (2011). More generally, our algorithm can be used to solve the MSC problem in O ( n ) time on simple orthogonal polygons P for which the dual graph induced by the vertical decomposition of P is a path. Our results provide the first polynomial-time exact algorithms for the MSC problem on a non-trivial subclass of orthogonal polygons.

We extend to infinite graphs the matroidal characterization of finite graph duality, that two graphs are dual iff they have complementary spanning trees in some common edge set. The naive infinite analogue of this fails. The key in an infinite setting is that dual trees must share between them not only the edges of their host graphs but also their ends: the statement that a set of edges is acyclic and connects all the vertices in one of the graphs iff the remaining edges do the same in its dual will hold only once each of the two graphs' common ends has been assigned to one graph but not the other, and ‘cycle’ and ‘connected’ are interpreted topologically in the space containing the respective edges and precisely the ends thus assigned. This property characterizes graph duality: if, conversely, the spanning trees of two infinite graphs are complementary in this end-sharing way, the graphs form a dual pair.

In this paper we study alternating cycles in graphs embedded in a surface. We observe that 4-vertex-colorability of a triangulation on a surface can be expressed in terms of spanninq quadrangulations, and we establish connections between spanning quadrangulations and cycles in the dual graph which are noncontractible and alternating with respect to a perfect matching. We show that the dual graph of an Eulerian triangulation of an orientable surface other than the sphere has a perfect matching M and an M-alternating noncontractible cycle. As a consequence, every Eulerian triangulation of the torus has a nonbipartite spanning quadrangulation. For an Eulerian triangulation G of the projective plane the situation is different: If the dual graph \(G^*\) is nonbipartite, then \(G^*\) has no noncontractible alternating cycle, and all spanning quadrangulations of G are bipartite. If the dual graph \(G^*\) is bipartite, then it has a noncontractible, M-alternating cycle for some (and hence any) perfect matching, G has a bipartite spanning quadrangulation and also a nonbipartite spanning quadrangulation.

An isoradial graph is a planar graph in which each face is inscribable into a circle of common radius. We study the 2-dimensional perfect matchings on a bipartite isoradial graph, obtained from the union of an isoradial graph and its interior dual graph. Using the isoradial graph to approximate a simply-connected domain bounded by a simple closed curve, by letting the mesh size go to zero, we prove that in the scaling limit, the distribution of height is conformally invariant and converges to a Gaussian free field.

Though existing works of sign prediction have reasonable prediction performances, they suffer from the data sparseness problem, especially for the negative link prediction. Most nodes in signed social networks are connected to very limited number of other nodes, which could not provide enough knowledge for sign prediction. This paper, therefore, proposes a novel edge-dual graph preserving sign prediction model, which reconstructs the signed social network by converting the original graph into the edge-dual graph, uses Jaccard coefficient to measure the node similarity and applies support vector machine classifier to predict signs. The proposed method reconstructs the graph by converting edges of the original graph into nodes of the edge-dual graph, and creating edges for the edge-dual graph according to the connections of edges in the original graph. It is mathematically and experimentally verified that the sparseness of the signed social networks can be significantly reduced by the proposed method. Using the publicly available data sets, it is verified that the average degree of signed social networks can be 7 to 8 times enlarged by the proposed method and the sign prediction accuracy can be improved around 10% comparing with the existing works.

We define a divisorial motivic zeta function for stable curves with marked points which agrees with Kapranov's motivic zeta function when the curve is smooth and unmarked. We show that this zeta function is rational, and give a formula in terms of the dual graph of the curve., 8 pages, 4 figures

Endomorphisms of Weyl algebras are studied using bimodules. Initially, for a Weyl algebra over a field of characteristic zero, Bernstein's inequality implies that holonomic bimodules finitely generated from the right (respectively, left) form a monoidal category. The most important bimodule in this paper is the graph of an endomorphism. We prove that the graph of an endomorphism of a Weyl algebra over a field of characteristic zero is a simple bimodule. The simplicity of the tensor product of the dual graph and the graph is equivalent to the Dixmier conjecture. It is also shown how the graph construction leads to a non-commutative Gröbner basis algorithm for detecting invertibility of an endomorphism for Weyl algebras and computing the inverse over arbitrary fields.

A digital image can be perceived as a 2.5D surface consisting of pixel coordinates and the intensity of pixel as height of the point in the surface. Such surfaces can be e ciently represented by the pair of dual plane graphs: neighborhood (primal) graph and its dual. By de ning ori- entation of edges in the primal graph and use of Local Binary Patters (LBPs), we can categorize the vertices corresponding to the pixel into critical (maximum, minimum, saddle) or slope points. Basic operation of contraction and removal of edges in primal graph result in con guration of graphs with di erent combinations of critical and non-critical points. The faces of graph resemble a slope region after restoration of the contin- uous surface by successive monotone cubic interpolation. In this paper, we de ne orientation of edges in the dual graph such that it remains consistent with the primal graph. Further we deliver the necessary and su cient conditions for merging of two adjacent slope regions.

For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that 1. the subgraph induced by each cluster is drawn in the interior of the corresponding disk, 2. each edge intersects any disk at most once, and 3. the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Qing-Wen Feng, Robert F. Cohen, and Peter Eades. Planarity for clustered graphs. ESA'95], has only been recently settled [Radoslav Fulek and Csaba D. T\'oth. Atomic Embeddability, Clustered Planarity, and Thickenability. To appear at SODA'20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs. We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT algorithm for embedded clustered graphs, when parameterized by the carving-width of the dual graph of the input. This is the first FPT algorithm for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, in the general case, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and T\'oth. To further strengthen the relevance of this result, we show that the C-Planarity Testing problem retains its computational complexity when parameterized by several other graph-width parameters, which may potentially lead to faster algorithms., Comment: Extended version of the paper "C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width" to appear in the Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

This work is about graphs arising from Reuleaux polyhedra. Such graphs must necessarily be planar, $3$-connected and strongly self-dual. We study the question of when these conditions are sufficient. If $G$ is any such a graph with isomorphism $\tau : G \to G^*$ (where $G^*$ is the unique dual graph), a metric mapping is a map $\eta : V(G) \to \mathbb R^3$ such that the diameter of $\eta(G)$ is $1$ and for every pair of vertices $(u,v)$ such that $u\in \tau(v)$ we have dist$(\eta(u),\eta(v)) = 1$. If $\eta$ is injective, it is called a metric embedding. Note that a metric embedding gives rise to a Reuleaux Polyhedra. Our contributions are twofold: Firstly, we prove that any planar, $3$-connected, strongly self-dual graph has a metric mapping by proving that the chromatic number of the diameter graph (whose vertices are $V(G)$ and whose edges are pairs $(u,v)$ such that $u\in \tau(v)$) is at most $4$, which means there exists a metric mapping to the tetrahedron. Furthermore, we use the Lov\'asz neighborhood-complex theorem in algebraic topology to prove that the chromatic number of the diameter graph is exactly $4$. Secondly, we develop algorithms that allow us to obtain every such graph with up to $14$ vertices. Furthermore, we numerically construct metric embeddings for every such graph. From the theorem and this computational evidence we conjecture that every such graph is realizable as a Reuleaux polyhedron in $\mathbb R^3$. In previous work the first and last authors described a method to construct a constant-width body from a Reuleaux polyhedron. So in essence, we also construct hundreds of new examples of constant-width bodies. This is related to a problem of V\'azsonyi, and also to a problem of Blaschke-Lebesgue.

The Separatrix Theorem of C. Camacho and P. Sad says that there exists at least one invariant curve (separatrix) passing through the singularity of a germ of holomorphic foliation on complex surface, when the surface underlying the foliation is smooth or when it is singular and the dual graph of resolution surface singularity is a tree. Under some assumptions, we obtain existence of separatrix even when the resolution dual graph of the surface singular point is not a tree. It will be necessary to require an extra condition of the foliation, namely, absence of saddle-node in its reduction of singularities.

One of the approaches in machine learning is probabilistic models that operate with such concepts as binary neurons, the energy of a system, the normalization constant (partition function), the entropy, etc. Most of them are migrated to machine learning from physics. In solid-state physics, the most interesting are the results obtained using asymptotic approximations for crystal lattices of infinite dimensions. One of such most investigated objects is the infinite two-dimensional lattice of Ising spin model. In machine learning, on the contrary, lattices of finite sizes are of the greatest interest. In this paper we describe algorithms for the exact calculation of the partition function and other statistical quantities for the planar Ising model of finite dimensions (from N = 5 × 5 to N = 1000 × 1000). A polynomial algorithm for finding the partition function is described in detail, based on the calculation of the determinant of the dual graph of a planar lattice. Also, the results obtained by the classical Metropolis algorithm are discussed. The results obtained with the help of these algorithms allow us to draw some conclusions about the behavior of the model of the two-dimensional Ising model in the finite-size case and compare them with the asymptotic formulas.

Distance-hereditary graphs can be characterized by every cycle of length at least 5 having crossing chords. This makes distance-hereditary graphs susceptible to dualizing, using the common extension of geometric face/vertex planar graph duality to cycle/cutset duality as in abstract matroidal duality. The resulting “DH* graphs” are characterized and then analyzed in terms of connectivity. These results are used in a special case of plane-embedded graphs to justify viewing DH* graphs as the duals of distance-hereditary graphs.

Recently, manifold regularization with the affinity graph in matrix factorization-related studies, such as dual-graph regularized concept factorization (GCF), have yielded impressive results for clustering. However, due to the noisy and irrelevant features of the data samples, the affinity graph constructed directly from the original feature space is not necessarily a reliable reflection of the intrinsic manifold of the data samples. To overcome this problem, we integrate feature selection into the construction of the data (feature) graph and propose a novel algorithm called adaptive dual-graph regularized CF with Feature selection $$(\hbox {ADGCF}_{\mathrm{FS}})$$(ADGCFFS), which simultaneously considers the geometric structures of both the data manifold and the feature manifold. We unify feature selections, dual-graph regularized CF into a joint objective function and minimize this objective function with iterative and alternative updating optimization schemes. Moreover, we provide the convergence proof of our optimization scheme. Experimental results on TDT2 and Reuters document datasets, COIL20 and PIE image datasets demonstrate the effectiveness of our proposed method.

This paper generalizes a graph-theoretical result of Maffray to binary matroids. In particular, we prove that a connected simple binary matroid M has no odd circuits other than triangles if and only if M is affine, M is M(K4) or F7, or M is the cycle matroid of a graph consisting of a collection of triangles all of which share a common edge. This result implies that a 2-connected loopless graph G has no odd bonds of size at least five if and only if G is Eulerian or G is a subdivision of either K4 or the graph that is obtained from a cycle of parallel pairs by deleting a single edge.

We present a fundamental framework for organizing exploration, coverage, and surveillance by a swarm of robots with limited individual capabilities, based on triangulating an unknown environment with a multi-robot system. Locally, an individual triangle is easy for a single robot to manage and covers a small area; globally, the topology of the triangulation approximately captures the geometry of the entire environment. Combined, a multi-robot system can explore, map, navigate, and patrol. Algorithms can store information in triangles that the robots can read and write as they run their algorithms. This creates a physical data structure (PDS) that is both robust and versatile. We study distributed approaches to triangulating an unknown, two-dimensional Euclidean space using a multi-robot network. The resulting PDS is a compact representation of the workspace, contains distributed knowledge of each triangle, encodes the dual graph of the triangulation, and supports reads and writes of auxiliary data. The ability to store and process this auxiliary information enables the simple robots to solve complex problems. We develop distributed algorithms for dual-graph navigation, patrolling, construction of a topological Voronoi tessellation, and location of the geodesic centers in non-convex regions. We provide theoretical performance guarantees for the quality of constructed triangulation and the connectivity of a dual graph in the triangulation. In addition, we show that the path lengths of the physical navigation are within a constant factor of the shortest-path Euclidean distance. We validate these theoretical results with simulations and experiments with a dozen or more robots.

We consider an embedding of a $2$-dimensional CW complex into the $3$-sphere, and construct it's dual graph. Then we obtain a homogeneous system of linear equations from the $2$-dimensional CW complex in the first homology group of the complement of the dual graph. By checking that the homogeneous system of linear equations does not have an integral solution, we show that some $2$-dimensional CW complexes cannot be embedded into the 3-sphere., 10 page, 11 figures

We extend the # operator in a natural way and derive new types of counting complexity classes. While in the case of # C classes (where C could be some circuit-based class like NC 1 ) only proofs for acceptance of some input are being counted, one can also count proofs for rejection. The Zap- C complexity classes we propose here implement this idea.We show that in certain cases Zap- C lies between # C and Gap- C which could help understanding the relationship between # C and Gap- C . In particular we consider Zap- NC 1 and polynomial size branching programs of bounded and unbounded width. Finally we argue about negative proofs in Turing machines and how those relate to open questions.

Low-rank representation (LRR) has received considerable attention in subspace segmentation due to its effectiveness in exploring low-dimensional subspace structures embedded in data. To preserve the intrinsic geometrical structure of data, a graph regularizer has been introduced into LRR framework for learning the locality and similarity information within data. However, it is often the case that not only the high-dimensional data reside on a non-linear low-dimensional manifold in the ambient space, but also their features lie on a manifold in feature space. In this paper, we propose a dual graph regularized LRR model (DGLRR) by enforcing preservation of geometric information in both the ambient space and the feature space. The proposed method aims for simultaneously considering the geometric structures of the data manifold and the feature manifold. Furthermore, we extend the DGLRR model to include non-negative constraint, leading to a parts-based representation of data. Experiments are conducted on several image data sets to demonstrate that the proposed method outperforms the state-of-the-art approaches in image clustering.

The Tutte polynomial is originally a bivariate polynomial which enumerates the colorings of a graph and of its dual graph. Ardila extended in 2007 the definition of the Tutte polynomial on the real hyperplane arrangements. He particularly computed the Tutte polynomials of the hyperplane arrangements associated to the classical Weyl groups. Those associated to the exceptional Weyl groups were computed by De Concini and Procesi one year later. This article has two objectives: On one side, we extend the Tutte polynomial computing to the complex hyperplane arrangements. On the other side, we introduce a wider class of hyperplane arrangements which is that of the symmetric hyperplane arrangements. Computing the Tutte polynomial of a symmetric hyperplane arrangement permits us to deduce the Tutte polynomials of some hyperplane arrangements, particularly of those associated to the imprimitive reflection groups., 18 pages. arXiv admin note: text overlap with arXiv:1705.10753

This paper develops a Cambrian extension of the work of C. Ceballos, A. Padrol and C. Sarmiento on $��$-Tamari lattices and their tropical realizations. For any signature $\varepsilon \in \{\pm\}^n$, we consider a family of $\varepsilon$-trees in bijection with the triangulations of the $\varepsilon$-polygon. These $\varepsilon$-trees define a flag regular triangulation $\mathcal{T}^\varepsilon$ of the subpolytope $\operatorname{conv} \{(\mathbf{e}_{i_\bullet}, \mathbf{e}_{j_\circ}) \, | \, 0 \le i_\bullet < j_\circ \le n+1 \}$ of the product of simplices $\triangle_{\{0_\bullet, \dots, n_\bullet\}} \times \triangle_{\{1_\circ, \dots, (n+1)_\circ\}}$. The oriented dual graph of the triangulation $\mathcal{T}^\varepsilon$ is the Hasse diagram of the (type $A$) $\varepsilon$-Cambrian lattice of N. Reading. For any $I_\bullet \subseteq \{0_\bullet, \dots, n_\bullet\}$ and $J_\circ \subseteq \{1_\circ, \dots, (n+1)_\circ\}$, we consider the restriction $\mathcal{T}^\varepsilon_{I_\bullet, J_\circ}$ of the triangulation $\mathcal{T}^\varepsilon$ to the face $\triangle_{I_\bullet} \times \triangle_{J_\circ}$. Its dual graph is naturally interpreted as the increasing flip graph on certain $(\varepsilon, I_\bullet, J_\circ)$-trees, which is shown to be a lattice generalizing in particular the $��$-Tamari lattices in the Cambrian setting. Finally, we present an alternative geometric realization of $\mathcal{T}^\varepsilon_{I_\bullet, J_\circ}$ as a polyhedral complex induced by a tropical hyperplane arrangement., 16 pages, 11 figures