Asymptotic dimension of intersection graphs

被引：0
|
作者：
Dvorak, Zdenek [1 ]
Norin, Sergey [2 ]
机构：
[1] Charles Univ Prague, Prague, Czech Republic
[2] McGill Univ, Montreal, PQ, Canada
来源：
EUROPEAN JOURNAL OF COMBINATORICS | 2025年 / 123卷
基金：
加拿大自然科学与工程研究理事会;
关键词：
D O I：
10.1016/j.ejc.2022.103631
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that intersection graphs of compact convex sets in R(n )of bounded aspect ratio have asymptotic dimension at most 2n+ 1. More generally, we show this is the case for intersection graphs of systems of subsets of any metric space of Assouad- Nagata dimension n that satisfy the following condition: For each r, s > 0 and every point p, the number of pairwise-disjoint elements of diameter at least s in the system that are at distance at most r from p is bounded by a function of r/s. (c) 2022 Elsevier Ltd. All rights reserved.
引用
收藏
页数：10
相关论文
共 50 条
  • [1] Intersection Dimension of Bipartite Graphs
    Chaplick, Steven
    Hell, Pavol
    Otachi, Yota
    Saitoh, Toshiki
    Uehara, Ryuhei
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014), 2014, 8402 : 323 - 340
  • [2] Grid Intersection Graphs and Order Dimension
    Steven Chaplick
    Stefan Felsner
    Udo Hoffmann
    Veit Wiechert
    Order, 2018, 35 : 363 - 391
  • [3] Grid Intersection Graphs and Order Dimension
    Chaplick, Steven
    Felsner, Stefan
    Hoffmann, Udo
    Wiechert, Veit
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2018, 35 (02): : 363 - 391
  • [4] Ferrers dimension of grid intersection graphs
    Chaplick, Steven
    Hell, Pavol
    Otachi, Yota
    Saitoh, Toshiki
    Uehara, Ryuhei
    DISCRETE APPLIED MATHEMATICS, 2017, 216 : 130 - 135
  • [5] ASYMPTOTIC DIMENSION OF PLANES AND PLANAR GRAPHS
    Fujiwara, Koji
    Papasoglu, Panos
    TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2021, 374 (12) : 8887 - 8901
  • [6] Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs
    Duraj, Lech
    Konieczny, Filip
    Potępa, Krzysztof
    Leibniz International Proceedings in Informatics, LIPIcs, 308
  • [7] Asymptotic behavior of Ext functors for modules of finite complete intersection dimension
    Celikbas, Olgur
    Dao, Hailong
    MATHEMATISCHE ZEITSCHRIFT, 2011, 269 (3-4) : 1005 - 1020
  • [8] Asymptotic behavior of Ext functors for modules of finite complete intersection dimension
    Olgur Celikbas
    Hailong Dao
    Mathematische Zeitschrift, 2011, 269 : 1005 - 1020
  • [9] Asymptotic dimension of graphs of groups and one-relator groups
    Tselekidis, Panagiotis
    ALGEBRAIC AND GEOMETRIC TOPOLOGY, 2023, 23 (08): : 3587 - 3613
  • [10] The Asymptotic Normality of the Global Clustering Coefficient in Sparse Random Intersection Graphs
    Bloznelis, Mindaugas
    Jaworski, Jerzy
    ALGORITHMS AND MODELS FOR THE WEB GRAPH (WAW 2018), 2018, 10836 : 16 - 29
12345