arXiv research

We study the Thurston-Bennequin number of complete and complete bipartite Legendrian graphs. We define a new invariant called the total Thurston-Bennequin number of the graph. We show that this invariant is determined by the Thurston-Bennequin numbers of 3-cycles for complete graphs and by the Thurston-Bennequin number…

The symmetries of complex molecular structures can be modeled by the {\em topological symmetry group} of the underlying embedded graph. It is therefore important to understand which topological symmetry groups can be realized by particular abstract graphs. This question has been answered for complete graphs; it is natu…

We characterize which automorphisms of an arbitrary complete bipartite graph $K_{n,m}$ can be induced by a homeomorphism of some embedding of the graph in $S^3$.

We determine for which $n$, the complete bipartite graph $K_{n,n}$ has an embedding in $S^3$ whose topological symmetry group is isomorphic to one of the polyhedral groups: $A_4$, $A_5$, or $S_4$.

We present a discrete Morse-theoretic method for proving that a regular CW complex is homeomorphic to a sphere. We use this method to define bisimplices, the cells of a class of regular CW complexes we call bisimplicial complexes. The 1-skeleta of bisimplices are complete bipartite graphs making them suitable in constr…

Formula for $\mathfrak{sl}_2$ weight system on complete bipartite graphs.

The graph braid group of a complete bipartite graph is the fundamental group of a configuration space of points on the graph, which is a CAT(0) cube complex. We combine an analysis of the topology of links of vertices in this complex, the description of a hidden symmetry among the parameters, and known results from the…

A graph is intrinsically knotted if every embedding contains a knotted cycle. It is known that intrinsically knotted graphs have at least 21 edges and that the KS graphs, $K_7$ and the 13 graphs obtained from $K_7$ by $\nabla Y$ moves, are the only minor minimal intrinsically knotted graphs with 21 edges. This set incl…

Temperley-Lieb algebras have been generalized to sl(3) web spaces. Since a cubic bipartite planar graph with suitable directions on edges is a web, the quantum sl(3) invariants naturally extend to all cubic bipartite planar graphs. First we completely classify them as a connected sum of primes webs. We also provide a m…

