A General Inequality for Walks in Graphs

arXiv:2609.11846 · math.CO · Submitted 2026-09-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "A General Inequality for Walks in Graphs".

Title and authors: Ada: So we're looking at this paper today titled "A General Inequality for Walks in Graphs". It’s by Chase Wilson and it looks like they are trying to find a simple rule—a necessary and sufficient condition—on these walk counts.

Emmy: Exactly. The core idea is to take sequences of numbers, say a and b, which represent the number of walks of certain lengths, and figure out when the product inequality holds for any graph G.

Ada: It’s about finding that condition on those sequences, but it seems they are connecting walk counts to something called majorization with parity.

Kolya: So, what does this mean in practice? Does it give us a shortcut to figuring out if an inequality is true without checking every single graph?

Ada: That's the point. The paper suggests that if those sequences a majorize b with a specific parity rule, then the inequality for walk counts will always hold for any graph G.

Emmy: It’s about establishing a direct link between this ordering of numbers and the existence of walks in graphs.

Ada: And it seems they are building on older results, like what Blakely and Roy showed in one thousand nine hundred sixty-five but they've made their proof much shorter and purely combinatorial <ref:2609.11846#pg1>.

The paper's summary: Emmy: The paper lays out the main idea of "A General Inequality for Walks in Graphs" by showing that this inequality is true if and only if those sequences a majorize b with parity. It's a very concise description of when the walk counts will satisfy the required relationship across all graphs.

Ada: It summarizes how they derive this result, starting with some generating inequalities and then using entropy techniques to get to the final condition involving majorization.

Kolya: From a probabilistic standpoint, what does that majorization with parity actually imply about the distribution of walks on a graph? Is it constraining the walk structure in a way we can use for bounding?

Emmy: It suggests that this majorization captures the structural constraints on graphs necessary to maintain that specific product inequality for all possible graphs.

Ada: The paper focuses heavily on deriving this from a generating set of inequalities, which is then translated into the language of symmetric matrices using rational approximation, which is important because it lets us use tools from linear algebra.

Kolya: So, if we are looking at a walk distribution, does this majorization condition tell us about the "tail" behavior or just the overall structure?

Emmy: It seems to be about the precise structure that allows you to move from those initial inequalities into this very simple check using majorization.

The paper's improvements: Ada: The authors suggest a few improvements, mostly focusing on making the result more accessible and perhaps handling some tricky cases better. They introduce Lemma three point one, which gives a condition for when the inequality holds in specific scenarios involving odd or even numbers <ref:2609.11846#pg1>.

Kolya: That lemma seems like it’s trying to handle situations where one of the sequences, say b, is odd, and they are checking if the elements of a have a certain parity relative to b. Is that a generalization or just a specific case?

Emmy: It's actually proving the "if" direction in Theorem one for the special case where all the b values are equal <ref:2609.11846#pg1>. They show that if b is odd and all the corresponding a i are even whenever they are smaller than b, then it works.

Ada: The paper also spends time constructing a counterexample when majorization with parity fails, showing that for certain sequences, you can build a graph G where the inequality actually goes the other way.

Kolya: So, what does this counterexample construction tell us about the limits of this rule? It shows exactly how much freedom we have in choosing graphs before the inequality breaks down.

Emmy: They construct a graph G using parameters M, and they show that for a large enough M, the walk count product drops below the required bound, which is quite concrete for understanding where the condition fails.

Conclusion: Ada: To wrap things up on "A General Inequality for Walks in Graphs", it boils down to this: we have a simple necessary and sufficient condition—majorization with parity—that tells us whether that product inequality holds universally across all graphs.

Emmy: It means if you have those sequences a and b, checking that majorization condition is the only way to know if the walk count product will be bigger than or equal to the other one for any graph G.

Kolya: I just want to add that this whole framework, relying on rational approximation and majorization, gives us a clear operational check. It moves us from potentially checking infinite graphs to checking a finite condition on those sequences.

Ada: Right. And the authors pointed out that they can use this approach even for multigraphs as well as simple graphs by translating it into the language of symmetric matrices using rational approximation, which is a handy tool for AI systems to process.

Emmy: So, we have established a very clear rule based on majorization with parity to govern walk counts in graphs. It provides a strong structural constraint on how walks can behave across the entire class of graphs.

University of California, San Diego

math.CO

Submitted: 2026-09-10

Updated: 2026-11-17

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 74/100

The gist: Let G be a graph and wk(G) denote the number of walks in G of length k, and a simple necessary and sufficient condition on a1, · · ·, an, b1, · · ·…

Key concepts

