New maximally linkless graphs found with fewer edges.
problem Finding graphs without any links in 3D space.
method Demonstrated new maximally linkless graphs with improved edge count.
result Found maximally linkless graphs with edges.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “maximally linkless graphs”
New bounds on maximal linkless graphs with improved edge-to-vertex ratios.
problem Finding maximal linklessly embeddable graphs with improved edge-to-vertex ratios.
method Constructing families of graphs and proving necessary and sufficient conditions for clique sums.
result Improved edge-to-vertex ratios for maximal linklessly embeddable graphs.
Notes a flaw in a proof about embedding graphs.
problem A flaw in proving Sachs' conjecture about graph embeddings.
method Analyzing Stanfield's proof for gaps.
result Identifies a significant error in the proof.
Constructions stemming from non-separating planar graphs and their Colin de Verdière invariantmath.CO
New constructions from non-separating planar graphs improve understanding of graph linkability and knotability.
problem Understanding linkability and knotability of graph complements.
method Using maximal non-separating planar graphs to construct examples of maximal linkless and knotless graphs, and analyzing their Colin de Verdière invariant.
result The Colin de Verdière invariant of the complement of a maximal non-separating planar graph satisfies μ(cG) ≤ n-4, and equality holds.
Study finds maximal linklessly embeddable graphs up to 11 vertices and their complements.
problem Characterizing linklessly embeddable graphs and their complements.
method Comprehensive search and verification of graphs up to 11 vertices.
result For graphs of order 11, either the graph or its complement is intrinsically linked.
Classifies intrinsically linked tournaments by their score sequences.
problem Classifying intrinsically linked tournaments using their score sequences.
method Examining the score sequences of tournaments and identifying linkless sequences.
result The vast majority of score sequences for 8-vertex tournaments are linkless.
Graphs embeddable on torus and linklessly in 3D can be embedded linklessly in standard torus.
problem Embedding linklessly in a standard torus for graphs embeddable on torus and in 3D.
method Analyzing graphs of order 9 and below, showing linkless embedding in standard torus.
result For graphs of order 9 and below, linkless embedding in standard torus is possible.
New graphs found that can be drawn without crossing links.
problem Finding graphs that can be drawn without links crossing.
method Provided specific examples for each .
result Infinite family of graphs linklessly embeddable and Tutte-4-connected.
A simpler proof for apex graphs in McCarty and Thomas' conjecture.
problem Proving a conjecture about apex graphs and their linklessly embeddable properties.
method Shorter and simpler proof for the apex case.
result A shorter and simpler proof for the apex case of the conjecture.
We announce results about flat (linkless) embeddings of graphs in 3-space. A piecewise-linear embedding of a graph in 3-space is called {\it flat} if every circuit of the graph bounds a disk disjoint from the rest of the graph. We have shown: (i) An embedding is flat if and only if the fundamental group of the compleme…
We consider intrinsic linking and knotting in the context of directed graphs. We construct an example of a directed graph that contains a consistently oriented knotted cycle in every embedding. We also construct examples of intrinsically 3-linked and 4-linked directed graphs. We introduce two operations, consistent edg…
Study embeddability of 2-complexes in 4-space, proving Heawood family's excluded minors.
problem Whether a 2-dimensional CW complex embeds in .
method Operations preserving embeddability, constructions of non-preserving transformations, study of 4-flat graphs.
result Prove 78 graphs of Heawood family are excluded minors for 4-flat graphs.
GRAPH-BERT uses only attention for graph representation learning.
problem Graph neural networks over-rely on graph links and suffer from performance issues.
method GRAPH-BERT uses only attention mechanism without graph convolution or aggregation, trained on sampled subgraphs.
result GRAPH-BERT outperforms existing GNNs in learning effectiveness and efficiency.
Maximal knotless graphsmath.GT
Maximal knotless graphs have at least 74% of their vertices' edges.
problem Characterizing maximal knotless graphs and understanding their edge constraints.
method Analyzing edge maximality and constructing graphs to meet constraints.
result There exists an infinite family of maximal knotless graphs with fewer edges than previously thought.
The paper shows conflict graphs of Petersen family graphs are mostly unbalanced.
problem Understanding the balance of conflict graphs in Petersen family graphs.
method Analyzing maximally planar subgraphs and their conflict graphs.
result All but three strong conflict graphs from Petersen Family Graphs are unbalanced.
The study extends Tutte's conflict graph concept to nonplanar graphs.
problem Understanding the structure of nonplanar graphs through conflict graphs.
method Defining a signed conflict graph for maximally planar subgraphs and analyzing their balance.
result For graphs with a flat embedding, every maximal planar subgraph has unbalanced conflict graphs if and only if the graph is intrinsically linked.
Maximal diameter theorem for graphs with positive Ricci curvature.
problem Diameter comparison in directed graphs with positive Ricci curvature.
method Introduced a Lin-Lu-Yau type Ricci curvature for directed graphs and investigated rigidity properties for the equality case.
result Concluded a maximal diameter theorem of Cheng type.
Constructs graphs with singularities in a special space.
problem Creating graphs with specific singularities in a unique space.
method Using Weierstrass representation for minimal surfaces.
result Constructs entire singly periodic graphs with isolated cone-like singularities.
Maximal surfaces in Lorentz-Minkowski space have conjugate graphs.
problem Characterizing maximal surfaces in Lorentz-Minkowski space.
method Three proofs showing correspondence to minimal surfaces in Euclidean space.
result Conjugate surface of a maximal graph over a convex domain is also a graph.
We extend Osserman's lemma on the generalized Gauss map of two-dimensional minimal graphs of higher codimension, construct a Jenkins-Serrin type special Lagrangian Scherk graph explicitly, and generalize Calabi's correspondence between minimal graphs and maximal graphs.
We show that the number of entire maximal graphs with finitely many singular points that are conformally equivalent is a universal constant that depends only on the number of singularities, namely 2^$ for graphs with n+1 singularities. We also give an explicit description of the family of entire maximal graphs with a f…
In the lorentzian product we give a comparison between the -volume of an entire -maximal graph and the -volume of the hyperbolic under the assumption that the gradient of the function defining the graph is bounded away from 1. As a consequence, we obtain a Bernstein type theor…
Algorithm calculates genus of embedded graphs on surfaces.
problem Finding minimal and maximal genus for graph embeddings.
method Constructing special branched coverings of the 2-sphere.
result Algorithm calculates orientable genus and maximal genus of graphs.
The grand arc graphmath.GT
New simplicial complex for infinite-type surfaces shows graph properties.
problem Characterizing infinite-type surfaces using graph theory.
method Constructing grand arc graph and analyzing its properties.
result Grand arc graph is infinite-diameter and δ-hyperbolic under certain conditions.
In this paper, we unify the Markov theory of a variety of different types of graphs used in graphical Markov models by introducing the class of loopless mixed graphs, and show that all independence models induced by -separation on such graphs are compositional graphoids. We focus in particular on the subclass of rib…
New method for fair influence maximization in social networks.
problem Maximizing influence while ensuring fairness across sensitive attributes.
method Co-training an auto-encoder and discriminator to create fair graph embeddings.
result Our method reduces disparity while maintaining competitive influence maximization performance.
New method constructs graphs from data efficiently, suitable for large datasets.
problem Memory and runtime limitations of traditional TMFG for large datasets.
method Uses k-Nearest Neighbors Graphs and memory management for scalable graph construction.
result Provides a parsimonious way to construct graphs for learning tasks.
GraphCL learns node representations by maximizing similarity between perturbed node features.
problem Learning node representations in graph data without labeled data.
method Contrastive learning of node embeddings using graph neural networks and a loss function.
result Significantly outperforms state-of-the-art in unsupervised node classification benchmarks.
Proposes a novel graph self-training method with EM regularization for semi-supervised node classification.
problem Handles noisy graph structures and feature spaces in semi-supervised node classification.
method Introduces an Expectation-Maximization (EM) regularization scheme for uncertainty-aware pseudo-label generation and model retraining.
result Significantly outperforms strong baselines by up to 2.5% in accuracy.
If the Lorentzian norm on a maximal surface in the 3-dimensional Lorentz-Minkowski space is positive and proper, then the surface is relative parabolic. As a consequence, entire maximal graphs with a closed set of isolated singularities are relative parabolic. Furthermore, maximal and minimal graphs over closed…
This work improves GNN training efficiency by maximizing ego-graph information.
problem Training dedicated GNNs is costly for large-scale graphs.
method Proposes EGI (Ego-Graph Information maximization) to capture essential graph information and establish a theoretical framework for transfer learning.
result Demonstrates the effectiveness of EGI in improving GNN training efficiency and transferability.
New theorem connects minimal and maximal surfaces, affecting graphness.
problem Understanding graphness of minimal surfaces in different spaces.
method Introducing a new deformation family and proving Krust-type theorems.
result Graphness of minimal surfaces in isotropic 3-space affects deformed surfaces.
Maximizing Mutual Information Across Feature and Topology Views for Learning Graph Representationscs.LG
A novel method integrates feature and topology views for unsupervised graph representation learning.
problem Lack of mutual information across feature and topology views in graph representation learning.
method Proposes a multi-view representation learning module and a common representation learning module using mutual information maximization and reconstruction loss minimization.
result Demonstrates effectiveness in integrating feature and topology views, achieving comparable or better performance than supervised methods.
We construct a partial order relation which acts on the set of 3-cliques of a maximal planar graph G and defines a unique hierarchy. We demonstrate that G is the union of a set of special subgraphs, named `bubbles', that are themselves maximal planar graphs. The graph G is retrieved by connecting these bubbles in a tre…
A new algorithm learns MAGs from data more efficiently using entropy.
problem Learning MAGs from data is unstable and computationally expensive.
method Uses entropy estimation and refined Markov property to score MAGs.
result Algorithm is polynomial in number of nodes and outperforms existing methods.
We show that a Born-Infeld soliton can be realised either as a spacelike minimal graph or timelike minimal graph over a timelike plane or a combination of both away from singular points. We also obtain some exact solutions of the Born-Infeld equation from already known solutions to the maximal surface equation. Further…
Iterative Proportional Fitting (IPF), combined with EM, is commonly used as an algorithm for likelihood maximization in undirected graphical models. In this paper, we present two iterative algorithms that generalize upon IPF. The first one is for likelihood maximization in discrete chain factor graphs, which we define …
The main goal of this survey is to illustrate geometric applications of the Poincaré Lemma to constant mean curvature equations. In 1970, Calabi introduced the duality between minimal graphs in three dimensional Euclidean space and maximal graphs in three dimensional Lorentz space. We construct two extensions of Calabi…
A variety of graph neural networks (GNNs) frameworks for representation learning on graphs have been recently developed. These frameworks rely on aggregation and iteration scheme to learn the representation of nodes. However, information between nodes is inevitably lost in the scheme during learning. In order to reduce…
In this paper we establish some parabolicity criteria for maximal surfaces immersed into a Lorentzian product space of the form , where is a connected Riemannian surface with non-negative Gaussian curvature and is endowed with the Lorentzian product metric $<,>=<,>_M…
Explainable, Stable, and Scalable Graph Convolutional Networks for Learning Graph Representationcs.LG
New GCNs solve graph embedding problems efficiently and interpretably.
problem Graph embedding for scalable and interpretable machine learning.
method Proposed two GCNs: CAFE-GCN and sphere-GCN, based on constrained optimization.
result Both GCNs yield good approximations of dominant eigenvectors and perform dimensionality reduction.
Spatio-temporal graphs such as traffic networks or gene regulatory systems present challenges for the existing deep learning methods due to the complexity of structural changes over time. To address these issues, we introduce Spatio-Temporal Deep Graph Infomax (STDGI)---a fully unsupervised node representation learning…
MissNODAG learns cyclic causal graphs from incomplete data.
problem Causal discovery in systems with feedback loops and missing data.
method Differentiable framework integrating additive noise model and expectation-maximization.
result MissNODAG uncovers cyclic structures and missingness mechanisms from partially observed data.
This paper proposes a method to learn graph representations without supervision.
problem Learning high-quality graph representations without external supervision.
method Graphical Mutual Information (GMI) to measure graph and hidden representation correlation.
result The proposed method outperforms state-of-the-art unsupervised counterparts and sometimes supervised ones.
Convolution operations designed for graph-structured data usually utilize the graph Laplacian, which can be seen as message passing between the adjacent neighbors through a generic random walk. In this paper, we propose PAN, a new graph convolution framework that involves every path linking the message sender and recei…
We consider the Dirichlet boundary value problem for graphical maximal submanifolds inside Lorentzian type ambient spaces, and obtain general existence and uniqueness results which apply to any codimension.
Graph products inherit Morse local-to-global property from their components.
problem Generalizing local-to-global property to graph products of infinite groups.
method Generalizing maximization procedure for relatively hierarchically hyperbolic groups and showing stable embeddings.
result Graph products of infinite Morse local-to-global groups have the Morse local-to-global property.
Maximizes mixing efficiency in surface braids.
problem Finding the maximum mixing efficiency in surface braids.
method Introduced an efficient algorithm to compute topological entropy and TEPO for surface braids.
result Conjectured a novel candidate braid to have maximal mixing efficiency.