We study the Seifert surfaces of a link by relating the embeddings of graphs by using induced graphs. As applications, we prove that every link $L$ is the boundary of an oriented surface which is obtained from a graph embedding of a complete bipartite graph $K_{2,n}$, where all voltage assignments on the edges of $K_{2…

We consider matrix completion for recommender systems from the point of view of link prediction on graphs. Interaction data such as movie ratings can be represented by a bipartite user-item graph with labeled edges denoting observed ratings. Building on recent progress in deep learning on graph-structured data, we prop…

We find the minimal number of links in an embedding of any complete $k$-partite graph on 7 vertices (including $K_7$, which has at least 21 links). We give either exact values or upper and lower bounds for the minimal number of links for all complete $k$-partite graphs on 8 vertices. We also look at larger complete bip…

The paper calculates a specific weight system for chord diagrams with a particular graph structure.

Let G be a connected bipartite graph with color classes E and V and root polytope Q. Regarding the hypergraph (V,E) induced by G, we prove that its interior polynomial is equivalent to the Ehrhart polynomial of Q, which in turn is equivalent to the h-vector of any triangulation of Q. It follows that the interior polyno…

A biclustering algorithm finds dense disjoint subgraphs in weighted bipartite graphs.

New research finds six bipartite intrinsically knotted graphs with 23 edges.

New model for detecting communities in weighted bipartite networks.

We study the class N of graphs, the right-angled Artin groups defined on which do not contain surface subgroups. We prove that a presumably smaller class N' is closed under amalgamating along complete subgraphs, and also under adding bisimplicial edges. It follows that chordal graphs and chordal bipartite graphs belong…

Proves Khovanov homology has no torsion for bipartite circle graphs.

Bipartite graphs have been used to represent data relationships in many data-mining applications such as in E-commerce recommendation systems. Since learning in graph space is more complicated than in Euclidian space, recent studies have extensively utilized neural nets to effectively and efficiently embed a graph's no…

Improved text summarization using belief propagation on weighted bipartite graphs.

A strong interaction is known to exist between edge-colored graphs (which encode PL pseudo-manifolds of arbitrary dimension) and random tensor models (as a possible approach to the study of Quantum Gravity). The key tool is the {\it G-degree} of the involved graphs, which drives the {\it $1/N$ expansion} in the tensor …

In his 1930 paper, Kuratowksi categorized planar graphs, proving that a finite graph $Γ$ is planar if and only if it does not contain a subgraph that is homeomorphic to $K_5$, the complete graph on 5 vertices, or $K_{3,3}$, the complete bipartite graph on six vertices. In their 2001 paper, Davis and Okun point out that…

New method for matching bipartite and unipartite graphs without collapsing.

We define integral odd Khovanov homology of principally unimodular bipartite graph-links.

We present evidence in support of a conjecture that a bipartite graph with at least five vertices in each part and |E(G)| \geq 4 |V(G)| - 17 is intrinsically knotted. We prove the conjecture for graphs that have exactly five or exactly six vertices in one part. We also show that there is a constant C_n such that a bipa…

Incorrect parity-based descriptions of realizable Gauss diagrams found, but bipartite graphs provide a valid approach.

We present a simple combinatorial model for quasipositive surfaces and positive braids, based on embedded bipartite graphs. As a first application, we extend the well-known duality on standard diagrams of torus links to twisted torus links. We then introduce a combinatorial notion of adjacency for bipartite graph links…

Improved bipartite link prediction using 2-hop paths.

The aim of this short note is to draw attention to a method by which the partition function and marginal probabilities for a certain class of random fields on complete graphs can be computed in polynomial time. This class includes Ising models with homogeneous pairwise potentials but arbitrary (inhomogeneous) unary pot…

An ordered and oriented 2-component link L in the 3-sphere is said to be achiral if it is ambient isotopic to its mirror image ignoring the orientation and ordering of the components. Kirk-Livingston showed that if L is achiral then the linking number of L is not congruent to 2 modulo 4. In this paper we study orientat…

New tests detect communities in dense bipartite graphs with high accuracy.

We generalize the construction of the Heegaard Floer homology for a singular knot to that for a balanced bipartite graph. For a given graph, we provide a combinatorial description of the Euler characteristic of its Heegaard Floer homology by using the "Kauffman states" on a graph diagram.

The study proves conjecture for specific Artin groups.

We give an algorithmic computation for the height of Kauffman's clock lattice obtained from a knot diagram with two adjacent regions starred and without crossing information specified. We show that this lattice is more familiarly the graph of perfect matchings of a bipartite graph obtained from the knot diagram by over…

The interior polynomial is an invariant of bipartite graphs, and a part of the HOMFLY polynomial of a special alternating link coincides with the interior polynomial of the Seifert graph of the link. We extend the interior polynomial to signed bipartite graphs, and we show that, in the planar case, it is equal to a par…

The interior polynomial is an invariant of (signed) bipartite graphs, and the interior polynomial of a plane bipartite graph is equal to a part of the HOMFLY polynomial of a naturally associated link. The HOMFLY polynomial $P_L(v,z)$ is a famous link invariant with many known properties. For example, the HOMFLY polynom…

In Bipartite Correlation Clustering (BCC) we are given a complete bipartite graph $G$ with `+' and `-' edges, and we seek a vertex clustering that maximizes the number of agreements: the number of all `+' edges within clusters plus all `-' edges cut across clusters. BCC is known to be NP-hard. We present a novel approx…

Improved model for grouping nodes in bipartite networks.

Neural execution solves complex graph problems like bipartite matching.

Quantum model for knotted graphs from knot theory.

We prove that every embedding of $K_{2n+1,2n+1}$ into $\R^3$ contains a non-split link of $n$-components. Further, given an embedding of $K_{2n+1,2n+1}$ in $\R^3$, every edge of $K_{2n+1,2n+1}$ is contained in a non-split $n$-component link in $K_{2n+1,2n+1}$.

Characterizes graphs with leveled embeddings and introduces new graph invariants.

Graph neural networks speed up nonnegative matrix factorization.

PAC learning simplified as bipartite matching.

Paper uses bipartite graph to forecast cross-market returns, revealing asymmetry.

New method embeds bipartite graphs into vectors, overcoming nonlinear challenges.

Bipartite data is common in data engineering and brings unique challenges, particularly when it comes to clustering tasks that impose on strong structural assumptions. This work presents an unsupervised method for assessing similarity in bipartite data. Similar to some co-clustering methods, the method is based on regu…