Proof of the Erdős-Simonovits conjecture on walks

2020/09/22 by Grigoriy Blekherman, Blekherman, Grigoriy, Annie Raymond +1
Computer Science · Mathematics · #05C35 #90C35 #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #semigroups and automata theory

paper · doi:10.48550/arxiv.2009.10845

openalex publication_date 2020/09/22 · openalex created_date 2020/11/09 · openalex updated_date 2026/07/28

Abstract

Let Gⁿ be a graph on n vertices and let w_k(Gⁿ) denote the number of walks of length k in Gⁿ divided by n. Erdős and Simonovits conjectured that w_k(Gⁿ)^t ≥ w_t(Gⁿ)^k when k≥ t and both t and k are odd. We prove this conjecture.

Related

• A random walk proof of the Erdos-Taylor conjecture
• Permutation Inequalities for Walks in Graphs
• A family of partitions of the set of walks on a directed graph
• Counting graphic sequences via integrated random walks
• Pattern Avoiding Permutations as Walks