Counting cycles and finite dimensional Lp norms

2001/11/09 by Igor Rivin, Rivin, Igor · 3 citations
Mathematics · #05C38 #49N99 #Classical Analysis and ODEs (math.CA) #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Mathematical Approximation and Integration #math.CA #math.CO #msc:05C38 #msc:49N99

paper · pdf · doi:10.48550/arxiv.math/0111106

considerable extension of math.CO/9910093

arxiv created 2001/11/09 · openalex publication_date 2001/11/09 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We obtain sharp bounds for the number of n--cycles in a finite graph as a function of the number of edges, and prove that the complete graph is optimal in more ways than could be imagined. We prove sharp estimates on both the sum of k-th powers of the coordinates and the Lk norm subject to the constraints that the sum of squares of the coordinates is fixed, and that the sum of the coordinates vanishes.

Cited by

• Simulations between Strongly Sublinear MPC and Node-Capacitated Clique
• Creating triangles in Constructor-Blocker games
• Bounded Memory in Distributed Networks

Related

• Simple cycles
• Bounding the number of cycles in a graph in terms of its degree sequence
• The maximum number of cycles in a graph with fixed number of edges
• Improved bound on the number of cycle sets
• On the number of cycles in a graph with restricted cycle lengths