Motiverade av problemet med routing på ett tillförlitligt och skalbart sätt i en graf, introducerar vi idén om en sclicer, föreningen av spännande träd i en graf. Vi bevisar att för någon begränsad-grad nvertex graf, föreningen av två slumpmässiga spänner träd approximerar expansionen av varje snitt av grafen till inom en faktor av O(log n). För den slumpmässiga grafen G n,p, för p > c log n/n, två spännande träd ger en expander. Detta föreslås av fallet med den fullständiga grafen, där vi bevisar att två slumpmässiga spanning träd ger en expander. Konstruktionen av splitter är elementär -varje spanning träd kan produceras självständigt med hjälp av en algoritm av Aldous och Broder: en slumpmässig promenad i grafen med kanter som leder till tidigare obesökta hörn som ingår i trädet. En andra viktig tillämpning av splittrar är att graf sparsification där målet är att approximera varje snitt (och mer allmänt den kvadratiska formen av Laplacian) med hjälp av endast en liten subgraph av den ursprungliga grafen. Benczur-Karger [5] och Spielman-Srivastava [22] har visat sparifierare med O(n log n/ε 2 ) kanter som uppnår approximation inom faktorerna 1 + ε och 1 − ε. Deras metoder, som grundar sig på oberoende urval av kanter, behöver  på (n log n) kanter för att få någon approximation (eller subgrafen kan kopplas bort) och lämna frågan om linjär storlek sparifierare öppen. Plikrar tar upp denna fråga för slumpmässiga grafer genom att tillhandahålla sparifierare av storlek O(n) som ungefär motsvarar varje snitt inom en faktor av O(log n).
Nyligen REF visar hur man konstruerar en expander/sparsifier med hjälp av slumpmässiga spanning träd.
Expanders via Random Spanning Trees
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}