Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSparsity-certifying Graph Decompositions
تقسيمات شبكة تضمين البطء
464
0
0.0
(
0
)
Added by
Louis Theran
Publication date
2007
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
نحن نصف الخوارزمية الجديدة، لعبة الحصى $(k,ell)$ مع الألوان، واستخدامها للحصول على تشخيص لعائلة الشبكات $(k,ell)$ الناعمة والحلول الخوارزمية لعائلة مشاكل تتعلق بتقسيمات الأشجار للشبكات. الشبكات الناعمة الخاصة تظهر في نظرية الثبات ولقد تلقت اهتماما متزايدا في السنوات الأخيرة. بشكل خاص، تجاربنا الحصوى الملونة تعمق وتقوي النتائج السابقة للي وسترينو وتعطي دليلا جديدا على تشخيص توتي - ناش ويليامز للأربوريسيتي. كما نقدم تقسيما جديدا الذي يؤكد الناعمة على أساس لعبة الحصوى $(k,ell)$ مع الألوان. أيضا، عملنا يكشف الصلة بين خوارزميات لعبة الحصوى والخوارزميات السابقة لغابو وغابو ووسترمان وهندريكسون.
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 instances of sparse graphs appear in rigidity theory and have received increased attention in recent years. In particular, our colored pebbles generalize and strengthen the previous results of Lee and Streinu and give a new proof of the Tutte-Nash-Williams characterization of arboricity. We also present a new decomposition that certifies sparsity based on the $(k,ell)$-pebble game with colors. Our work also exposes connections between pebble game algorithms and previous sparse graph algorithms by Gabow, Gabow and Westermann and Hendrickson.
rate research
Read More
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. Spe
cial 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
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 matroidal family. Motivated by problems in rigidity theory, we give a new linear representation theorem for the (k,l)-sparse hypergraphs that is natural; i.e., the representing matrix captures the vertex-edge incidence structure of the underlying hypergraph G.
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 programs (SDPs) with a group symmetry. Indeed, in this context, the dimension of the SDP can be significantly reduced if the irreducible representations of the group action are explicitly known. Rigorous numerical algorithms for decomposing a given group representation into irreps are known, but fairly expensive. To avoid this performance problem, existing software packages -- e.g. RepLAB, which motivated the present work -- use randomized heuristics. While these seem to work well in practice, the problem of to which extent the results can be trusted arises. Here, we provide rigorous guarantees applicable to finite and compact groups, as well as a software implementation that can interface with RepLAB. Under natural assumptions, a commonly used previous method due to Babai and Friedl runs in time O(n^5) for n-dimensional representations. In our approach, the complexity of running both the heuristic decomposition and the certification step is O(max{n^3 log n, D d^2 log d}), where d is the maximum dimension of an irreducible subrepresentation, and D is the time required to multiply elements of the group. A reference implementation interfacing with RepLAB is provided.
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 halving lines, we show that (i) for any finite set of points in the plane, there exists a Hamiltonian cycle that is a Tverberg graph; (ii) for any $n$ red and $n$ blue points in the plane, there exists a perfect red-blue matching that is a Tverberg graph. Using the idea of infinite descent, we prove that (iii) for any even set of points in $mathbb R^d$, there exists a perfect matching that is an open Tverberg graph; (iv) for any $n$ red and $n$ blue points in $ mathbb R^d $, there exists a perfect red-blue matching that is a Tverberg graph.
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 create a sequence called the $(n,m)$-bin sequence with which we can define a notion of a legal decomposition for every positive integer. These sequences are not always positive linear recurrences, which have been studied in the literature, yet we prove, that like positive linear recurrences, these decompositions exist and are unique. Moreover, our main result proves that the distribution of the number of summands used in the $(n,m)$-bin legal decompositions displays Gaussian behavior.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
