اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRandomized construction of complexes with large diameter
58
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider the question of the largest possible combinatorial diameter among $(d-1)$-dimensional simplicial complexes on $n$ vertices, denoted $H_s(n, d)$. Using a probabilistic construction we give a new lower bound on $H_s(n, d)$ that is within an $O(d^2)$ factor of the upper bound. This improves on the previously best-known lower bound which was within a factor of $e^{Theta(d)}$ of the upper bound. We also make a similar improvement in the case of pseudomanifolds.
قيم البحث
اقرأ أيضاً
Gyarfas conjectured in 2011 that every $r$-edge-colored $K_n$ contains a monochromatic component of bounded (perhaps three) diameter on at least $n/(r-1)$ vertices. Letzter proved this conjecture with diameter four. In this note we improve the re
sult in the case of $r=3$: We show that in every $3$-edge-coloring of $K_n$ either there is a monochromatic component of diameter at most three on at least $n/2$ vertices or every color class is spanning and has diameter at most four.
We show that the size of the largest simple d-cycle in a simplicial d-complex $K$ is at least a square root of $K$s density. This generalizes a well-known classical result of ErdH{o}s and Gallai cite{EG59} for graphs. We use methods from matroid theory applied to combinatorial simplicial complexes.
Let $X$ be a simplicial complex on $n$ vertices without missing faces of dimension larger than $d$. Let $L_{j}$ denote the $j$-Laplacian acting on real $j$-cochains of $X$ and let $mu_{j}(X)$ denote its minimal eigenvalue. We study the connection bet
ween the spectral gaps $mu_{k}(X)$ for $kgeq d$ and $mu_{d-1}(X)$. In particular, we establish the following vanishing result: If $mu_{d-1}(X)>(1-binom{k+1}{d}^{-1})n$, then $tilde{H}^{j}(X;mathbb{R})=0$ for all $d-1leq j leq k$. As an application we prove a fractional extension of a Hall-type theorem of Holmsen, Martinez-Sandoval and Montejano for general position sets in matroids.
Sombor index is a novel topological index introduced by Gutman, defined as $SO(G)=sumlimits_{uvin E(G)}sqrt{d_{u}^{2}+d_{v}^{2}}$, where $d_{u}$ denotes the degree of vertex $u$. Recently, Chen et al. [H. Chen, W. Li, J. Wang, Extremal values on the
Sombor index of trees, MATCH Commun. Math. Comput. Chem. 87 (2022), in press] considered the Sombor indices of trees with given diameter. For the continue, we determine the maximum Sombor indices for unicyclic graphs with given diameter.
We study the realizability of simplicial complexes with a given pair of integer sequences, representing the node degree distribution and facet size distribution, respectively. While the $s$-uniform variant of the problem is $mathsf{NP}$-complete when
$s geq 3$, we identify two populations of input sequences, most of which can be solved in polynomial time using a recursive algorithm that we contribute. Combining with a sampler for the simplicial configuration model [Young $textit{et al.}$, Phys. Rev. E $textbf{96}$, 032312 (2017)], we facilitate efficient sampling of simplicial ensembles from arbitrary degree and size distributions. We find that, contrary to expectations based on dyadic networks, increasing nodes degrees reduces the number of loops in simplicial complexes. Our work unveils a fundamental constraint on the degree-size sequences and sheds light on further analysis of higher-order phenomena based on local structures.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
