Maximizing Alternating Paths via Entropy

Hao Chen, Felix Christian Clemen, Jonathan A. Noel · 2025

Read Maximizing Alternating Paths via Entropy by Hao Chen, Felix Christian Clemen, Jonathan A. Noel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-03903.txt.

Introduction

Hao Chen, Felix Christian Clemen, and Jonathan Noel counted alternating walks in two-colored graphs in 2025. Color a graph's edges red and blue, and count walks that switch color at each step. A recent problem asked for the most such walks a graph on a fixed number of vertices can hold.

They give a sharp upper bound for walks of a set length with one more red edge than blue. The bound matches the posed problem and settles it. The proof runs through the entropy method, a counting tool from information theory. Their formula gives the exact growth rate in the number of vertices for each fixed walk length.

Catalog record

CREATORHao Chen, Felix Christian Clemen, Jonathan A. Noel
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-03903

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Maximizing Alternating Paths via Entropy Hao Chen, Felix Christian Clemen, Jonathan A. Noel Abstract We prove that if G G is an n n -vertex graph whose edges are coloured with red and blue, then the number of colour-alternating walks of length 2 ​ k + 1 2k+1 with k + 1 k+1 red edges and k k blue edges is at most k k ​ ( k + 1 ) k + 1 ​ ( 2 ​ k + 1 ) − 2 ​ k − 1 ​ n 2 ​ k + 2 k^{k}(k+1)^{k+1}(2k+1)^{-2k-1}n^{2k+2} . This solves a problem that was recently posed by Basit, Granet, Horsley, Kündgen and Staden. Our proof involves an application of the entropy method. 1 Introduction Let H be a finite simple undirected graph whose edges are coloured with two colours, say red and blue; we refer to such a structure as an edge-coloured graph and note that, in this paper, we always deal with edge-colourings using only red and blue unless stated otherwise. A natural extremal problem, raised recently by Basit et al. [ 2 ] and known as the semi-inducibility problem , asks for the maximum possible number of copies of an edge-colored graph H in an edge-coloured graph G on n vertices. In addition to defining the problem and solving it for several small examples and infinite families of edge-coloured graphs, the authors of [ 2 ] raised some intriguing problems regarding edge-coloured paths and cycles. For k\geq 1 , the alternating path P_{k}^{A} is the edge-coloured graph consisting of a path with k+1 vertices v_{0},v_{1},\dots,v_{k} where pairs of consecutive vertices are adjacent, every vertex is incident to at most one edge of each colour and the first edge v_{0}v_{1} is red. The semi-inducibility problem for alternating paths of even length was solved in [ 2 , Theorem 1.3] ; see Theorem 1.1 below. Our main result (Theorem 1.2 ) settles the case of odd alternating paths; in particular, we solve [ 2 , Problem 9.2] . Before stating these theorems, we require a few definitions. For two edge-coloured graphs H and G , a homomorphism from H to G is a mapping \varphi:V(H)\to V(G) with the property that, for every edge uv of H , f(u)f(v) is an edge of G of the same colour as uv . We let \Hom(H,G) denote the set of all such homomorphisms and \hom(H,G) be |\Hom(H,G)| . The homomorphism density of H in G is then defined to be t(H,G):=\frac{\hom(H,G)}{v(G)^{v(H)}} where v(F) denotes the number of vertices of an edge-coloured graph F . In other words, t(H,G) is the probability that a uniformly random map from V(H) to V(G) is a homomorphism. The result of [ 2 ] on alternating paths of even length can be phrased as follows. Theorem 1.1 (Basit et al. [ 2 , Theorem 1.3] ) . For every k\geq 1 and edge-coloured graph G , t(P_{2k}^{A},G)\leq(1/2)^{2k}. Theorem 1.1 can be seen to be asymptotically tight by letting G be an n -vertex edge-coloured graphs in which every vertex is incident to approximately n/2 edges of each colour. We determine the semi-inducibility of odd alternating paths. Theorem 1.2 . For every k\geq 1 and edge-coloured graph G , t(P_{2k+1}^{A},G)\leq k^{k}(k+1)^{k+1}(2k+1)^{-2k-1}. Theorem 1.2 can be seen to be asympotically tight by taking G to be an edge-coloured graph on n vertices in which every vertex is incident to approximately \frac{k+1}{2k+1}n red edges and approximately \frac{k}{2k+1}n blue edges. While the semi-inducibility problem was originally phrased in [ 2 ] in terms of “copies” of H in G as opposed to homomorphisms from H to G , it is not hard to see that these two formulations are roughly equivalent (up to a constant factor and lower order asymptotic terms). We focus on homomorphisms here as we find them more convenient to deal with (e.g. it is useful that homomorphisms need not be injective, and that counting them does not require accounting for the number of “symmetries” of H ). In the next section, we provide an informal sketch of some of the key ideas of the proof, focusing mainly on the example of the 3-edge and 5-edge alternating paths. We also reduce Theorem 1.2 to proving a particular lemma about a special forest which we call H_{2k+1} . In Section 3 , we review the basics of the entropy method and use it to prove a lemma that allows us, under certain conditions, to relate the homomorphism density of P_{2k+1}^{A} to that of an edge-coloured forest H . Then, in Section 4 , we provide the rather technical construction of H_{2k+1} , show that it satisfies the condition of the lemma from the previous section, and bound its homomorphism density from above in terms of P_{2k+1}^{A} to complete the proof. Some of the calculations related to this technical construction are included in an appendix. We then close the paper in Section 5 with some concluding remarks and ruminations about possible directions for future work. Remark 1.3 . We have learned that Balogh, Lidický, Mubayi and Pfender (personal communication) were working on problems related to semi-inducibility simultaneously to us and have obtained some related results. 2 Proof Sketch and Warm-Up A key idea in our proof of Theorem 1.2 is to construct a forest H_{2k+1} such that the homomorphism density of H_{2k+1} can be bounded from below and above in terms of the homomorphism density of P_{2k+1}^{A} , as described by the next lemma. For an edge-coloured graph F , we let e_{R}(F) and e_{B}(F) denote the number of red or blue edges of F , respectively, and e(F)=e_{R}(F)+e_{B}(F) . Lemma 2.1 . For each k\geq 1 , there exists an edge-coloured forest H_{2k+1} with more edges than P_{2k+1}^{A} such that k\cdot e_{R}(H_{2k+1})=(k+1)\cdot e_{B}(H_{2k+1}) and every edge-coloured graph G satisfies t(P_{2k+1}^{A},G)^{1/e(P_{2k+1}^{A})}\leq t(H_{2k+1},G)^{1/e(H_{2k+1})} (2.2) and t(H_{2k+1},G)\leq\left(k^{\frac{k}{2k+1}}(k+1)^{\frac{k+1}{2k+1}}(2k+1)^{-1}\right)^{e(H_{2k+1})-e(P_{2k+1}^{A})}t(P_{2k+1}^{A},G). (2.3) Note that, while many of the bounds in this paper are only tight when G is an edge-coloured clique, it is interesting that ( 2.2 ) is tight for a much wider class of edge-coloured graphs. To see this, suppose that p and q are positive reals such that p+q\leq 1 and let G be any edge-coloured graph on n vertices in which every vertex is incident to about pn red edges and about qn blue edges. Since P_{2k+1}^{A} and H_{2k+1} are both forests, we get t(P_{2k+1}^{A},G)\approx p^{k+1}q^{k} and t(H_{2k+1},G)\approx p^{e_{R}(H_{2k+1})}q^{e_{B}(H_{2k+1})}=p^{\frac{k+1}{2k+1}e(H_{2k+1})}q^{\frac{k}{2k+1}e(H_{2k+1})}=t(P_{2k+1}^{A},G)^{\frac{e(H_{2k+1})}{e(P_{2k+1}^{A})}}. and so ( 2.2 ) is tight for any such G . Let us demonstrate that Theorem 1.2 follows easily from Lemma 2.1 , after which we will turn to sketching the proof of the lemma itself. Proof of Theorem 1.2 . Let G be an edge-coloured graph. By Lemma 2.1 , we have \displaystyle t(P_{2k+1}^{A},G)^{e(H_{2k+1})} \displaystyle\leq t(H_{2k+1},G)^{e(P_{2k+1}^{A})} \displaystyle\leq\left(k^{\frac{k}{2k+1}}(k+1)^{\frac{k+1}{2k+1}}(2k+1)^{-1}\right)^{e(P_{2k+1}^{A})\left(e(H_{2k+1})-e(P_{2k+1}^{A})\right)}t(P_{2k+1}^{A},G)^{e(P_{2k+1}^{A})}. The result now follows from a bit of algebra and the fact that e(H_{2k+1})>e(P_{2k+1}^{A}) . ∎ A key aspect of H_{2k+1} is that it is constructed by starting with P_{2k+1}^{A} and adding pendant edges, short pendant paths, disjoint edges and disjoint vertices in such a way that \hom(H_{2k+1},G) can be easily bounded above in terms of \hom(P_{2k+1}^{A},G) by analyzing local quantities, such as the degree sequence. Let us take a look at the construction in the

Read the complete text