Majorization with Parity
This mathematical concept compares two vectors, (a1...an) and (b1...bn), to see if the first vector distributes its 'mass' in a way that is at least as large as the second vector. The 'parity' adds an extra constraint related to whether the components are even or odd, which is crucial for determining if the walk inequality holds across all possible graphs.
Walk Count (wk(G))
This refers to the total number of different paths (walks) of a specific length k in a given graph G. The paper uses these counts as variables to test an inequality. Understanding how these counts behave is central to the proof, especially when relating them to matrix properties.
Rational Allocation Strategy
This is a method used in the proof that attempts to find a specific way to distribute resources or allocations between two sets of parameters (a and b). The paper shows that if such an allocation exists, it can be found using this strategy, which helps prove the 'if' part of the main theorem.
Counterexample Construction
When the necessary condition fails, this technique is used to build a specific graph G that serves as a counterexample. This construction involves creating complex structures with parameters like M to show that for large enough M, the product of walk counts will be smaller than expected.

Terminology

Summary

Let G be a graph and wk(G) denote the number of walks in G of length k, and a simple necessary and sufficient condition on a1, · · ·, an, b1, · · ·, bn for the inequality wa1(G)· … wan(G) ≥ wb1(G)· … wbn(G) to hold for any graph G is that (a1, …, an) majorizes (b1, …, bn) with parity

Necessary and Sufficient Condition

The inequality wa1(G)· · · wan(G) ≥ wb1(G)· · · wbn(G) holds for any graph G if and only if (a1, …, an) majorizes (b1, …, bn) with parity Corollary 1.1 states that the inequality holds for any symmetric matrix A with non-negative entries iff (a1, · · ·, an) majorizes (b1, · · ·, bn) with parity. p. 1

Where the paper says it

Let a1, · · · , an, b1, · · · , bn be non-negative integers such that a1 + · · · + an = b1 + · · · + bn. Then Yn i=1 ⟨A ai1, 1⟩ ≥ Yn i=1 ⟨A bi1, 1⟩ holds for any symmetric matrix A with non-negative entries iff (a1, · · · , an) majorizes (b1, · · · , bn) with parity.

Proof Techniques

The proof of the theorem involves several stages, starting with proving a special case using entropy techniques inspired by Raymond and Blekherman [1] in Section 2, then proving the full "if direction by averaging many instances of the special case where b1 = b2 = · · · = bn in Section 4, and finally proving the only if" direction by constructing a graph G in Section 5.

Key Lemmas and Tools

The paper introduces several lemmas to support the main theorem, including Lemma 3.1, which provides a condition for wa1· · · wan ≥ wnb for any graph G when b is odd and ai is even whenever ai < b. p. 2

Where the paper says it

3 A Simpler Inequality In this section we prove the following Lemma which will be used to prove Theorem 1. Let a1, · · · , an, b be integers such that a1 + · · · + an = bn, then wa1 · · · wan ≥ w n b for any graph G if either • b is odd and ai is even whenever ai < b.

Lemma 4.7 shows that the greedy allocation strategy does not abort under certain conditions. p. 9
Where the paper says it

≤ b o i+1 +   β X (i,j) k=1 a o k   +   i+j X−β(i,j) k=1 a e k   ≤   β( X i,j)+1 k=1 a o k   +   i+j X−β(i,j) k=1 a e k   The fact that β ′ (i, j) ≤ β ′ (i, j + 1) follows from a simple induction on i. Suppose that there exists a majorizer β(i, j), then the greedy allocation strategy does not abort.

Furthermore, Lemma 5. p. 2
Where the paper says it

[The Chain Rule] (X1, X2, · · · , Xk) is an S1 × · · · × Sk random variable and H[X1, · · · , Xk] = H[X1] + H[X2|X1] + · · · + H[Xk|X1, · · · , Xk−1]. 3 A Simpler Inequality In this section we prove the following Lemma which will be used to prove Theorem 1.

3 relates the walk count in H to a path in Pb o i0. p. 2
Where the paper says it

In order to use entropy, we aim to show that given a walk W of length b, there exists n walks ρ1, · · · , ρn of length a1, · · · , an that can be arranged into n walks γ1, · · · , γn each of length b such that for all i, γi is either W or the the reverse of W and the start and endpoint of ρi are endpoints of W. v0 v1 v2 v3 A walk of length 2 starting at v0 (red) and a walk of length 4 starting at v3 (blue) arranged into two paths of length 3 (top path and bottom path) Lemma 3.

The Averaging Argument

The main inequality is proven by averaging instances of Lemma 3.1, which leads to the result that if there exists a rational allocation of a onto b, then wa1· · · wan ≥ wb1· · · wbn. p. 5

