اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDissections, orientations, and trees, with applications to optimal mesh encoding and to random sampling
158
0
0.0
(
0
)
تأليف
Eric Fusy
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We present a bijection between some quadrangular dissections of an hexagon and unrooted binary trees, with interesting consequences for enumeration, mesh compression and graph sampling. Our bijection yields an efficient uniform random sampler for 3-connected planar graphs, which turns out to be determinant for the quadratic complexity of the current best known uniform random sampler for labelled planar graphs [{bf Fusy, Analysis of Algorithms 2005}]. It also provides an encoding for the set $mathcal{P}(n)$ of $n$-edge 3-connected planar graphs that matches the entropy bound $frac1nlog_2|mathcal{P}(n)|=2+o(1)$ bits per edge (bpe). This solves a theoretical problem recently raised in mesh compression, as these graphs abstract the combinatorial part of meshes with spherical topology. We also achieve the {optimal parametric rate} $frac1nlog_2|mathcal{P}(n,i,j)|$ bpe for graphs of $mathcal{P}(n)$ with $i$ vertices and $j$ faces, matching in particular the optimal rate for triangulations. Our encoding relies on a linear time algorithm to compute an orientation associated to the minimal Schnyder wood of a 3-connected planar map. This algorithm is of independent interest, and it is for instance a key ingredient in a recent straight line drawing algorithm for 3-connected planar graphs [bf Bonichon et al., Graph Drawing 2005].
قيم البحث
اقرأ أيضاً
For a collection of papers in memory of Elwyn Berlekamp (1940-2019), John Conway (1937-2020), and Richard Guy (1916-2020). The Sprague-Grundy theory for finite games without cycles was extended to general finite games by Cedric Smith and by Aviezri
Fraenkel and coauthors. We observe that the same framework used to classify finite games also covers the case of locally finite games (that is, games where any position has only finitely many options). In particular, any locally finite game is equivalent to some finite game. We then study cases where the directed graph of a game is chosen randomly, and is given by the tree of a Galton-Watson branching process. Natural families of offspring distributions display a surprisingly wide range of behaviour. The setting shows a nice interplay between ideas from combinatorial game theory and ideas from probability.
We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoffs matrix-tree theorem, is equivalent to determinant of a graph Laplacian minor, or equivalently, of any SDDM matrix. Our ana
lyses utilizes this combinatorial connection to bridge between statistical leverage scores / effective resistances and the analysis of random graphs by [Janson, Combinatorics, Probability and Computing `94]. This leads to a routine that in quadratic time, sparsifies a graph down to about $n^{1.5}$ edges in ways that preserve both the determinant and the distribution of spanning trees (provided the sparsified graph is viewed as a random object). Extending this algorithm to work with Schur complements and approximate Choleksy factorizations leads to algorithms for counting and sampling spanning trees which are nearly optimal for dense graphs. We give an algorithm that computes a $(1 pm delta)$ approximation to the determinant of any SDDM matrix with constant probability in about $n^2 delta^{-2}$ time. This is the first routine for graphs that outperforms general-purpose routines for computing determinants of arbitrary matrices. We also give an algorithm that generates in about $n^2 delta^{-2}$ time a spanning tree of a weighted undirected graph from a distribution with total variation distance of $delta$ from the $w$-uniform distribution .
We extend an observation due to Stong that the distribution of the number of degree $d$ irreducible factors of the characteristic polynomial of a random $n times n$ matrix over a finite field $mathbb{F}_{q}$ converges to the distribution of the numbe
r of length $d$ cycles of a random permutation in $S_{n}$, as $q rightarrow infty$, by having any finitely many choices of $d$, say $d_{1}, dots, d_{r}$. This generalized convergence will be used for the following two applications: the distribution of the cokernel of an $n times n$ Haar-random $mathbb{Z}_{p}$-matrix when $p rightarrow infty$ and a matrix version of Landaus theorem that estimates the number of irreducible factors of a random characteristic polynomial for large $n$ when $q rightarrow infty$.
We study a natural question about sparse random matrices which arises from an application in distributed computing: what is the distance from a fixed vector to the column span of a sparse random matrix $A in R^{n times m}$? We answer this question fo
r several ensembles of sparse random matrices in which the average number of non-zero entries per column, $d$, is smaller than $log(n)$. Key to our analysis is a new characterization of linear dependencies in sparse random matrices. We show that with high probability, in certain random matrices, including rectangular matrices with i.i.d.~Bernoulli entries and $m geq (1 + epsilon)n$, and symmetric random matrices with Bernoulli entries, any linear dependency must be caused by one of three specific combinatorial structures. We show applications of our result to analyzing and designing em gradient codesem, replication schemes used in distributed machine learning to mitigate the effect of slow machines, called em stragglersem. We give the first known construction for a gradient code that achieves near-optimal error for both random and adversarial choices of stragglers.
Efficient automatic protein classification is of central importance in genomic annotation. As an independent way to check the reliability of the classification, we propose a statistical approach to test if two sets of protein domain sequences coming
from two families of the Pfam database are significantly different. We model protein sequences as realizations of Variable Length Markov Chains (VLMC) and we use the context trees as a signature of each protein family. Our approach is based on a Kolmogorov--Smirnov-type goodness-of-fit test proposed by Balding et al. [Limit theorems for sequences of random trees (2008), DOI: 10.1007/s11749-008-0092-z]. The test statistic is a supremum over the space of trees of a function of the two samples; its computation grows, in principle, exponentially fast with the maximal number of nodes of the potential trees. We show how to transform this problem into a max-flow over a related graph which can be solved using a Ford--Fulkerson algorithm in polynomial time on that number. We apply the test to 10 randomly chosen protein domain families from the seed of Pfam-A database (high quality, manually curated families). The test shows that the distributions of context trees coming from different families are significantly different. We emphasize that this is a novel mathematical approach to validate the automatic clustering of sequences in any context. We also study the performance of the test via simulations on Galton--Watson related processes.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
