نحن نصف نظاماً جديداً، لعبة الحصى $(k,\\ell)$ مع الألوان، ونستخدمه للحصول على تحليل لعائلة الأرشفة $(k,\\ell)$ وحلول خوارزمية لعائلة المشاكل المتعلقة بتجزئة الأشجار للأرشفة. الأرشفة النادرة تظهر في نظرية الصلابة ولقد تلقت اهتماماً متزايداً في السنوات الأخيرة. بالخصوص، حصولنا على الحصول على الألوان المتطورة والتي تعزز النتائج السابقة للي وسترينو وتعطي دليلاً جديداً لتحليل توتي-ناش ويليامز للأربورسيتي. كما نقدم تجزئة جديدة تؤكد النادرية بناء على لعبة الحصول $(k,\\ell)$ مع الألوان. أيضاً، عملنا يكشف العلاقات بين خوارزميات لعبة الحصول والخوارزميات السابقة لغابو وغابو ووسترمان وهندريكسون.
We describe a new algorithm, the $(k,\\ell)$-pebble game with colors, and use\nit obtain a characterization of the family of $(k,\\ell)$-sparse graphs and\nalgorithmic solutions to a family of problems concerning tree decompositions of\ngraphs. Special instances of sparse graphs appear in rigidity theory and have\nreceived increased attention in recent years. In particular, our colored\npebbles generalize and strengthen the previous results of Lee and Streinu and\ngive a new proof of the Tutte-Nash-Williams characterization of arboricity. We\nalso present a new decomposition that certifies sparsity based on the\n$(k,\\ell)$-pebble game with colors. Our work also exposes connections between\npebble game algorithms and previous sparse graph algorithms by Gabow, Gabow and\nWestermann and Hendrickson.\n
We describe a new algorithm, the $(k,ell)$-pebble game with colors, and use it obtain a characterization of the family of $(k,ell)$-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special inst
A hypergraph G with n vertices and m hyperedges with d endpoints each is (k,l)-sparse if for all sub-hypergraphs G on n vertices and m edges, mle kn-l. For integers k and l satisfying 0le lle dk-1, this is known to be a linearly representable matroid
We present a performant and rigorous algorithm for certifying that a matrix is close to being a projection onto an irreducible subspace of a given group representation. This addresses a problem arising when one seeks solutions to semi-definite progra
For a graph whose vertex set is a finite set of points in $mathbb R^d$, consider the closed (open) balls with diameters induced by its edges. The graph is called a (an open) Tverberg graph if these closed (open) balls intersect. Using the idea of hal
It is well known that every positive integer can be expressed as a sum of nonconsecutive Fibonacci numbers provided the Fibonacci numbers satisfy $F_n =F_{n-1}+F_{n-2}$ for $ngeq 3$, $F_1 =1$ and $F_2 =2$. In this paper, for any $n,minmathbb{N}$ we c