Where the paper says it

The notion of a rational allocation is exactly what we need to be able to average instances of Lemma 3. If a1, · · · , an, b1, · · · , bn are non-negative integers and there exists a rational allocation of a1, · · · , an onto b1, · · · , bn, then wa1 , · · · wan ≥ wb1 · · · wbn .

This relies on Lemma 4. p. 2
Where the paper says it

[The Chain Rule] (X1, X2, · · · , Xk) is an S1 × · · · × Sk random variable and H[X1, · · · , Xk] = H[X1] + H[X2|X1] + · · · + H[Xk|X1, · · · , Xk−1]. 3 A Simpler Inequality In this section we prove the following Lemma which will be used to prove Theorem 1.

2, which states that if an allocation exists, a rational one exists. p. 5
Where the paper says it

And a rational allocation exists iff A ∩ Qn intersects R. If A intersects R in exactly one position, then that position lies in Qn since R is determined by rational inequalities.

The construction of the rational allocation involves a greedy strategy for allocating onto even components of b and then onto odd components of b. p. 5
Where the paper says it

1 we are only allowed to use a e to allocate onto b e . We do this with the greedy allocation strategy where we process the components of b e one by one and attempt to allocate onto them parts of a e as close together as possible.

Construction for the Only Direction

When (a1, · · ·, an) does not majorize (b1, · · ·, bn) with parity, a graph G is constructed using a parameter M such that for sufficiently large M, wa1(G)· … wan(G) < wb1(G)· … wbn(G). This construction involves two components H and K, where H is constructed with specific complete bipartite graphs, and K is a regular graph on M3+A′ε vertices. The final inequality in this case is derived by showing that the resulting walk count is bounded by a term involving M3n+(1−ε)S+(n−i0−j0)A′ε+Pi0+j0k=1 b o k+Pj0k=1 b e k. p. 1

Where the paper says it

We also note that translating from a generating to set of inequalities to our consise description is non-trivial. Indeed, our approach also starts by giving a (different) list of generating inequalities but the bulk of this paper is spent showing that it is possible to derive an inequality of the form wa1 · · · wan ≥ wb1 · · · wbn from our generating set of inequalities precisely when a1, · · · , an majorizes b1, · · · , bn with parity.

Edge Cases

The construction of G is modified for three edge cases: i0 = 0, bi0 = 1, and when there are less than i0 + j0 elements in a not appearing in a′. These modifications involve changing the number of parts in H or replacing H with an M regular graph, but the computation remains the same as in the general case. p. 0

Where the paper says it

A General Inequality for Walks in Graphs Chase Wilson∗ Abstract Let G be a graph and wk(G) denote the number of walks in G of length k. For sequences a1, · · · , an and b1, · · · , bn of non-negative integers such that a1 + · · · + an = b1 + · · · + bn, we determine a simple necessary and sufficient condition on a1, · · · , an, b1, · · · , bn for the inequality wa1 (G)· · · wan (G) ≥ wb1 (G)· · · wbn (G) to hold for any graph G.

References

[2] George Blakley and Prabir Roy. Hölder type inequality for symmetric matrices with nonnegative entries. p. 1

Where the paper says it

Theorem 1 holds for mult-graphs as well as graphs. By considering the adjacency matrix of G, and using rational approximation we can translate this into the language of symmetric matrices.

Proceedings of the American Mathematical Society, 16:1244-1245, 1965

[3] P. Erd˝os and M. p. 0

Where the paper says it

In 1965, Blakely and Roy [2] proved that wn(G)w0(G) n−1 ≥ w1(G) n for all n ≥ 1. Erd˝os and Simonovits [3] proved that wk(G) t ≥ wt(G) kw0(G) t−k when both k and t are even and k ≥ t.

Simonovits. p. 0
Where the paper says it

In 1965, Blakely and Roy [2] proved that wn(G)w0(G) n−1 ≥ w1(G) n for all n ≥ 1. Erd˝os and Simonovits [3] proved that wk(G) t ≥ wt(G) kw0(G) t−k when both k and t are even and k ≥ t.

Compactness results in extremal graph theory. p. 0
Where the paper says it

Hemecke, Kosub, et al. [4] generalized these two results by proving the so called sandwhich theorem which states w2a+c(G)w2(a+b)+c (G) ≤ w2a(G)w2(a+b+c) (G).

Combinatorica, 2(3):275-283, 1982

[4] R. Hemmecke, S. Kosub, E. mayr, H. T¨aubig, J. Weihmann. Inequalities for the Number of Walks in graphs. p. 0

Where the paper says it

