Invariant Gaussian processes and independent sets on regular graphs of large girth

Endre, Csóka [Csóka, Endre (matematika), szerző] Csoportok és gráfok - Lendület (HRN RAMKI); Lendület Struktúrák Limeszei Kutatócsoport (HRN RAMKI); Balázs, Gerencsér [Gerencsér, Balázs (Valószínűségszámí...), szerző] Valószínűségszámítás és Statisztika (HRN RAMKI); Viktor, Harangi [Harangi, Viktor (gráflimeszek), szerző] Diszkrét Matematika (RAMKI); Bálint, Virág [Virág, Bálint (Algebra), szerző] MTA Rényi Alfréd Matematikai Kutatóintézet

Angol nyelvű Szakcikk (Folyóiratcikk) Tudományos
Megjelent: RANDOM STRUCTURES & ALGORITHMS 1042-9832 1098-2418 47 (2) pp. 284-303 2015
  • SJR Scopus - Computer Graphics and Computer-Aided Design: D1
Azonosítók
Szakterületek:
  • Diszkrét matematika és kombinatorika
  • Elméleti és alkalmazott matematika
  • Matematika
  • Számítás- és információtudomány
  • Tudományos alkalmazott matematika
We prove that every 3-regular, n-vertex simple graph with sufficiently large girth contains an independent set of size at least 0.4361n. (The best known bound is 0.4352n.) In fact, computer simulation suggests that the bound our method provides is about 0.438n. Our method uses invariant Gaussian processes on the d-regular tree that satisfy the eigenvector equation at each vertex for a certain eigenvalue λ. We show that such processes can be approximated by i.i.d. factors provided that |λ|≤2d-1. We then use these approximations for λ=-2d-1 to produce factor of i.i.d. independent sets on regular trees. © 2014 Wiley Periodicals, Inc.
Idézők (50)
Hivatkozás stílusok: IEEEACMAPAChicagoHarvardCSLMásolásNyomtatás
2026-04-16 00:26