Quadratic bounds found for graph dimensions.
problem Understanding dimensions of arc and disk graphs.
method Quadratic upper bounds calculation.
result Asymptotic dimensions of arc and disk graphs have been bounded.
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,695 papers · 148 categories
Trend · papers per month
48 results for “Graph dimension”
Asymptotic dimension of planes and graphs is at most three.
problem Understanding the geometric complexity of planes and graphs.
method Analyzing geodesic spaces and their homeomorphisms to subsets in the plane.
result The asymptotic dimension of the plane and any planar graph is at most three.
Paper studies asymptotic dimension and Assouad-Nagata dimension of graphs and surfaces.
problem Understanding the asymptotic dimension and Assouad-Nagata dimension of graphs and surfaces.
method Analyzes asymptotic dimension of graph metrics and applies to surfaces, proving dimension bounds.
result Proves that complete Riemannian surfaces have Assouad-Nagata dimension at most 2.
Graphs on surfaces have a 2-dimensional large scale structure.
problem Understanding the large scale structure of graphs on surfaces.
method Proving asymptotic dimension for specific graph classes and surfaces.
result Graphs on surfaces have an asymptotic dimension of 2.
Graph Laplacians adapt to different manifold dimensions, while Dirichlet energies converge to a tensorized Dirichlet energy.
problem Understanding machine learning methods for data with varying intrinsic dimensions.
method Γ-convergence of graph Dirichlet energies and spectral convergence of graph Laplacians on intersecting manifolds of varying dimensions.
result Normalized Dirichlet energy converges to a tensorized Dirichlet energy that adapts to all dimensions simultaneously.
Borel asymptotic dimension of the Roller boundary of finite dimensional CAT(0) cube complexesmath.GT
Study shows Roller compactification's median graph has limited asymptotic dimension.
problem Understanding the asymptotic dimension of Roller compactifications.
method Proved using finite dimensional CAT(0) cube complexes and Borel median graph.
result Borel asymptotic dimension is bounded by the complex's dimension.
Contradiction graphs reveal VC dimension threshold.
problem Determining VC dimension of concept classes.
method Study contradiction graphs of binary concept classes.
result Single contradiction graph determines VC dimension.
In this paper, we define the curvature dimension inequalities CD(m, K) on finite directed graphs modifying the case of undirected graphs. As a main result, we evaluate m and K on finite directed graphs.
We introduce and study the conical curvature-dimension condition, , for graphs. We show that provides necessary and sufficient conditions for the underlying graph to satisfy a sharp global Poincaré inequality which in turn translates to a sharp lower bound for the first eigenvalues of these graphs.…
We give upper bounds, linear in rank, to the topological dimensions of the Gromov boundaries of the intersection graph, the free factor graph and the cyclic splitting graph of a finitely generated free group.
We find an upper bound for the asymptotic dimension of a hyperbolic metric space with a set of geodesics satisfying a certain boundedness condition studied by Bowditch. The primary example is a collection of tight geodesics on the curve graph of a compact orientable surface. We use this to conclude that a curve graph h…
WL meet VCcs.LG
The paper connects GNNs to VC dimension theory to study their generalization performance.
problem Understanding GNNs' ability to make meaningful predictions beyond the training set.
method Using Vapnik-Chervonenkis (VC) dimension theory in two settings: no upper bound on graph order and known upper bound.
result Tight connections between GNNs' bitlength, number of colors, and VC dimension in different settings.
We show that the asymptotic dimension of a hyperbolic relatively hyperbolic graph is finite provided that this holds true uniformly for the peripheral subgraphs and for the electrifiation. We use this to show that the asymptotic dimension of the disk graph of a handlebody of genus at least two is at most quadratic in t…
Paper shows graphs can be embedded in lower dimensions than expected.
problem Choosing the right embedding dimension for graph analysis.
method Utilizes hidden manifold structure to predict lower-dimensional embedding.
result Graphs can be embedded in much lower dimensions than previously thought.
We consider the problem of providing nonparametric confidence guarantees for undirected graphs under weak assumptions. In particular, we do not assume sparsity, incoherence or Normality. We allow the dimension to increase with the sample size . First, we prove lower bounds that show that if we want accurate infe…
The curve graph and related graphs are hyperbolic and have quasi-tree fibers.
problem Understanding the structure of the curve graph and related graphs.
method Analyzing a sequence of graphs with Lipschitz maps and proving hyperbolicity and quasi-tree properties.
result The graphs in the sequence are hyperbolic and have quasi-tree fibers, leading to bounds on asymptotic dimension and acylindrical actions.
Develops a method to construct entire minimal graphs of odd dimensions.
problem Constructing entire minimal graphs of odd dimensions and arbitrary codimensions.
method Evolving-plane ansatz reducing minimal surface system to geodesic equation on Grassmannian.
result Yields a rich family of explicit entire minimal graphs of odd dimension and arbitrary codimension.
Study the geometry of graph product extension graphs.
problem Properties of graph products.
method Introduce and study the extension graph of graph products of groups.
result Extension graph is isomorphic to crossing graph of a quasi-median graph and exhibits asymptotic dimension similar to quasi-trees.
Kronheimer-Mrowka's instanton homology dimension equals Tait colorings.
problem Calculating the dimension of a specific homology group for plane trivalent graphs.
method Using SO(3) instanton Floer homology, the dimension is shown to be equal to the number of Tait colorings.
result The dimension of J#(G) is equal to the number of Tait colorings of G.
Paper determines Assouad-Nagata dimension for all minor-closed metrics.
problem Understanding the Assouad-Nagata dimension of minor-closed metrics.
method Using edge-weighted graphs and edge-deletion/contraction to model minor-closed metrics, determining their Assouad-Nagata dimension.
result Determined the Assouad-Nagata dimension for every minor-closed metric.
The grand arc graph's asymptotic dimension is shown to be infinite.
problem Determining the asymptotic dimension of the grand arc graph.
method Using Gromov-hyperbolic and cocompact arc and curve models, the asymptotic dimension is shown to be infinite for a broad class of surfaces.
result The asymptotic dimension of the grand arc graph is infinite.
We introduce a new version of a curvature-dimension inequality for non-negative curvature. We use this inequality to prove a logarithmic Li-Yau inequality on finite graphs. To formulate this inequality, we introduce a non-linear variant of the calculus of Bakry and Émery. In the case of manifolds, the new calculus and …
Estimates manifold dimension using local graph structure.
problem Estimating the intrinsic dimension of manifolds from data.
method Regression on local PCA coordinates, focusing on local graph structure.
result Proposed QE and TLS estimators outperform existing methods.
Bernstein theorem proven for 2-valued minimal graphs in 4D.
problem Classifying 2-valued minimal graphs in 4D.
method Analyzing blowdown cones and combinatorial arguments.
result Two-valued minimal graphs in 4D are unions of two 3D planes.
We study ancient solutions of polynomial growth to heat equations on graphs, and extend Colding and Minicozzi's theorem [CM19] on manifolds to graphs: For a graph of polynomial volume growth, the dimension of the space of ancient solutions of polynomial growth is bounded by the product of the growth degree and the dime…
Study extends GNN VC dimension bounds to Pfaffian activation functions.
problem Bounding GNN VC dimension for new activation functions.
method Pfaffian function theory applied to GNNs with sigmoid and hyperbolic tangent activations.
result Bounds on GNN VC dimension for various architectures and graph properties.
New algorithms for clustering and dimension reduction using relative von Neumann entropy.
problem Clustering and dimension reduction for complex data sets.
method Construct graphs from data points, select graph maximizing relative von Neumann entropy, use eigenvectors for dimension reduction.
result Outperforms existing methods on non-trivial data sets.
Random matrix models generalize to Group Field Theories (GFT) whose Feynman graphs are dual to gluings of higher dimensional simplices. It is generally assumed that GFT graphs are always dual to pseudo manifolds. In this paper we prove that already in dimension three (and in all higher dimensions), this is not true due…
Graphs with fat minors have a limited large-scale structure.
problem Understanding the large-scale structure of graphs excluding certain minors.
method Introduced the concept of Baker-treewidth and used it to prove asymptotic dimension bounds.
result Every hereditary class of bounded-degree graphs excluding some graph as a fat minor has asymptotic dimension at most 2.
New topological realization of Kontsevich graph complex for large dimensions.
problem Understanding the rational homotopy groups of Diff partial(D2k).
method Construction of a chain map from Kontsevich graph complex to rational singular chain complex.
result New elements in rational homotopy groups of BDiff partial(D2k) determined by cycles in graph complex.
We prove that the linearly controlled asymptotic dimension of the fundamental group of any 3-dimensional graph-manifold does not exceed 7. As applications we obtain that the universal cover of such a graph-manifold is an absolute Lipschitz retract and it admits a quasisymmetric embedding into the product of 8 metric tr…
We study ancient solutions of polynomial growth to both continuous-time and discrete-time heat equations on graphs with unbounded Laplacians. We generalize Colding and Minicozzi's theorem [CM19] on manifolds, and the result [Hua19] on graphs with normalized Laplacians to the setting of graphs with unbounded Laplacians:…
We study some equivalent properties of the curvature-dimension conditions inequality on infinite, but locally finite graph. These equivalences are gradient estimate, Poincaré type inequalities and reverse Poincaré inequalities. And we also obtain one equivalent property of gradient estimate for a new notion o…
The study finds conditions for compressing the hidden dimension of Graph Transformers for transductive learning.
problem The challenge of efficiently analyzing and training Graph Transformers for transductive learning.
method Theoretical bounds on hidden dimension compression for Graph Transformers, considering both sparse and dense variants.
result Theoretical findings on how and under what conditions the hidden dimension of Graph Transformers can be compressed.
The study finds a subgroup of graph braid groups that is a direct product of non-abelian free groups.
problem Finding subgroups of graph braid groups with specific properties.
method Observing the structure of graph braid groups and their subgroups.
result A subgroup of the same cohomological dimension is a direct product of non-abelian free groups.
Estimating dimension from sparse random geometric graphs.
problem Estimating the dimension of the underlying space from a random geometric graph.
method An estimator of dimension is derived using the adjacency matrix of the graph, under specific conditions on the density and threshold.
result An estimator converges to the true dimension with high probability under certain conditions.
Graph dynamics link combinatorics to geometry, revealing manifold intersections and stability.
problem Understanding the geometry of graph dynamical systems with odd interactions.
method Proved geometry and stability of manifolds governed by graph homology and coverings.
result Derived upper and lower bounds on the dimension of the equilibrium set.
Study of mapping class groups on infinite graphs, focusing on their large-scale geometry.
problem Understanding the large-scale geometry of mapping class groups on infinite graphs.
method Using coarse geometry techniques, classify coarsely bounded groups and compute asymptotic dimension.
result Identify conditions for global and local coarsely bounded pure mapping class groups of infinite rank graphs.
In every dimension we introduce a class of orthogonal graph-manifolds and prove that the fundamental group of any orthogonal graph-manifold quasi-isometrically embeds into a product of trees. As a consequence, we obtain that asymptotic and linearly-controlled asymptotic dimensions of such group are equal t…
Study on teaching complexity in graphs, proving hardness and tractability.
problem Computing the minimum number of examples per concept for teaching.
method Classical and parameterized complexity analysis, NP-hardness, upper and lower bounds, fixed-parameter tractability.
result Nearly complete understanding of teaching complexity in graphs.
We define the class of high dimensional graph manifolds. These are compact smooth manifolds supporting a decomposition into finitely many pieces, each of which is diffeomorphic to the product of a torus with a finite volume hyperbolic manifold with toric cusps. The various pieces are attached together via affine maps o…
Study bandit problem on smooth graph functions for recommender systems.
problem Online learning problems involving graphs, like content-based recommendation.
method Introduced spectral bandit problem and two algorithms that scale linearly in effective dimension.
result Learned user preferences for thousands of items from just tens nodes evaluations.
Automorphisms and subdivisions of Helly graphs are studied, leading to explicit models and rational translation lengths.
problem Understanding automorphisms and subdivisions of Helly graphs.
method Simple fine simplicial subdivisions and explicit simplicial models of the injective hull.
result Any automorphism of a Helly graph is either elliptic or hyperbolic, with rational translation lengths.
It is well-known that a minimal graph of codimension one is stable, i.e. the second variation of the area functional is non-negative. This is no longer true for higher codimensional minimal graphs. In this note, we prove that a minimal graph of any codimension is stable if its normal bundle is flat. We also prove minim…
Graph Signal Processing (GSP) is a promising framework to analyze multi-dimensional neuroimaging datasets, while taking into account both the spatial and functional dependencies between brain signals. In the present work, we apply dimensionality reduction techniques based on graph representations of the brain to decode…
Spectral banditsstat.ML
Bandit problem on graphs aims to recommend items with high expected ratings.
problem Online learning problems involving graphs, such as content-based recommendation.
method Study of a bandit problem on graphs, introducing effective dimension and proposing algorithms.
result Proposed algorithms scale linearly and sublinearly in the effective dimension, improving cumulative regret.
Study shows singular set of certain graphs has codimension 1.
problem Understanding the singular set of specific graph structures.
method Proved using the area stationarity condition.
result Singular set has codimension 1.
Introduces a probabilistic framework for dimension reduction methods.
problem Lack of clear probabilistic foundations for popular DR methods.
method A unifying statistical framework based on the coupling of hidden graphs using cross entropy.
result Existing DR methods suffer from a statistical deficiency that affects performance.