A General Inequality for Walks in Graphs Chase Wilson∗ Abstract Let G be a graph and wk(G) denote the number of walks in G of length k. For sequences a1, · · · , an and b1, · · · , bn of non-negative integers such that a1 + · · · + an = b1 + · · · + bn, we determine a simple necessary and sufficient condition on a1, · · · , an, b1, · · · , bn for the inequality wa1 (G)· · · wan (G) ≥ wb1 (G)· · · wbn (G) to hold for any graph G.

Algorithmica, 66, 804-828, (2013)

[5] A. Dress and I. p. 0

Where the paper says it

Further inequalities of this type have also been studied. Lagarius [6] showed that w2a+b(G)wb(G) ≤ w0(G)w2a+2b(G) Dress and Gutman [5] showed that wa+b(G) 2 ≤ w2a(G)w2b(G).

Gutman. The number of walks in a graph. p. 0
Where the paper says it

A General Inequality for Walks in Graphs Chase Wilson∗ Abstract Let G be a graph and wk(G) denote the number of walks in G of length k. For sequences a1, · · · , an and b1, · · · , bn of non-negative integers such that a1 + · · · + an = b1 + · · · + bn, we determine a simple necessary and sufficient condition on a1, · · · , an, b1, · · · , bn for the inequality wa1 (G)· · · wan (G) ≥ wb1 (G)· · · wbn (G) to hold for any graph G.

Applied Mathematics Letters, 16(5): 797-801, July 2003

[6] J. Lagarias, J. Mazor, L. Shepp, B. McKay. An inequality for walks in a graph. p. 0

Where the paper says it

A General Inequality for Walks in Graphs Chase Wilson∗ Abstract Let G be a graph and wk(G) denote the number of walks in G of length k. For sequences a1, · · · , an and b1, · · · , bn of non-negative integers such that a1 + · · · + an = b1 + · · · + bn, we determine a simple necessary and sufficient condition on a1, · · · , an, b1, · · · , bn for the inequality wa1 (G)· · · wan (G) ≥ wb1 (G)· · · wbn (G) to hold for any graph G.

IAM Review, 25(3):403, July 1983

[7] Blekherman, Grigoriy, and Annie Raymond. ”A Path Forward: Tropicalization in Extremal Combinatorics. p. 2

Where the paper says it

We will start by constructing p = (p0, · · · , p2s) greedily. Conceptually, this means we walk along Pb, backtraking by 1 to cover any qi we can, and then moving forward and finally returning to 0 when we are out of length.

” Advances in Mathematics, vol. p. 0
Where the paper says it

Then the inequality wa1 (G)· · · wan (G) ≥ wb1 (G)· · · wbn (G) holds for any graph G iff (a1, · · · , an) majorizes (b1, · · · , bn) with parity. ∗Department of Mathematics, University of California, San Diego, CA, 92093-0112 USA.

407, 2022, article 108561

[8] Blekherman, Raymond, Proof of the Erd˝os-Simonovits conjecture on walks, Graphs and Combinatorics 39 (3) 53

[9] Hemmecke, Kosub, et al. [4] R. Hemmecke, S. Kosub, E. mayr, H. T¨aubig, J. Weihmann. Inequalities for the Number of Walks in graphs

[10] Lagarias et al., [6] J. Lagarias, J. Mazor, L. Shepp, B. McKay.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved walk counting algorithms for large graphs can be made significantly more efficient by using rational allocation techniques to check if an inequality holds for any graph G, as Theorem 1 provides a simple way to check if wa1(G)· · · wan(G) ≥ wb1(G)· · · wbn(G) holds.

  2. AI systems can be equipped with a mechanism to determine the necessary and sufficient condition for walk inequalities, allowing them to rapidly verify if a proposed inequality is true or false based on the majorization with parity criterion.

  3. The system can utilize entropy techniques, as described in Section 2 and 3, to analyze the distribution of walks in graphs, enabling more nuanced probabilistic modeling of walk counts than traditional methods allow.

  4. AI can perform complex structural analysis on graphs by constructing specific counterexamples when an inequality does not hold, as shown in Section 5 of the paper.

  5. The system can be designed to handle multigraphs effectively by translating graph properties into the language of symmetric matrices and using rational approximations, as suggested by Corollary 1.1.

Abstract

Let G be a graph and w k(G) denote the number of walks in G of length k. For sequences a 1,, a n and b 1,, b n of non-negative integers such that a 1 + + a n = b 1 + + b n, we determine a simple necessary and sufficient condition on a 1,, a n, b 1,, b n for the inequality w a 1(G) w a n(G) at least w b 1(G) w b n(G) to hold for any graph G.

Related papers