Random promenader på expander grafer har studerats ingående. Vi definierar en hög ordning kombinatorial slumpmässig promenad på högdimensionella simplial komplex. Denna gång rör sig slumpmässigt mellan angränsande i-dimensionella ansikten (t.ex. kanter) av komplexet, där två i-dimensionella ansikten betraktas som grannar om de delar ett gemensamt (i + 1)-dimensionellt ansikte (t.ex. en triangel). Vi bevisar att om länkarna i komplexet är bra spektralexpanders, då den höga ordningen kombinatorial slumpmässig promenad konvergerar snabbt. Vi härleder vårt resultat om konvergensen av den höga ordningen slumpmässiga vandringen genom att definiera en ny uppfattning om högdimensionell kombinatorisk expansion av ett komplex, som vi kallar färgstark expansion. Vi visar att spektral expansion av länkarna i komplexet innebär färgstark expansion av komplexet, vilket i sin tur innebär snabb konvergens av den höga ordningen slumpmässiga promenad. Vi visar vidare existensen av avgränsade högdimensionella simplial komplex som uppfyller vårt kriterium, och därmed bilda en explicit familj av högdimensionella simplial komplex där den höga ordningen slumpmässiga promenader snabbt konvergerar. Vår högklassiga kombinatoriska slumpmässiga gång är annorlunda än den topologiska topologiska randomvandringen som nyligen har definierats i [PR]. Den topologiska slumpmässiga vandringen är förknippad med koncentrationen av spektrumet av den höga ordningen laplaciern på det utrymme som är ortogonalt för de medbundna, medan vi på sätt och vis behöver argumentera om koncentrationen av spektrumet på det utrymme som är ortogonalt för de konstanta funktionerna, vilket är ett mycket större utrymme.
I ett tidigare verk av författarna till detta verk REF har man studerat hur snabbt konvergensen av den slumpmässiga högklassen går på simpliala komplex av varje dimension.
High Dimensional Combinatorial Random Walks and Colorful Expansion
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}