On Tournament Anti-Sidorenko Orientations of Trees
May 13, 2026
Abstract
An oriented graph \(\vec{H}\) is said to be tournament anti-Sidorenko if the homomorphism density of \(\vec{H}\) in any tournament \(\vec{T}\) is bounded above by the homomorphism density of \(\vec{H}\) in a large uniformly random tournament. We prove the following:
(1) Every oriented path with at least three arcs and exactly one non-leaf source or sink vertex is tournament anti-Sidorenko.
(2) An oriented path is tournament anti-Sidorenko if the distance between any leaf vertex and any source or sink vertex is at least two and the distance between any pair of non-leaf source or sink vertices is a multiple of four.
(3) Every spider with exactly three legs admits a tournament anti-Sidorenko orientation.
The first result proves a conjecture posed by He, Mani, Nie, Tung and Wei [1]. The third resolves a problem from the same paper, in fact establishing a substantially more general statement, and provides evidence in support of a conjecture of Fox, Himwich, Mani and Zhou [2]. The second yields the first family of tournament anti-Sidorenko oriented paths which is exponentially large with respect to the number of arcs.
1 Introduction↩︎
A central theme in extremal combinatorics is to identify small “patterns” whose frequency in a large combinatorial object is extremized by a random object of the same type. An archetypal example is Sidorenko’s Conjecture [3]–[6] that, for any bipartite graph \(H\), the homomorphism density of \(H\) in a graph \(G\) with edge density \(p=2|E(G)|/|V(G)|^2\) is at least the expected density in a large binomial random graph of edge density \(p\).
In this paper, we focus on instances of this phenomenon in the setting of tournaments. An oriented graph is a pair \(\vec{H}=(V(\vec{H}),A(\vec{H}))\) where \(V(\vec{H})\) is a set of vertices and \(A(\vec{H})\subseteq V(\vec{H})\times V(\vec{H})\) is a set of arcs containing no self-loops and at most one arc between any pair of distinct vertices. A tournament is an oriented graph in which there is exactly one arc between every pair of distinct vertices. A homomorphism from an oriented graph \(\vec{H}\) to an oriented graph \(\vec{G}\) is a function \(f:V(\vec{H})\to V(\vec{G})\) with the property that \((f(u),f(v))\in A(\vec{G})\) for all \((u,v)\in A(\vec{H})\). We write \(f:\vec{H}\to \vec{G}\) to indicate that \(f\) is a homomorphism from \(\vec{H}\) to \(\vec{G}\). The number of homomorphisms from \(\vec{H}\) to \(\vec{G}\) is denoted \(\hom(\vec{H},\vec{G})\) and the homomorphism density of \(\vec{H}\) in \(\vec{G}\) is \[t(\vec{H},\vec{G}):=\frac{\hom(\vec{H},\vec{G})}{v(\vec{G})^{v(\vec{H})}}\] where \(v(\vec{F}):=|V(\vec{F})|\) for any oriented graph \(\vec{F}\). Inspired by Sidorenko’s Conjecture, there are several recent papers on classifying oriented graphs \(\vec{H}\) such that, among all large tournaments \(\vec{T}\), the quantity \(t(\vec{H},\vec{T})\) is asymptotically maximized or minimized by taking \(\vec{T}\) to be a uniformly random tournament [1], [2], [7]–[17]; see also [18]–[20]. The following definitions make this more precise.
Definition 1. An oriented graph \(\vec{H}\) is tournament anti-Sidorenko if \(t(\vec{H},\vec{T})\leq (1/2)^{a(\vec{H})}\) for every tournament \(\vec{T}\), where \(a(\vec{H}):=|A(\vec{H})|\).
Definition 1. An oriented graph \(\vec{H}\) is tournament Sidorenko if \(t(\vec{H},\vec{T})\geq (1-o(1))(1/2)^{a(\vec{H})}\) for every tournament \(\vec{T}\), where the \(o(1)\) term tends to zero as \(v(\vec{T})\) tends to infinity.
In this paper, we solve several open problems on tournament anti-Sidorenko orientations of paths and spiders. Given an oriented path \(\vec{P}\), a block of \(\vec{P}\) is a maximal subpath of \(\vec{P}\) in which all arcs are oriented in the same direction; see Figure 1. A block of \(\vec{P}\) is internal if it does not contain a leaf of \(\vec{P}\). Sah, Sawhney and Zhao [11] proved that every oriented path with one block (i.e. every directed path) is tournament anti-Sidorenko. He, Mani, Nie, Tung and Wei [1] conjectured that every oriented path with exactly two blocks and at least three arcs is tournament anti-Sidorenko. We prove this.
Theorem 1. Every oriented path with exactly two blocks and at least three arcs is tournament anti-Sidorenko.
We also obtain a general result for paths with an arbitrary number of blocks.
Theorem 1. If \(\vec{P}\) is an oriented path in which every block of \(\vec{P}\) has length at least two and every internal block has length divisible by four, then \(\vec{P}\) is tournament anti-Sidorenko.
To our knowledge, the above theorem provides the first family of tournament anti-Sidorenko oriented paths of exponential size in the number of arcs. He, Mani, Nie, Tung and Wei [1] conjectured that a \(1/2-o(1)\) proportion of all oriented paths with \(k\) arcs are tournament anti-Sidorenko. While we disprove this in a forthcoming paper with Sharfenberg [16], Theorem 1 can be seen as evidence supporting the weaker statement that a positive proportion of all oriented paths with \(k\) arcs are tournament anti-Sidorenko.
An intriguing conjecture of Fox, Himwich, Mani and Zhou [2] is that every undirected tree admits a tournament anti-Sidorenko orientation. It is known to hold for a handful of trees, including paths [11], trees with at most one vertex of even degree [2], and caterpillars [1]. For \(a_1,\dots,a_k\geq1\), define the \((a_1,\dots,a_k)\)-spider, or simply a \(k\)-spider, to be the undirected graph obtained by taking disjoint paths of lengths \(a_1,\dots,a_k\) and identifying all paths on one of their endpoints; see Figure 2. He, Mani, Nie, Tung and Wei [1] identified the \((2,3,4)\)-spider as being an interesting small case for which [2] is open. We not only settle this case, but we obtain tournament anti-Sidorenko orientations of \(3\)-spiders in full generality.5
Theorem 1. Every \(3\)-spider admits a tournament anti-Sidorenko orientation.
1.1 Outline of the Paper↩︎
The proofs of our main results are built up from many auxiliary statements with complex relationships between one another. The purpose of this subsection is to provide a road map for the rest of the paper and to elucidate the main logical dependencies among the results. We use the following convention. The three main results stated in the introduction are referred to as theorems. Results establishing that a particular oriented graph, or each member of a small explicit family of oriented graphs, is tournament Sidorenko or tournament anti-Sidorenko are stated as propositions. General tools and reduction principles are stated as lemmas, and results establishing the existence of specific structures are stated as constructions. The reader can compare, for example, Theorem 1, Proposition 1, Lemma 1 and Construction 1. Table 1 summarizes the propositions and theorems proved in the paper, the sections in which these results are proved, and the results that are used in their proofs.
We now describe the sections in more detail. Section 2 establishes several elementary properties of homomorphism densities in tournaments. These tools are used to establish the tournament Sidorenko and tournament anti-Sidorenko properties for several small examples which are used later. Section 3 uses an algebraic expansion technique, together with estimates for paths in skew-symmetric matrices from [21], to obtain two useful examples of tournament anti-Sidorenko oriented paths and to reduce the proof of Theorem 1 to the case that both blocks have equal length.
After Section 3, the paper shifts to focus on developing and applying an entropy-based approach to the problem of classifying tournament anti-Sidorenko oriented trees. Specifically, in Section 4, we prove Lemma 1 which shows that the existence of a certain type of certificate—which we call an “\(\vec{H}\)-sandwich”—is sufficient for an oriented forest \(\vec{H}\) to be tournament anti-Sidorenko. To illustrate the approach, we provide a sandwich certificate to re-prove the theorem of Sah, Sawhney and Zhao [11] that every directed path is tournament anti-Sidorenko. In Section 5, we construct the sandwich certificates for oriented paths needed to prove Theorem 1. In the same section, we derive Theorem 1 from Theorem 1 and the reduction proved in Section 3. Finally, Section 6 establishes sandwich certificates for an orientation of every \(3\)-spider, except for those which contain a leg of length 1, which is covered by a result of [1], thereby proving Theorem 1. Many of the sandwich certificates in the paper are most easily verified by analyzing a diagram. To make the paper easier to navigate, we collect all of the diagrams for the results in Sections 5 and 6 in Appendix 8.
We conclude the paper in Section 7 by mentioning some related independent work.
2 Basic Tricks↩︎
Throughout the paper, we assume that the vertices of any oriented path with \(k\) arcs are labeled \(v_0,\dots,v_k\), which we view as being arranged from left to right. Given \(\ell_1,\ell_2,\dots,\ell_m\geq1\), let \(\vec{P}_{\ell_1,\dots,\ell_m}\) be the oriented path with \(k=\sum_{i=1}^m\ell_i\) arcs in which, for each \(1\leq i\leq m\), the \(i\)th block has length \(\ell_i\) and the first block is directed from left to right. In particular, \(\vec{P}_k\) is a path with one block of length \(k\). For convenience, we let \(\vec{P}_0\) be the path with only one vertex and \(\vec{P}_{\ell_1,\dots,\ell_m,0,\dots,0}:=\vec{P}_{\ell_1,\dots,\ell_m}\).
The goals of this section are to build up some basic results on homomorphism densities in tournaments which will be used throughout the paper, and to use them to establish Theorem 1 for several small cases—namely \(\vec{P}_{1,2},\vec{P}_{1,3}\) and \(\vec{P}_{1,4}\). At the end of the section, we will also show that \(\vec{P}_{2}\sqcup\vec{P}_{1,1}\) is tournament anti-Sidorenko, a fact which will be useful to us later in the paper.
Given an oriented graph \(\vec{H}\), let \(\reflectbox{\vec{\reflectbox{H}}}\) be the oriented graph obtained from \(\vec{H}\) by reversing the direction of all arcs. The next lemma is quite obvious, but can be useful as it implies that \(\vec{H}\) is tournament anti-Sidorenko if and only if \(\reflectbox{\vec{\reflectbox{H}}}\) is, and so we can freely exchange \(\vec{H}\) and \(\reflectbox{\vec{\reflectbox{H}}}\) whenever it is convenient to do so.
Lemma 1. For any oriented graphs \(\vec{H}\) and \(\vec{G}\), it holds that \(\hom(\vec{H},\vec{G})=\hom(\reflectbox{\vec{\reflectbox{H}}},\reflectbox{\vec{\reflectbox{G}}})\).
Proof. For any function \(\varphi:V(\vec{H})\to V(\vec{G})\) and vertices \(u,v\in V(\vec{H})\), we have that \((u,v)\) is an arc of \(\vec{H}\) if and only if \((v,u)\) is an arc of \(\reflectbox{\vec{\reflectbox{H}}}\) and that \((\varphi(u),\varphi(v))\) is an arc of \(\vec{G}\) if and only if \((\varphi(v),\varphi(u))\) is an arc of \(\reflectbox{\vec{\reflectbox{G}}}\). Therefore, \(\varphi\) is a homomorphism from \(\vec{H}\) to \(\vec{G}\) if and only if it is a homomorphism from \(\reflectbox{\vec{\reflectbox{H}}}\) to \(\reflectbox{\vec{\reflectbox{G}}}\). ◻
The asymmetry between the definition of tournament Sidorenko, which includes a \(o(1)\) term, and tournament anti-Sidorenko, which does not, may seem somewhat awkward. However, as we show next, both notions can be written with a \(o(1)\) term.
Lemma 1. If \(\vec{H}\) is an oriented graph such that \(t(\vec{H},\vec{T})\leq (1+o(1))(1/2)^{a(\vec{H})}\) for every tournament \(\vec{T}\), then \(\vec{H}\) is tournament anti-Sidorenko.
Proof. We prove the contrapositive. Suppose that there is a tournament \(\vec{T}\) and \(\varepsilon>0\) such that \(t(\vec{H},\vec{T})=(1+\varepsilon)(1/2)^{a(\vec{H})}\). For each \(n\geq1\), let \(\vec{T}_n\) be a tournament obtained from \(\vec{T}\) by replacing each vertex \(u\) with a set \(S_u\) of \(n\) vertices and adding all arcs from set \(S_u\) to set \(S_v\) if \((u,v)\in A(\vec{T})\) and adding arcs inside the sets \(S_u\) arbitrarily. Then \(t(\vec{H},\vec{T}_n)\geq t(\vec{H},\vec{T}) = (1+\varepsilon)(1/2)^{a(\vec{H})}\) by construction and \(v(\vec{T}_n)=n\cdot v(\vec{T})\). Therefore, it is not the case that \(t(\vec{H},\vec{T}_n)\leq (1+o(1))(1/2)^{a(\vec{H})}\), and so the proof is complete. ◻
Next, we obtain a useful property of homomorphisms into tournaments.
Lemma 1. Let \(\vec{F}\) be an oriented graph and let \(u\) and \(v\) be distinct vertices of \(\vec{F}\) such that neither of the arcs \((u,v)\) nor \((v,u)\) are present in \(\vec{F}\). Let \(\vec{F}_{u,v}\) and \(\vec{F}_{v,u}\) be the oriented graphs obtained from \(\vec{F}\) by adding the arcs \((u,v)\) and \((v,u)\), respectively. Then, for every tournament \(\vec{T}\), \[\hom(\vec{F},\vec{T}) = \hom(\vec{F}_{u,v},\vec{T})+\hom(\vec{F}_{v,u},\vec{T}) + O\left(v(\vec{T})^{v(\vec{F})-1}\right).\]
Proof. For each homomorphism \(\varphi:\vec{F}\to\vec{T}\) such that \(\varphi(u)\neq \varphi(v)\), exactly one of \((\varphi(u),\varphi(v))\) or \((\varphi(v),\varphi(u))\) must be an arc of \(\vec{T}\), since \(\vec{T}\) is a tournament. Thus, every such homomorphism corresponds to a homomorphism from \(\vec{F}_{u,v}\) or \(\vec{F}_{v,u}\) to \(\vec{T}\), but not both. The number of homomorphisms from \(\vec{F}\) to \(\vec{T}\) which map \(u\) and \(v\) to the same vertex is \(O\left(v(\vec{T})^{v(\vec{F})-1}\right)\), and so the proof is complete. ◻
The next lemma relates the homomorphism density of a disconnected oriented graph to that of its components. Given two oriented graphs \(\vec{H}\) and \(\vec{F}\), we let \(\vec{H}\sqcup \vec{F}\) denote their vertex-disjoint union.
Lemma 1. For any oriented graphs \(\vec{H},\vec{F}\) and \(\vec{G}\), we have \(t(\vec{H}\sqcup \vec{F},\vec{G})=t(\vec{H},\vec{G})t(\vec{F},\vec{G})\).
Proof. A function \(\varphi:V(\vec{H}\sqcup \vec{F})\to V(\vec{G})\) is a homomorphism from \(\vec{H}\sqcup \vec{F}\) to \(\vec{G}\) if and only if its restrictions to \(V(\vec{H})\) and \(V(\vec{F})\) are homomorphisms from \(\vec{H}\) to \(\vec{G}\) and \(\vec{F}\) to \(\vec{G}\), respectively. Therefore, \(\hom(\vec{H}\sqcup \vec{F},\vec{G})=\hom(\vec{H},\vec{G})\hom(\vec{F},\vec{G})\), which implies the result. ◻
The above lemmas are key to building the family of impartial oriented graphs—i.e. oriented graphs that are simultaneously tournament Sidorenko and tournament anti-Sidorenko—characterized by Zhao and Zhou [15]. The smallest non-trivial example is \(\vec{P}_{1,2}\).
Proposition 1 (See Zhao and Zhou [15]). The oriented path \(\vec{P}_{1,2}\) is tournament anti-Sidorenko and tournament Sidorenko.
Proof. Let \(\vec{F}\) be the oriented graph with vertices \(0,1,2\) and \(3\) and arcs \((0,1)\) and \((3,2)\). Let \(\vec{F}_{1,2}\) and \(\vec{F}_{2,1}\) be obtained from \(\vec{F}\) by adding the arcs \((1,2)\) and \((2,1)\), respectively. Observe that both \(\vec{F}_{1,2}\) and \(\vec{F}_{2,1}\) are isomorphic to \(\vec{P}_{1,2}\). Thus, by Lemma 1, every tournament \(\vec{T}\) satisfies \[\hom(\vec{F},\vec{T})=2\hom(\vec{P}_{1,2},\vec{T}) + O\left(v(\vec{T})^{3}\right)\] or, in other words, \[\hom(\vec{P}_{1,2},\vec{T}) = \frac{1}{2}\left(\hom(\vec{F},\vec{T}) -O\left(v(\vec{T})^{3}\right)\right).\] Note that \(\vec{F}\) is isomorphic to \(\vec{P}_1\sqcup\vec{P}_1\). It is easily observed that every tournament \(\vec{T}\) satisfies \(\hom(\vec{P}_1,\vec{T})=\binom{v(\vec{T})}{2}\) and so, by Lemma 1, we have \(\hom(\vec{F},\vec{T})=\binom{v(\vec{T})}{2}^2\). Putting all of this together, we get \((1-o(1))(1/2)^3\leq t(\vec{P}_{1,2},\vec{T})\leq (1/2)^3\) for every tournament \(\vec{T}\) and so the proof is complete. ◻
Next, we show that \(\vec{P}_{1,2,1,1}\) is tournament Sidorenko and use that to get that \(\vec{P}_{1,4}\) is tournament anti-Sidorenko, thereby establishing another case of Theorem 1.
Proposition 1. The oriented path \(\vec{P}_{1,2,1,1}\) is tournament Sidorenko.
Proof. Let \(\vec{F}\) be the oriented graph with vertices \(0,1,2,3,4,5\) and arcs \((0,1),(2,1),(3,4),(5,4)\). Let \(\vec{F}_{2,3}\) and \(\vec{F}_{3,2}\) be obtained from \(\vec{F}\) by adding the arcs \((2,3)\) and \((3,2)\), respectively. Then, clearly, \(\vec{F}\) is isomorphic to \(\vec{P}_{1,1}\sqcup \vec{P}_{1,1}\) and each of \(\vec{F}_{2,3}\) and \(\vec{F}_{3,2}\) is isomorphic to \(\vec{P}_{1,2,1,1}\). So, by Lemmas 1 and 1, we have, for any tournament \(\vec{T}\), \[\hom(\vec{P}_{1,1},\vec{T})^2 = \hom(\vec{F},\vec{T}) = 2\hom(\vec{P}_{1,2,1,1},\vec{T})+O(v(\vec{T})^{5})\] or, in other words, \[t(\vec{P}_{1,2,1,1},\vec{T})=\frac{1}{2}t(\vec{P}_{1,1},\vec{T})^2-o(1).\] It is well-known, and easy to prove, that \(\vec{P}_{1,1}\) is tournament Sidorenko; see, e.g., [15]. Therefore, \[t(\vec{P}_{1,2,1,1},\vec{T}) \geq (1-o(1))(1/2)^5,\] and so \(\vec{P}_{1,2,1,1}\) is tournament Sidorenko. ◻
Proposition 1. The oriented path \(\vec{P}_{1,4}\) is tournament anti-Sidorenko.
Proof. Let \(\vec{F}\) be the oriented forest with vertices \(0,1,2,3,4,5\) with arcs \((0,1),(2,1),(3,2),(5,4)\). Let \(\vec{F}_{3,4}\) and \(\vec{F}_{4,3}\) be obtained from \(\vec{F}\) by adding the arcs \((3,4)\) and \((4,3)\), respectively. Clearly, \(\vec{F}_{3,4}\) is isomorphic to \(\vec{P}_{1,2,1,1}\) and \(\vec{F}_{4,3}\) is isomorphic to \(\vec{P}_{1,4}\). So, by Lemma 1, any tournament \(\vec{T}\) satisfies \[\hom(\vec{P}_{1,4},\vec{T})=\hom(\vec{F},\vec{T})-\hom(\vec{P}_{1,2,1,1},\vec{T})-O(v(\vec{T})^5).\] Clearly, \(\vec{F}\) is isomorphic to \(\vec{P}_{1,2}\sqcup \vec{P}_1\). The result now follows from Lemma 1 and the facts that \(\vec{F}\) is tournament anti-Sidorenko (by Lemma 1 and Proposition 1) and \(\vec{P}_{1,2,1,1}\) is tournament Sidorenko (by Proposition 1). ◻
The next lemma provides a simple construction for generating new examples of tournament anti-Sidorenko graphs from old ones; it is essentially the same as [1]. Let \(\vec{H}\) and \(\vec{F}\) be oriented graphs and let \(u\in V(\vec{H})\) and \(v\in V(\vec{F})\). Let \(\vec{F}_1\) and \(\vec{F}_2\) be two copies of the graph \(\vec{F}\) where, for each \(w\in V(\vec{F})\) and \(i\in\{1,2\}\), we let \(w_i\) be the vertex of \(\vec{F}_i\) corresponding to \(w\). Let \(\vec{H}\pm_{u,v}\vec{F}\) be the graph obtained from \(\vec{H}\sqcup\vec{F}_1\sqcup\vec{F}_2\) by adding the arcs \((u,v_1)\) and \((v_2,u)\). See Figure 3 for a diagram illustrating this construction.
Lemma 1 (He et al. [1]). For any oriented graphs \(\vec{H}\) and \(\vec{F}\), vertices \(u\in V(\vec{H})\) and \(v\in V(\vec{F})\) and tournament \(\vec{T}\), it holds that \[\hom(\vec{H}\pm_{u,v}\vec{F},\vec{T})\leq \frac{1}{4}\hom(\vec{H},\vec{T})\hom(\vec{F},\vec{T})^2.\]
Proof. Given a homomorphism \(\varphi:\vec{H}\to\vec{T}\), let \(\hom_{\varphi,u,v}^+(\vec{F},\vec{T})\) be the number of homomorphisms \(\psi:\vec{F}\to \vec{T}\) such that \((\varphi(u),\psi(v))\in A(\vec{T})\) and let \(\hom_{\varphi,u,v}^-(\vec{F},\vec{T})\) be the number such that \((\psi(v),\varphi(u))\in A(\vec{T})\). Then, clearly, \[\hom_{\varphi,u,v}^+(\vec{F},\vec{T}) + \hom_{\varphi,u,v}^-(\vec{F},\vec{T})\leq \hom(\vec{F},\vec{T})\] and so, by AM-GM, \[\hom_{\varphi,u,v}^+(\vec{F},\vec{T})\hom_{\varphi,u,v}^-(\vec{F},\vec{T})\leq \left(\frac{\hom_{\varphi,u,v}^+(\vec{F},\vec{T}) + \hom_{\varphi,u,v}^-(\vec{F},\vec{T})}{2}\right)^2 \leq \frac{1}{4}\hom(\vec{F},\vec{T})^2.\] Now, by construction, we have \[\hom(\vec{H}\pm_{u,v}\vec{F},\vec{T}) = \sum_{\varphi:\vec{H}\to\vec{T}}\hom_{\varphi,u,v}^+(\vec{F},\vec{T})\hom_{\varphi,u,v}^-(\vec{F},\vec{T})\leq \frac{1}{4}\hom(\vec{H},\vec{T})\hom(\vec{F},\vec{T})^2\] as desired. ◻
As a simple application of the above lemma, we establish Theorem 1 for \(\vec{P}_{1,3}\).
Proposition 1. The oriented path \(\vec{P}_{1,3}\) is tournament anti-Sidorenko.
Proof. Let \(\vec{H}:=\vec{P}_0\) and \(\vec{F}:=\reflectbox{\vec{\reflectbox{P}}}_1\). Then it is easily observed that \(\vec{H}\pm_{0,1}\vec{F}\) is isomorphic to \(\vec{P}_{1,3}\). So, the result follows from Lemma 1 and the fact that \(\vec{P}_0\) and \(\vec{P}_1\) are clearly tournament anti-Sidorenko. ◻
To close this section, let us apply Lemmas 1 and 1 one more time to obtain an example of a tournament anti-Sidorenko forest, namely \(\vec{P}_{2}\sqcup \vec{P}_{1,1}\), which will be useful in Section 5.
Proposition 1. The oriented forest \(\vec{P}_{2}\sqcup \vec{P}_{1,1}\) is tournament anti-Sidorenko.
Proof. Let \(\vec{T}\) be any tournament. Then, by Lemma 1 and the AM-GM Inequality, \[\label{eq:unionForest}\hom(\vec{P}_{2}\sqcup \vec{P}_{1,1},\vec{T})=\hom(\vec{P}_{2},\vec{T})\hom(\vec{P}_{1,1},\vec{T})\leq \left(\frac{\hom(\vec{P}_{2},\vec{T}) + \hom(\vec{P}_{1,1},\vec{T})}{2}\right)^2.\tag{1}\] Let \(\vec{F}\) be the oriented forest consisting of three vertices \(0,1,2\) and one arc \((0,1)\). Let \(\vec{F}_{1,2}\) and \(\vec{F}_{2,1}\) be the oriented graphs obtained from \(\vec{F}\) by adding the arcs \((1,2)\) and \((2,1)\), respectively. Clearly, \(\vec{F}_{1,2}=\vec{P}_2\) and \(\vec{F}_{2,1}=\vec{P}_{1,1}\). By Lemma 1, we have \[\hom(\vec{P}_{2},\vec{T})+\hom(\vec{P}_{1,1},\vec{T}) = \hom(\vec{F},\vec{T}) - O(v(\vec{T})^2).\] Since \(\vec{F}\) is isomorphic to \(\vec{P}_1\sqcup\vec{P}_0\), we have, by Lemma 1, \[\hom(\vec{F},\vec{T})=\binom{v(\vec{T})}{2}v(\vec{T})\leq \frac{1}{2}v(\vec{T})^3.\] By combining the last two inequalities and plugging the result into 1 , we obtain \[\hom(\vec{P}_{2}\sqcup \vec{P}_{1,1},\vec{T}) \leq \left(\frac{v(\vec{T})^3}{4}\right)^2 = (1/2)^4v(\vec{T})^6,\] as desired. For an illustration of the proof, see Figure 4. ◻
3 Reductions of Theorem 1 Via Algebraic Expansion↩︎
The focus of this section is on reducing Theorem 1 to the case that both blocks have the same length. We start with the following standard application of the Cauchy–Schwarz inequality.
Lemma 1. If \(k\geq3\), then every tournament \(\vec{T}\) satisfies \[t(\vec{P}_{1,k},\vec{T})^2\leq t(\vec{P}_{1,3,3,1},\vec{T})t(\vec{P}_{k-3,k-3},\vec{T}).\]
Proof. Let \(\vec{T}\) be a tournament. Given an oriented graph \(\vec{H}\), a vertex \(v\in V(\vec{H})\) and \(u\in V(\vec{T})\), let \(\hom_{v\mapsto u}(\vec{H},\vec{T})\) be the number of homomorphisms \(\varphi:\vec{H}\to\vec{T}\) such that \(\varphi(v)=u\). Then, by the Cauchy–Schwarz Inequality, \[\begin{align} \hom(\vec{P}_{1,k},\vec{T}) &= \sum_{u\in V(\vec{T})}\hom_{v_4\mapsto u}(\vec{P}_{1,3},\vec{T})\cdot \hom_{v_0\mapsto u}(\reflectbox{\vec{\reflectbox{P}}}_{k-3},\vec{T})\\ &\leq\left(\sum_{u\in V(\vec{T})}\hom_{v_4\mapsto u}(\vec{P}_{1,3},\vec{T})^2\right)^{1/2} \left(\sum_{u\in V(\vec{T})}\hom_{v_0\mapsto u}(\reflectbox{\vec{\reflectbox{P}}}_{k-3},\vec{T})^2\right)^{1/2}\\ & = \hom(\vec{P}_{1,3,3,1},\vec{T})^{1/2}\hom(\vec{P}_{k-3,k-3},\vec{T})^{1/2}. \end{align}\] The result now follows by dividing by \(v(\vec{T})^{k+2}\) and squaring both sides. For an illustration of this proof, see Figure 5. ◻
In light of Lemma 1, it is useful to show that \(\vec{P}_{1,3,3,1}\) is tournament anti-Sidorenko. Thus, most of the rest of this section is devoted to proving the following proposition.
Proposition 1. The oriented path \(\vec{P}_{1,3,3,1}\) is tournament anti-Sidorenko.
Our approach to proving Proposition 1 is based on the “algebraic expansion” trick that is commonly used in papers on graph limits. For this, it is convenient to work in terms of matrices as opposed to tournaments.6 Given an \(n\times n\) matrix \(A\) and \(1\leq i,j\leq n\), let \(A(i,j)\) be the entry of \(A\) on the \(i\)th row and \(j\)th column. Given an oriented graph \(\vec{H}\), define \[\label{eq:homHA} \hom(\vec{H},A):=\sum_{f:V(\vec{H})\to [n]}\left( \prod_{(u,v)\in A(\vec{H})} A(f(u),f(v))\right)\tag{2}\] and \(t(\vec{H},A):=\frac{1}{n^{v(\vec{H})}}\hom(\vec{H},A)\). The adjacency matrix of a tournament \(\vec{T}\) with vertices \(u_1,\dots,u_n\) is the \(n\times n\) matrix \(A_{\vec{T}}\) where the entry on the \(i\)th row and \(j\)th column is \(1\) if \((u_i,u_j)\in A(\vec{T})\) and \(0\) otherwise. It is easily observed that \(\hom(\vec{H},\vec{T})=\hom(\vec{H},A_{\vec{T}})\) for any tournament \(\vec{T}\). It will actually be more convenient to deal with an augmented adjacency matrix for \(\vec{T}\) which we define by \[A_{\vec{T}}^*:=A_{\vec{T}}+\frac{1}{2}I_n\] where \(I_n\) is the \(n\times n\) identity matrix. The next observation follows from the fact that all entries of \(A_{\vec{T}}^*\) and \(A_{\vec{T}}\) are non-negative and every entry of \(A_{\vec{T}}^*\) is greater than or equal to the corresponding entry of \(A_{\vec{T}}\).
Observation 1. For every oriented graph \(\vec{H}\) and tournament \(\vec{T}\), \[\hom(\vec{H},\vec{T})\leq \hom(\vec{H},A_{\vec{T}}^*).\]
Given an oriented graph \(\vec{H}\) and a set \(S\subseteq A(\vec{H})\), let \(\vec{H}[S]\) be the oriented graph with vertex set \(V(\vec{H})\) and arc set \(S\). Let \(J_n\) be the \(n\times n\) all-ones matrix. The next lemma provides a useful alternative expression for \(\hom(\vec{H},A)\) for any matrix \(A\).
Lemma 1. Let \(\vec{H}\) be an oriented graph. For any \(n\times n\) matrix \(A\), if \(U=A-\frac{1}{2}J_n\), then \[\hom(\vec{H},A)=\sum_{S\subseteq A(\vec{H})}(1/2)^{a(\vec{H})-|S|}\hom(\vec{H}[S],U).\]
Proof. By 2 , \[\begin{align} \hom(\vec{H},A)&=\sum_{f:V(\vec{H})\to [n]} \left(\prod_{(u,v)\in A(\vec{H})} A(f(u),f(v))\right)=\sum_{f:V(\vec{H})\to [n]} \left(\prod_{(u,v)\in A(\vec{H})} (1/2+ U(f(u),f(v)))\right)\\ &=\sum_{f:V(\vec{H})\to [n]} \left(\sum_{S\subseteq A(\vec{H})}(1/2)^{a(\vec{H})-|S|}\prod_{(u,v)\in S} U(f(u),f(v))\right)\\ &=\sum_{S\subseteq A(\vec{H})}(1/2)^{a(\vec{H})-|S|} \left(\sum_{f:V(\vec{H})\to [n]}\prod_{(u,v)\in S} U(f(u),f(v))\right)\\ &=\sum_{S\subseteq A(\vec{H})}(1/2)^{a(\vec{H})-|S|}\hom(\vec{H}[S],U) \end{align}\] as desired. ◻
Our proof of Proposition 1 involves applying Lemma 1 to \(\vec{H}=\vec{P}_{1,3,3,1}\) and the matrix \(A=A_{\vec{T}}^*\) for a tournament \(\vec{T}\). Given an \(n\)-vertex tournament \(\vec{T}\), the matrix \(U_T:=A_{\vec{T}}^* - \frac{1}{2}J_n\) is skew-symmetric, meaning that \(U^T=-U\), and all entries of \(U\) are between \(-1/2\) and \(1/2\). Thus, we would benefit from knowing properties of \(\hom(\vec{P},U)\) where \(\vec{P}\) is an oriented path and \(U\) is a skew-symmetric matrix with entries in \([-1/2,1/2]\). We borrow several such results from a paper of Grzesik, Il’kovič, Kielak and Král’ [21].
Lemma 1 (Grzesik et al. [21]). Let \(p(x)=\sum_{k=1}^m\alpha_kx^k\) be a polynomial over \(\mathbb{R}\). If \(p(x)\geq 0\) for all \(x\in [0,1/\pi^2]\), then \[\sum_{k=1}^m\alpha_k\cdot t(\vec{P}_{k,k},U)\geq 0\] for every skew-symmetric matrix \(U\) with entries in \([-1/2,1/2]\).
Lemma 1 (Grzesik et al. [21]). Every skew-symmetric matrix \(U\) satisfies \(t(\vec{P}_{1,1},U)^2\leq t(\vec{P}_{2,2},U)\).
Lemma 1 (Grzesik et al. [21]). Every skew-symmetric matrix \(U\) with entries in \([-1/2,1/2]\) satisfies \(0\leq t(\vec{P}_{1,1},U)\leq \frac{1}{12}\).
We will also use the following two standard facts about homomorphism densities into skew-symmetric matrices.
Lemma 1 (Grzesik et al. [21]). Let \(\vec{H}\) and \(\vec{F}\) be two oriented graphs that differ by reversing the orientation of a single arc. Then \(t(\vec{H},U)=-t(\vec{F},U)\) for every skew-symmetric matrix \(U\).
Proof. Let \(x,y\) be the pair of vertices such that \((x,y)\in A(\vec{H})\) and \((y,x)\in A(\vec{F})\). Then \[\begin{align} \hom(\vec{H},U)&=\sum_{f:V(\vec{H})\to [n]}\left( \prod_{(u,v)\in A(\vec{H})} U(f(u),f(v))\right)\\ &=\sum_{f:V(\vec{H})\to [n]}\left(U(f(x),f(y)) \prod_{(u,v)\in A(\vec{H})\setminus\{(x,y)\}} U(f(u),f(v))\right)\\ &=-\sum_{f:V(\vec{H})\to [n]}\left(U(f(y),f(x)) \prod_{(u,v)\in A(\vec{H})\setminus\{(x,y)\}} U(f(u),f(v))\right)\\ &=-\hom(\vec{F},U) \end{align}\] from which the result follows. ◻
Lemma 1 (Grzesik et al. [21]). Let \(\vec{P}\) be an oriented path with an odd number of edges. Then \(t(\vec{P},U)=0\) for every skew-symmetric matrix \(U\).
Proof. Let \(k=2\ell+1\) be the length of \(\vec{P}\). By swapping the directions of arcs of \(\vec{P}\), one by one, and applying Lemma 1 we get that \(t(\vec{P},U)\) is equal to either \(t(\vec{P}_{\ell,\ell+1},U)\) or \(-t(\vec{P}_{\ell,\ell+1},U)\). Also, by swapping the direction of the central arc, we see that \(t(\vec{P}_{\ell,\ell+1},U) = -t(\vec{P}_{\ell+1,\ell},U)\). However, \(\vec{P}_{\ell,\ell+1}\) and \(\vec{P}_{\ell+1,\ell}\) are clearly isomorphic, and so \(t(\vec{P}_{\ell,\ell+1},U) = t(\vec{P}_{\ell+1,\ell},U)\). Thus, we conclude that \(t(\vec{P}_{\ell,\ell+1},U)=0\) and so \(t(\vec{P},U)=0\) as well. ◻
We now present the proof of Proposition 1.
Proof of Proposition 1. Let \(\vec{T}\) be a tournament with \(n\) vertices and let \(U_T:= A_{\vec{T}}^*-\frac{1}{2}J_n\). We start by applying Observation 1 and Lemma 1 and dividing both sides by \(n^9\) to get \[t(\vec{P}_{1,3,3,1},\vec{T}) \leq t(\vec{P}_{1,3,3,1},A_{\vec{T}}^*)=\sum_{S\subseteq A(\vec{P}_{1,3,3,1})}(1/2)^{8-|S|}t(\vec{P}_{1,3,3,1}[S],U_T).\] In the expression on the right side, any term corresponding to a set \(S\) such that \(\vec{P}_{1,3,3,1}[S]\) has a component with an odd number of edges is zero by Lemmas 1 and 1.7 So, using Lemma 1 and 1, we can express every remaining term on the right side as a polynomial in the expressions \(t(\vec{P}_{k,k},U_T)\) for \(k\in \{1,2,3,4\}\). It is equal to \[\label{eq:expansion} \begin{gather} t(\vec{P}_{4,4},U_T) + \frac{3}{4}t(\vec{P}_{3,3},U_T) - \frac{1}{2}t(\vec{P}_{1,1},U_T)t(\vec{P}_{2,2},U_T) + \frac{1}{4}t(\vec{P}_{1,1},U_T)^3-\frac{3}{16}t(\vec{P}_{2,2},U_T)\\ +\frac{1}{8}t(\vec{P}_{1,1},U_T)^2-\frac{1}{64}t(\vec{P}_{1,1},U_T) + \frac{1}{256}. \end{gather}\tag{3}\] We will be done if we can show that the above expression is always bounded above by \(1/256\). To this end, define \[f(U_T):=t(\vec{P}_{4,4},U_T) + \frac{3}{4}t(\vec{P}_{3,3},U_T)-\frac{3}{16}t(\vec{P}_{2,2},U_T)-\frac{35}{6336}t(\vec{P}_{1,1},U_T)\] and \[g(U_T):=- \frac{1}{2}t(\vec{P}_{1,1},U_T)t(\vec{P}_{2,2},U_T)+ \frac{1}{4}t(\vec{P}_{1,1},U_T)^3 +\frac{1}{8}t(\vec{P}_{1,1},U_T)^2 - \frac{1}{99}t(\vec{P}_{1,1},U_T).\] We observe that the expression in 3 is precisely \(f(U_T)+g(U_T)+\frac{1}{256}\). So, it suffices to show that \(f(U_T)\leq 0\) and \(g(U_T)\leq 0\).
Consider first the polynomial \[p(x):=x^4+\frac{3}{4}x^3-\frac{3}{16}x^2-\frac{35}{6336}x.\] It is a simple calculus exercise to show that \(p(x)\leq 0\) for all \(x\in[0,1/\pi^2]\). Thus \(-p(x)\geq0\) on this interval, so Lemma 1 gives \(f(U_T)\leq 0\). Next, by Lemma 1, we have that \[g(U_T)\leq - \frac{1}{4}t(\vec{P}_{1,1},U_T)^3 +\frac{1}{8}t(\vec{P}_{1,1},U_T)^2 - \frac{1}{99}t(\vec{P}_{1,1},U_T).\] By Lemma 1, we know that \(0\leq t(\vec{P}_{1,1},U_T)\leq 1/12\). The polynomial \(q(x)=-\frac{1}{4}x^3 + \frac{1}{8}x^2-\frac{1}{99}x\) satisfies \(q(x)\leq 0\) for all \(x\in [0,1/12]\) and so \(g(U_T)\leq0\). This completes the proof. ◻
Combining Lemma 1 and Proposition 1 immediately yields the following.
Lemma 1. For \(k\geq5\), if \(\vec{P}_{k-3,k-3}\) is tournament anti-Sidorenko, then so is \(\vec{P}_{1,k}\).
Thus, as we already know that \(\vec{P}_{1,2},\vec{P}_{1,3}\) and \(\vec{P}_{1,4}\) are tournament anti-Sidorenko by Propositions 1, 1 and 1, respectively, Lemma 1 implies that, in order to prove that \(\vec{P}_{1,k}\) is tournament anti-Sidorenko for every \(k\geq2\), it suffices to know that \(\vec{P}_{j,j}\) is tournament anti-Sidorenko for every \(j\geq2\). All oriented paths with exactly two blocks, each of which has length two, including the paths \(\vec{P}_{j,j}\) for \(j\geq2\), are covered by Theorem 1. Putting this all together, we see that, once Theorem 1 has been proven, Theorem 1 will easily follow.
As it turns out, it is useful to establish the case of \(\vec{P}_{2,2}\) separately. This is quite easy to do using the ideas from this section.
Proposition 1. The oriented path \(\vec{P}_{2,2}\) is tournament anti-Sidorenko.
Proof. Let \(\vec{T}\) be a tournament with \(n\) vertices and let \(U_T:= A_{\vec{T}}^*-\frac{1}{2}J_n\). Analogous to the proof of Proposition 1, we have \[t(\vec{P}_{2,2},\vec{T})\leq t(\vec{P}_{2,2},A_{\vec{T}}^*)=\sum_{S\subseteq A(\vec{P}_{2,2})}(1/2)^{4-|S|}t(\vec{P}_{2,2}[S],U_T).\] Using Lemmas 1, 1 and 1, the right-hand side is equal to \[t(\vec{P}_{2,2},U_T)-\frac{1}{4}t(\vec{P}_{1,1},U_T) + \frac{1}{16}.\] The polynomial \(\frac{1}{4}x-x^2\) is non-negative for all \(x\in [0,1/4]\); in particular, it is non-negative for \(x\in[0,1/\pi^2]\). Hence Lemma 1 gives \[t(\vec{P}_{2,2},U_T)-\frac{1}{4}t(\vec{P}_{1,1},U_T)\leq 0.\] Therefore \(t(\vec{P}_{2,2},A_{\vec{T}}^*)\leq 1/16\), and so \(\vec{P}_{2,2}\) is tournament anti-Sidorenko. ◻
4 Making Sandwiches↩︎
The purpose of this section is to present an information-theoretic approach for certifying that a given oriented forest is tournament anti-Sidorenko. The approach boils down to constructing a certificate which we call a “sandwich.” The main lemma of the section states that the existence of an \(\vec{H}\)-sandwich implies that \(\vec{H}\) is tournament anti-Sidorenko. The later sections are devoted to constructing sandwiches for the paths and spiders and using them to prove our main theorems.
Before stating our main definition and lemma, we require the following standard terminology. We say that an oriented graph \(\vec{D}\) contains another oriented graph \(\vec{H}\) as a subgraph if \(V(\vec{H})\subseteq V(\vec{D})\) and \(A(\vec{H})\subseteq A(\vec{D})\). A set \(S\subseteq V(\vec{D})\) is connected if, for every partition \(\{A,B\}\) of \(S\), there exists an arc of \(\vec{D}\) with one endpoint in each of \(A\) and \(B\). A component of \(\vec{D}\) is a maximal non-empty connected subset of \(V(\vec{D})\). For \(S\subseteq V(\vec{D})\), the subgraph of \(\vec{D}\) induced by \(S\), denoted \(\vec{D}[S]\), is the oriented graph with vertex set \(S\) containing all arcs of \(\vec{D}\) that have both endpoints in \(S\). Given a homomorphism \(\psi:\vec{D}\to \vec{H}\) and an arc \((u,v)\in A(\vec{H})\), let \(\psi^{-1}(u,v)\) be the set of all arcs \((x,y)\) of \(\vec{D}\) such that \(\psi(x)=u\) and \(\psi(y)=v\). An involution on a set \(X\) is a function \(\pi:X\to X\) such that \(\pi\circ\pi\) is the identity.
Definition 1. Let \(\vec{H}\) be an oriented forest. An \(\vec{H}\)-sandwich8 is a tuple \(\mathcal{S}=(\vec{D},\psi,\omega,\pi)\) satisfying the following properties:
\(\vec{D}\) is an oriented forest that contains \(\vec{H}\) as a subgraph.
\(\psi\) is a homomorphism from \(\vec{D}\) to \(\vec{H}\) which fixes every vertex of \(\vec{H}\).
\(\omega:\mathcal{C}\to [0,\infty)\) is a weight function, where \(\mathcal{C}\) is the collection of all components of \(\vec{D}\setminus V(\vec{H})\). Given \(v\in V(\vec{D})\), we let \(\omega(v)\) be equal to \(\omega(C)\) if \(v\in C\) for some \(C\in\mathcal{C}\) and \(0\) otherwise. Given an arc \((u,v)\in A(\vec{D})\), if there exists \(C\in\mathcal{C}\) such that \(\{u,v\}\cap C\neq \emptyset\), then we let \(\omega(u,v):=\omega(C)\) and we let \(\omega(u,v):=0\) otherwise.
For every arc \((u,v)\) of \(\vec{H}\), \(\sum_{(x,y)\in \psi^{-1}(u,v)}\omega(x,y) = 1\).
For every vertex \(v\) of \(\vec{H}\), \(\sum_{x\in \psi^{-1}(v)}\omega(x) \leq 1\).
\(\{\mathcal{C}_1,\dots,\mathcal{C}_m\}\) is a partition of \(\mathcal{C}\) such that \(\omega\) is constant on \(\mathcal{C}_j\) for all \(1\leq j\leq m\).
\(\vec{D}\left[\bigcup_{C\in \mathcal{C}_j}C\right]\) is tournament anti-Sidorenko for all \(1\leq j\leq m\).
Every component \(C\in\mathcal{C}\) is incident with at most one arc of \(\vec{D}\) that has one endpoint in \(C\) and the other endpoint in \(V(\vec{H})\).
\(\pi\) is an involution on \(V(\vec{D})\setminus V(\vec{H})\) that is a homomorphism from \(\vec{D}\setminus V(\vec{H})\) to itself.
\(\omega(v)=\omega(\pi(v))\) for all \(v\in V(\vec{D})\setminus V(\vec{H})\).
Given \(u\in V(\vec{H})\) and \(v\in V(\vec{D})\setminus V(\vec{H})\), there is an arc from \(u\) to \(v\) in \(\vec{D}\) if and only if there is an arc from \(\pi(v)\) to \(u\) in \(\vec{D}\).
We say that \(\mathcal{S}\) is a partial \(\vec{H}\)-sandwich if all of the above conditions hold, except that [eq:coverede] is relaxed to
- For every arc \((u,v)\) of \(\vec{H}\), \(\sum_{(x,y)\in \psi^{-1}(u,v)}\omega(x,y) \leq 1\).
Let \(\mathcal{S}=(\vec{D},\psi,\omega,\pi)\) be an \(\vec{H}\)-sandwich or a partial \(\vec{H}\)-sandwich. For an arc \((u,v)\in A(\vec{H})\), define \[\mathop{\mathrm{cov}}_{\mathcal{S}}(u,v):= \sum_{(x,y)\in \psi^{-1}(u,v)}\omega(x,y)\] and, for \(v\in V(\vec{H})\), define \[\mathop{\mathrm{cov}}_{\mathcal{S}}(v):= \sum_{x\in \psi^{-1}(v)}\omega(x).\] Then [eq:coverede] can be rewritten as \(\mathop{\mathrm{cov}}_\mathcal{S}(u,v)=1\) for all \((u,v)\in A(\vec{H})\) and [eq:coveredv] and [eq:coveredepartial] can be expressed in terms of \(\mathop{\mathrm{cov}}_\mathcal{S}\) in a similar fashion. The main goal of this section is to prove the following lemma which says that, if an \(\vec{H}\)-sandwich exists, then \(\vec{H}\) is tournament anti-Sidorenko.
Lemma 1. Let \(\vec{H}\) be an oriented forest. If there exists an \(\vec{H}\)-sandwich, then \(\vec{H}\) is tournament anti-Sidorenko.
While Definition 1 and 1 are new, they are rooted in several existing ideas. In particular, they are heavily inspired by the approach in our recent solution [23] to an extremal problem of Basit, Granet, Horsley, Küngen and Staden [24] on alternating paths in edge-coloured graphs. Moreover, the idea underlying the conditions [eq:anti-Sidcomponents] and [eq:reverseArcs] is closely related to Lemma 1, which is essentially the same as [1].
Before embarking on the proof of Lemma 1, let us demonstrate its utility by giving an alternative proof of the result [11] that directed paths are tournament anti-Sidorenko.
Proposition 1 (Sah, Sawhney and Zhao [11]). \(\vec{P}_k\) is tournament anti-Sidorenko for all \(k\geq0\).
Proof. It is easily observed that \(\vec{P}_0\) and \(\vec{P}_1\) are tournament anti-Sidorenko, and so we assume that \(k\geq2\). Let \(\vec{D}_k\) be an oriented forest obtained from \(\vec{P}_k\) by adding
vertices \(w_0,w_1,w_{k-1},w_k\), \(u_0^+,\dots,u_{k-2}^+\), and \(u_2^-,\dots,u_k^-\).
arcs \((w_0,w_1),\) \((w_{k-1},w_k)\), \((u_0^+,v_1),\dots,(u_{k-2}^+,v_{k-1})\), and \((v_1,u_2^-),\dots,(v_{k-1},u_k^-)\).
We define \(\psi_k:\vec{D}_k\to\vec{P}_k\) so that each vertex of \(\vec{D}_k\) is mapped to the vertex with the same subscript as it. That is, \(\psi_k(v_i)=v_i\), \(\psi_k(u_i^+)=v_i\), \(\psi_k(u_i^-)=v_i\) and \(\psi_k(w_i)=v_i\). We let \(\omega_k\) be a weight function on the components of \(\vec{D}_k\setminus V(\vec{P}_k)\) which assigns weight \(1/2\) to each component. Finally, we let \(\pi_k\) be an involution on \(V(\vec{D}_k)\setminus V(\vec{P}_k)\) which fixes \(w_0,w_1,w_{k-1},w_k\) and maps \(u_{i-1}^+\) to \(u_{i+1}^-\) for all \(1\leq i\leq k-1\). See Figure 6. It is easily observed that all of the properties of Definition 1 hold for \((\vec{D}_k,\psi_k,\omega_k,\pi_k)\) with respect to \(\vec{H}=\vec{P}_k\), where the partition in [eq:partition] is taken to be the trivial partition on the components of \(\vec{D}_k\setminus V(\vec{P}_k)\). Thus, \((\vec{D}_k,\psi_k,\omega_k,\pi_k)\) is a \(\vec{P}_k\)-sandwich and the result follows by Lemma 1. ◻
![Figure 6: The oriented graph \vec{D}_k used in the proof of Proposition 1 in the case k=5. The vertices are drawn in six columns and every vertex u of \vec{D}_5 is mapped by \psi_5 to the vertex v_i in the same column as u. Every component of \vec{D}_5\setminus V(\vec{P}_5) has weight 1/2. We let \pi_5 be the unique map which satisfies condition [eq:reverseArcs] and fixes w_0,w_1,w_4,w_5.](/article/2605.14138/_pdflatex/lhpadeiz.png "fig:")
Remark 1. All of our diagrams of \(\vec{P}\)-sandwiches and partial \(\vec{P}\)-sandwiches \(\mathcal{S}=(\vec{D},\psi,\omega,\pi)\) for an oriented path \(\vec{P}\) follow the same convention as Figure 6. Near the middle of the diagram is a copy of \(\vec{P}\) with its vertices \(v_0,\dots,v_k\) drawn from left to right in \(k+1\) columns. All vertices of \(\vec{D}\) which are drawn in the \(i\)th column are mapped by \(\psi\) to \(v_i\). The weight function is indicated in the caption of the figure or in the diagram itself. Consequently, the values of \(\mathop{\mathrm{cov}}_\mathcal{S}\) can be read from the figure by summing the weights in each column and between consecutive columns. In most cases, the involution \(\pi\) is almost uniquely determined by the fact that it needs to satisfy [eq:involution], [eq:sameWeight] and [eq:reverseArcs] and the partition of \(\mathcal{C}\) is the trivial partition. Any potential ambiguities are explained in the caption of the figure. To keep the main text readable, most of these figures are collected in Appendix 8.
Remark 1. A useful feature of our approach is that the search for sandwiches can be automated using linear programming software, which can allow one to quickly discover constructions which are far more complex than any human could hope to find by hand. That is, given an oriented forest \(\vec{H}\) and a collection \(\mathcal{A}\) of oriented forests which are already known to be tournament anti-Sidorenko, one can create a variable for each tuple \((\vec{A},\psi_{\vec{A}},u,v,s)\) where \(\vec{A}\in\mathcal{A},\psi_{\vec{A}}:\vec{A}\to\vec{H},u\in V(\vec{H}),v\in V(\vec{A})\) and \(s\in\{-1,0,1\}\). This variable corresponds to the weight of a component of \(V(\vec{D})\setminus V(\vec{H})\) which is isomorphic to \(\vec{A}\) such that the restriction of \(\psi\) to this component is \(\psi_{\vec{A}}\) and \(\vec{D}\) has an arc from \(v\) to \(u\) if \(s=-1\), from \(u\) to \(v\) if \(s=1\), and no arc between \(u\) and \(v\) if \(s=0\). To ensure that the final construction satisfies all properties of Definition 1 simply boils down to searching for a weight function which satisfies a particular system of linear constraints. This explains how all of the sandwiches in this paper were discovered in practice.
We now turn our attention toward building up the ideas that we need to prove Lemma 1. Given a \(\vec{H}\)-sandwich \((\vec{D},\psi,\omega,\pi)\), our goal will be to construct an oriented graph \(\vec{F}\) that is larger than \(\vec{H}\) such that \(t(\vec{H},\vec{T})\) is bounded above and below by two different expressions of \(t(\vec{F},\vec{T})\) for every tournament \(\vec{T}\), from which it will follow that \(\vec{H}\) is tournament anti-Sidorenko. This is made more precise in the next lemma, which is inspired by [23].
Lemma 1. Let \(\vec{H}\) be an oriented graph with \(a(\vec{H})\neq0\). If there exists an oriented graph \(\vec{F}\) such that \(a(\vec{F})>a(\vec{H})\) and every tournament \(\vec{T}\) satisfies \[\label{eq:entropyBound} t(\vec{H},\vec{T})^{a(\vec{F})/a(\vec{H})}\leq t(\vec{F},\vec{T})\qquad{(1)}\] and \[\label{eq:strippingOff} t(\vec{F},\vec{T})\leq (1/2)^{a(\vec{F})-a(\vec{H})}t(\vec{H},\vec{T}),\qquad{(2)}\] then \(\vec{H}\) is tournament anti-Sidorenko.
Proof. Let \(\vec{T}\) be a tournament. We have \[t(\vec{H},\vec{T})\leq t(\vec{F},\vec{T})^{a(\vec{H})/a(\vec{F})}\leq \left((1/2)^{a(\vec{F})-a(\vec{H})}t(\vec{H},\vec{T})\right)^{a(\vec{H})/a(\vec{F})}.\] Since \(a(\vec{F})>a(\vec{H})\), this simplifies to \(t(\vec{H},\vec{T})\leq (1/2)^{a(\vec{H})}\), as desired. ◻
When applying Lemma 1, we will always certify the inequality ?? using Lemma 1. When certifying ?? , we apply an entropy-based approach that originated in a paper of Kopparty and Rossman [25] and has been used in, e.g., [19], [23], [26]–[29]. We will now review the basic properties of entropy that we will need.
Let \(X\) be a discrete random variable. Its range is \[\mathop{\mathrm{rng}}(X):=\{x:\mathbb{P}(X=x)>0\}\] and the entropy of \(X\) is \[\mathbb{H}(X):=-\sum_{x\in\mathop{\mathrm{rng}}(X)}\mathbb{P}(X=x)\log_2(\mathbb{P}(X=x)).\] A useful way of thinking of the entropy of a random variable is as the average amount of information carried by the random variable \(X\), measured in bits. As a simple example, if the range of \(X\) has cardinality \(2^n\) and all outcomes are equally likely, then \(X\) has the same distribution as a uniformly random binary string of length \(n\). So, revealing the outcome of \(X\) is like revealing \(n\) bits of information and so, naturally, the entropy of \(X\) is equal to \(n\).
If \(X\) and \(Y\) are discrete random variables and \(y\in \mathop{\mathrm{rng}}(Y)\), then the conditional entropy of \(X\) given that \(Y=y\) is defined to be \[\mathbb{H}(X\mid Y=y):=-\sum_{x\in \mathop{\mathrm{rng}}(X\mid Y=y)}\mathbb{P}(X=x\mid Y=y)\log_2(\mathbb{P}(X=x\mid Y=y)),\] and the conditional entropy of \(X\) given \(Y\) is \[\mathbb{H}(X\mid Y):=\sum_{y\in \mathop{\mathrm{rng}}(Y)}\mathbb{P}(Y=y)\mathbb{H}(X\mid Y=y).\] We can think of \(\mathbb{H}(X\mid Y)\) as the average amount of information that is gained by learning the outcome of \(X\) after the outcome of \(Y\) is already known.
We will use the following three standard facts about entropy.
Lemma 1 (Maximality of the uniform distribution). If \(X\) is a discrete random variable with finite range, then \[\mathbb{H}(X)\leq \log_2(|\mathop{\mathrm{rng}}(X)|),\] with equality if and only if \(X\) is uniformly distributed on \(\mathop{\mathrm{rng}}(X)\).
Lemma 1 (Chain rule). For any discrete random variables \(X_1,\dots,X_m\), \[\mathbb{H}(X_1,\dots,X_m)=\mathbb{H}(X_1)+\sum_{i=2}^m \mathbb{H}(X_i\mid X_1,\dots,X_{i-1}).\]
Lemma 1 (Deconditioning). For any discrete random variables \(X,Y\) and \(Z\), \[\mathbb{H}(X\mid Y,Z)\leq \mathbb{H}(X\mid Z)\] with equality if and only if \(X\) and \(Y\) are conditionally independent given \(Z\).
Our next goal is to obtain a formula for the entropy of a uniformly random homomorphism from an oriented forest. If \(\vec{F}\) is an oriented forest and \(v\in V(\vec{F})\), then \(d_{\vec{F}}(v)\) denotes the number of arcs that are incident with \(v\); i.e., it is the degree of \(v\) in the unoriented forest underlying \(\vec{F}\).
Lemma 1. Let \(\vec{F}\) be an oriented forest and let \(\vec{G}\) be an oriented graph with \(\hom(\vec{F},\vec{G})\geq 1\). Let \(\varphi\) be a uniformly random homomorphism from \(\vec{F}\) to \(\vec{G}\). Then \[\mathbb{H}(\varphi)=\sum_{(u,v)\in A(\vec{F})}\mathbb{H}(\varphi(u),\varphi(v))-\sum_{v\in V(\vec{F})}(d_{\vec{F}}(v)-1)\mathbb{H}(\varphi(v)).\]
Proof. Let \(\vec{F}_1,\dots,\vec{F}_s\) be the components of \(\vec{F}\). The set of homomorphisms from \(\vec{F}\) to \(\vec{G}\) is the Cartesian product of the sets of homomorphisms from the components \(\vec{F}_1,\dots,\vec{F}_s\) to \(\vec{G}\). Therefore the restrictions of \(\varphi\) to the components of \(\vec{F}\) are independent uniformly random homomorphisms. Entropy is additive on independent tuples (by Lemmas 1 and 1), so it suffices to prove the lemma when \(\vec{F}\) is connected; i.e. \(\vec{F}\) is an oriented tree.
Choose a root \(r\in V(\vec{F})\) and order the vertices as \(v_1,\dots,v_m\) so that \(v_1=r\) and, for each \(i\geq 2\), there is a unique index \(p(i)\in\{1,\dots,i-1\}\) such that one of the arcs \((v_i,v_{p(i)})\) or \((v_{p(i)},v_i)\) is present in \(\vec{F}\); we call \(v_{p(i)}\) the parent of \(v_i\). For each \(i\geq 2\), let \(\vec{S}_i\) be the subtree of \(\vec{F}\) induced by \(v_i\) and all of its descendants, and, for each \(x\in V(\vec{G})\), let \(\hom_{v_i\mapsto x}(\vec{S}_i,\vec{G})\) be the number of homomorphisms from \(\vec{S}_i\) to \(\vec{G}\) that send \(v_i\) to \(x\).
Fix \(i\geq 2\). Suppose that \(x_1,\dots,x_{i-1}\in V(\vec{G})\) such that the event \[(\varphi(v_1),\dots,\varphi(v_{i-1}))=(x_1,\dots,x_{i-1})\] has positive probability. Since \(\vec{F}\) is an oriented tree, for any \(x\in V(\vec{G})\), \[\mathbb{P}(\varphi(v_i)=x\mid \varphi(v_1)=x_1,\dots,\varphi(v_{i-1})=x_{i-1})\] is proportional to the product of the indicator that \(x\) and \(x_{p(i)}\) form an arc in \(\vec{G}\) of the required orientation and the quantity \(\hom_{v_i\mapsto x}(\vec{S}_i,\vec{G})\). In particular, the only dependence of \(\varphi(v_i)=x\) on the event \((\varphi(v_1),\dots,\varphi(v_{i-1}))=(x_1,\dots,x_{i-1})\) is through \(\varphi(v_{p(i)})=x_{p(i)}\). Therefore, \[\mathbb{H}(\varphi(v_i)\mid \varphi(v_1),\dots,\varphi(v_{i-1})) = \mathbb{H}(\varphi(v_i)\mid \varphi(v_{p(i)})).\] By combining the above equality with two applications of Lemma 1, we obtain \[\begin{align} \mathbb{H}(\varphi) &=\mathbb{H}(\varphi(v_1),\dots,\varphi(v_m))\\ &=\mathbb{H}(\varphi(v_1))+\sum_{i=2}^m\mathbb{H}(\varphi(v_i)\mid \varphi(v_1),\dots,\varphi(v_{i-1}))\\ &=\mathbb{H}(\varphi(v_1))+\sum_{i=2}^m\mathbb{H}(\varphi(v_i)\mid \varphi(v_{p(i)}))\\ &=\mathbb{H}(\varphi(v_1))+\sum_{i=2}^m\left(\mathbb{H}(\varphi(v_i),\varphi(v_{p(i)}))-\mathbb{H}(\varphi(v_{p(i)}))\right). \end{align}\] Each edge of the underlying undirected tree of \(\vec{F}\) appears exactly once as an arc between a vertex and its parent, and entropy is invariant under permuting the coordinates of a tuple. Hence \[\sum_{i=2}^m\mathbb{H}(\varphi(v_i),\varphi(v_{p(i)})) = \sum_{(u,v)\in A(\vec{F})}\mathbb{H}(\varphi(u),\varphi(v)).\] Moreover, a non-root vertex \(v\) is the parent of exactly \(d_{\vec{F}}(v)-1\) vertices, while the root is the parent of exactly \(d_{\vec{F}}(r)\) vertices. Therefore the coefficient of \(\mathbb{H}(\varphi(v))\) in the above expression is \(-(d_{\vec{F}}(v)-1)\) for every \(v\in V(\vec{F})\), which proves the lemma. ◻
The next lemma is the main mechanism for establishing the bound ?? required for applications of Lemma 1. Similar ideas are used in, e.g., [19], [23], [29].
Lemma 1. Let \(\vec{H}\) and \(\vec{F}\) be oriented forests. Suppose that there exists a homomorphism \(\phi:\vec{F}\to \vec{H}\) and an integer \(c\geq 1\) such that the following hold:
\(|\phi^{-1}(u,v)|=c\) for every arc \((u,v)\in A(\vec{H})\),
\(|\phi^{-1}(v)|=c\) for every vertex \(v\in V(\vec{H})\).
Then every oriented graph \(\vec{G}\) satisfies \[t(\vec{H},\vec{G})^c\leq t(\vec{F},\vec{G}).\]
Proof. If \(\hom(\vec{H},\vec{G})=0\), then the inequality is trivial. So assume that \(\hom(\vec{H},\vec{G})\geq 1\), and let \(\varphi\) be a uniformly random homomorphism from \(\vec{H}\) to \(\vec{G}\).
Our goal is to construct a random homomorphism \(\theta:\vec{F}\to \vec{G}\) of entropy equal to \(c\cdot\mathbb{H}(\varphi)\). Choose a root in each component of \(\vec{F}\). For each root \(r\), choose \(\theta(r)\) according to the distribution of \(\varphi(\phi(r))\), independently of all choices made so far. If \(x\) is not a root and has parent \(y\), then, having already defined \(\theta(y)\), choose \(\theta(x)\) according to the conditional distribution of \(\varphi(\phi(x))\) given the event that \(\varphi(\phi(y))=\theta(y)\), independently of all other previously made choices. Since \(\phi\) and \(\varphi\) are homomorphisms, every pair in the support of \((\varphi(\phi(y)),\varphi(\phi(x)))\) is an arc of \(\vec{G}\) with the same direction as the arc between \(y\) and \(x\). Thus, \(\theta\) is a homomorphism from \(\vec{F}\) to \(\vec{G}\) with probability one.
By induction on the distance from the roots, it can be easily verified that \(\theta(u)\) has the same distribution as \(\varphi(\phi(u))\) and \((\theta(u),\theta(v))\) has the same distribution as \((\varphi(\phi(u)),\varphi(\phi(v)))\) for every \(u\in V(\vec{F})\) and \((u,v)\in A(\vec{F})\). Moreover, for each non-root vertex \(u\), the random variable \(\theta(u)\) is conditionally independent of all previously exposed variables other than its parent, given the image of its parent. Consequently, the same chain-rule computation used in the proof of Lemma 1 gives \[\mathbb{H}(\theta)=\sum_{(u,v)\in A(\vec{F})}\mathbb{H}(\theta(u),\theta(v))-\sum_{u\in V(\vec{F})}(d_{\vec{F}}(u)-1)\mathbb{H}(\theta(u)).\] Substituting the distributions of the random variables \(\theta(u)\) and then grouping the resulting terms according to \(\phi\), we obtain \[\begin{align} \mathbb{H}(\theta) &=\sum_{(u,v)\in A(\vec{F})}\mathbb{H}(\varphi(\phi(u)),\varphi(\phi(v))) -\sum_{u\in V(\vec{F})}(d_{\vec{F}}(u)-1)\mathbb{H}(\varphi(\phi(u)))\\ &=\sum_{(a,b)\in A(\vec{H})}|\phi^{-1}(a,b)|\,\mathbb{H}(\varphi(a),\varphi(b)) -\sum_{v\in V(\vec{H})}\left(\sum_{u\in\phi^{-1}(v)}(d_{\vec{F}}(u)-1)\right)\mathbb{H}(\varphi(v)). \end{align}\] By [eq:Acover], the first term is equal to \[c\sum_{(a,b)\in A(\vec{H})}\mathbb{H}(\varphi(a),\varphi(b)).\] For the second term, fix \(v\in V(\vec{H})\). Since \(\phi\) is a homomorphism, every arc of \(\vec{F}\) incident with a vertex in \(\phi^{-1}(v)\) is mapped to an arc of \(\vec{H}\) incident with \(v\), and every arc of \(\vec{H}\) incident with \(v\) has exactly \(c\) preimages. Therefore, \[\sum_{u\in\phi^{-1}(v)}d_{\vec{F}}(u)=c\,d_{\vec{H}}(v).\] Using [eq:Vcover], we deduce that \[\sum_{u\in\phi^{-1}(v)}(d_{\vec{F}}(u)-1)=c\,d_{\vec{H}}(v)-c=c(d_{\vec{H}}(v)-1).\] Hence \[\mathbb{H}(\theta) = c\sum_{(a,b)\in A(\vec{H})}\mathbb{H}(\varphi(a),\varphi(b)) - c\sum_{v\in V(\vec{H})}(d_{\vec{H}}(v)-1)\mathbb{H}(\varphi(v)).\] Applying Lemma 1 to \(\varphi\), we conclude that \[\mathbb{H}(\theta)=c\,\mathbb{H}(\varphi)=c\log_2(\hom(\vec{H},\vec{G})).\] Since \(\theta\) is supported on homomorphisms from \(\vec{F}\) to \(\vec{G}\), Lemma 1 implies that \[\log_2(\hom(\vec{F},\vec{G}))\geq \mathbb{H}(\theta)=c\log_2(\hom(\vec{H},\vec{G})).\] Exponentiating gives \[\hom(\vec{F},\vec{G})\geq \hom(\vec{H},\vec{G})^c.\] Finally, dividing by \(v(\vec{G})^{v(\vec{F})}=v(\vec{G})^{c\,v(\vec{H})}\), where the equality follows from [eq:Vcover], yields \[t(\vec{F},\vec{G})\geq t(\vec{H},\vec{G})^c.\] This completes the proof. ◻
We are now ready to prove the main lemma of the section.
Proof of Lemma 1. If \(a(\vec{H})=0\), then the conclusion is immediate. So assume from now on that \(a(\vec{H})\geq 1\).
Let \(\mathcal{S}=(\vec{D},\psi,\omega,\pi)\) be an \(\vec{H}\)-sandwich, and let \(\mathcal{C}\) be the set of components of \(\vec{D}\setminus V(\vec{H})\). By Lemma 1, the disjoint union of two tournament anti-Sidorenko oriented graphs is again tournament anti-Sidorenko.
Next, observe that, given the choice of \(\vec{D},\psi\) and \(\pi\), the conditions imposed on \(\omega\) in Definition 1 form a finite system of linear equalities and inequalities with rational coefficients. Since this system is feasible (because \(\omega\) exists), it has a rational feasible point. We may therefore assume that \(\omega(C)\in\mathbb{Q}\) for every \(C\in\mathcal{C}\). Choose a positive integer \(q\) such that \(q\omega(C)\in\mathbb{Z}\) for every \(C\in\mathcal{C}\).
We first construct an oriented forest \(\vec{F}\) as follows. Start with one distinguished copy of \(\vec{H}\). Then, for each \(C\in\mathcal{C}\), add \(q\omega(C)\) disjoint copies of \(C\) and attach each of them to the distinguished copy of \(\vec{H}\) exactly as \(C\) is attached to \(\vec{H}\) inside \(\vec{D}\). Then, for each \(v\in V(\vec{H})\), add a set \(L_v\) of \[q-\sum_{x\in\psi^{-1}(v)}q\omega(x)\] isolated vertices associated with \(v\). This quantity is a nonnegative integer by [eq:coveredv]. Let \(\vec{F}\) denote the resulting oriented forest, and let \[\phi:\vec{F}\to\vec{H}\] be the natural homomorphism that fixes the distinguished copy of \(\vec{H}\) pointwise, acts as \(\psi\) on every non-isolated added copy, and, for each \(v\in V(\vec{H})\), maps every vertex of \(L_v\) to \(v\).
For every arc \((u,v)\in A(\vec{H})\), we have \[|\phi^{-1}(u,v)|=1+\sum_{(x,y)\in\psi^{-1}(u,v)}q\omega(x,y)=q+1,\] where the initial \(1\) comes from the distinguished copy of \(\vec{H}\) and the final equality follows from [eq:coverede]. By construction, every vertex of \(\vec{H}\) also has exactly \(q+1\) preimages under \(\phi\); the cardinality of the sets \(L_v\) was chosen precisely to ensure this. Therefore Lemma 1 gives \[\label{eq:entropyMainLower} t(\vec{H},\vec{T})^{q+1}\leq t(\vec{F},\vec{T})\tag{4}\] for every tournament \(\vec{T}\).
So, by Lemma 1, to establish ?? , it suffices to prove that \[\label{eq:q431} q+1=\frac{a(\vec{F})}{a(\vec{H})}.\tag{5}\] For each \(C\in\mathcal{C}\), let \(a^*(C)\) denote the number of arcs of \(\vec{D}\) having at least one endpoint in \(C\). Since the isolated vertices added at the final step contribute no arcs, we have \[a(\vec{F})=a(\vec{H})+\sum_{C\in\mathcal{C}}q\omega(C)\,a^*(C).\] On the other hand, summing [eq:coverede] over all arcs of \(\vec{H}\) shows that \[\sum_{C\in\mathcal{C}}\omega(C)\,a^*(C)=a(\vec{H}),\] because every arc of \(\vec{D}\) with at least one endpoint outside \(\vec{H}\) contributes exactly the weight of its component to the left-hand side. Hence \[a(\vec{F})=a(\vec{H})+q\,a(\vec{H})=(q+1)a(\vec{H}).\] So, 5 holds. Therefore, ?? holds.
It remains to prove that ?? holds. That is, we prove that every tournament \(\vec{T}\) satisfies \[\label{eq:entropyMainUpperGoal} t(\vec{F},\vec{T})\leq (1/2)^{a(\vec{F})-a(\vec{H})}t(\vec{H},\vec{T}).\tag{6}\] Fix a tournament \(\vec{T}\), and write \(n:=v(\vec{T})\). Let \(\vec{F}_0\) be the subgraph of \(\vec{F}\) obtained by deleting the isolated vertices in the sets \(L_v\) for \(v\in V(\vec{H})\). Then \[\hom(\vec{F},\vec{T}) = n^{v(\vec{F})-v(\vec{F}_0)}\hom(\vec{F}_0,\vec{T}).\]
For a component \(C\in\mathcal{C}\), let \(\pi(C)\) denote the component of \(\vec{D}\setminus V(\vec{H})\) containing \(\pi(x)\) for some (equivalently every) vertex \(x\in C\). This is well-defined because \(\pi\) is a homomorphism from \(\vec{D}\setminus V(\vec{H})\) to itself and is an involution. Moreover, \(\pi\) restricts to an isomorphism from \(\vec{D}[C]\) to \(\vec{D}[\pi(C)]\).
Let \(\mathcal{C}^*\) be the set of components of \(\vec{D}\setminus V(\vec{H})\) that are incident with an arc having one endpoint in \(V(\vec{H})\). For \(C\in\mathcal{C}\), write \[r_C:=q\omega(C).\] By [eq:sameWeight], we have \(r_C=r_{\pi(C)}\) for every \(C\in\mathcal{C}\).
We first handle the components attached to \(\vec{H}\). The components in \(\mathcal{C}^*\) are paired by \(\pi\). Indeed, if \(C\) is attached to \(\vec{H}\), then [eq:reverseArcs] implies that \(\pi(C)\) is also attached to \(\vec{H}\). Moreover, no component in \(\mathcal{C}^*\) is fixed by \(\pi\). To see this, suppose that \(C=\pi(C)\) and that \(C\) is attached through an arc involving a vertex \(x\in C\) and a vertex \(h\in V(\vec{H})\). Then [eq:reverseArcs] gives the reversed attachment arc involving \(\pi(x)\in C\) and the same vertex \(h\). This contradicts [eq:singleAttachment]. Thus the components in \(\mathcal{C}^*\) split into two-element pairs \(\{C,\pi(C)\}\).
For each pair, choose one representative \(C\) so that the attachment arc from \(\vec{H}\) to the pair has the form \[(h_C,x_C),\] where \(h_C\in V(\vec{H})\) and \(x_C\in C\). Then [eq:reverseArcs] says that \(\pi(C)\) is attached through \(\pi(x_C)\) by the arc \[(\pi(x_C),h_C).\] Let \(\mathcal{R}\) be the set of these chosen representatives.
We now define an explicit sequence of graphs. Enumerate the multiset \[\{(C,s): C\in\mathcal{R},\;1\leq s\leq r_C\}\] as \[(C_1,s_1),\dots,(C_N,s_N).\] Let \(\vec{B}_0\) be the distinguished copy of \(\vec{H}\). Having defined \(\vec{B}_{i-1}\), define \(\vec{B}_i\) by adding to \(\vec{B}_{i-1}\) one fresh copy of \(\vec{D}[C_i]\) and one fresh copy of \(\vec{D}[\pi(C_i)]\), attached to the distinguished copy of \(\vec{H}\) by the arcs corresponding to \[(h_{C_i},x_{C_i}) \qquad\text{and}\qquad (\pi(x_{C_i}),h_{C_i}).\] Since \(\pi\) restricts to an isomorphism from \(\vec{D}[C_i]\) to \(\vec{D}[\pi(C_i)]\), the graph \(\vec{B}_i\) is isomorphic to the graph obtained from \(\vec{B}_{i-1}\) by applying the construction in Lemma 1 with \(u=h_{C_i}\) and with the rooted graph \((\vec{D}[C_i],x_{C_i})\). Therefore Lemma 1 gives \[\hom(\vec{B}_i,\vec{T}) \leq \frac{1}{4}\hom(\vec{B}_{i-1},\vec{T})\hom(\vec{D}[C_i],\vec{T})^2 = \frac{1}{4}\hom(\vec{B}_{i-1},\vec{T})\hom(\vec{D}[C_i],\vec{T})\hom(\vec{D}[\pi(C_i)],\vec{T}).\] Iterating over \(i=1,\dots,N\) gives \[\hom(\vec{B}_N,\vec{T}) \leq \hom(\vec{H},\vec{T}) \prod_{C\in\mathcal{R}} \left( \frac{1}{4}\hom(\vec{D}[C],\vec{T})\hom(\vec{D}[\pi(C)],\vec{T}) \right)^{r_C}.\]
The graph \(\vec{B}_N\) is the part of \(\vec{F}_0\) consisting of the distinguished copy of \(\vec{H}\) together with all copies of components in \(\mathcal{C}^*\). The remaining components of \(\vec{F}_0\) are disjoint copies of the unattached components. Hence \[\hom(\vec{F}_0,\vec{T}) = \hom(\vec{B}_N,\vec{T}) \prod_{C\in\mathcal{C}\setminus\mathcal{C}^*}\hom(\vec{D}[C],\vec{T})^{r_C}.\] Combining this with the previous inequality, and using that the two-element pairs \(\{C,\pi(C)\}\) partition \(\mathcal{C}^*\), gives \[\hom(\vec{F}_0,\vec{T}) \leq \hom(\vec{H},\vec{T})\, (1/2)^M \prod_{C\in\mathcal{C}}\hom(\vec{D}[C],\vec{T})^{r_C},\] where \[M:=\sum_{C\in\mathcal{C}^*} r_C.\] This number \(M\) is exactly the number of arcs of \(\vec{F}_0\) with one endpoint in the distinguished copy of \(V(\vec{H})\) and the other endpoint outside it.
We now use the partition from [eq:partition]. For each \(1\leq j\leq m\), let \[\vec{U}_j:=\vec{D}\left[\bigcup_{C\in\mathcal{C}_j}C\right],\] and let \(r_j\) be the common value of \(r_C=q\omega(C)\) for \(C\in\mathcal{C}_j\). Since \(\vec{U}_j\) is the disjoint union of the components \(\vec{D}[C]\) with \(C\in\mathcal{C}_j\), Lemma 1 gives \[\prod_{C\in\mathcal{C}_j}\hom(\vec{D}[C],\vec{T}) = \hom(\vec{U}_j,\vec{T}).\] Therefore \[\prod_{C\in\mathcal{C}}\hom(\vec{D}[C],\vec{T})^{r_C} = \prod_{j=1}^m \hom(\vec{U}_j,\vec{T})^{r_j}.\] By [eq:anti-Sidcomponents], each \(\vec{U}_j\) is tournament anti-Sidorenko. Hence \[\hom(\vec{U}_j,\vec{T}) \leq (1/2)^{a(\vec{U}_j)}n^{v(\vec{U}_j)}.\] Substituting this into the previous bound gives \[\hom(\vec{F}_0,\vec{T}) \leq \hom(\vec{H},\vec{T})\, (1/2)^M \prod_{j=1}^m \left((1/2)^{a(\vec{U}_j)}n^{v(\vec{U}_j)}\right)^{r_j}.\] Since the vertices in \(\vec{F}\setminus V(\vec{F}_0)\) are isolated, we get \[\hom(\vec{F},\vec{T}) \leq n^{v(\vec{F})-v(\vec{F}_0)} \hom(\vec{H},\vec{T})\, (1/2)^M \prod_{j=1}^m \left((1/2)^{a(\vec{U}_j)}n^{v(\vec{U}_j)}\right)^{r_j}.\]
Finally, observe that \[v(\vec{F})-v(\vec{H}) = v(\vec{F})-v(\vec{F}_0)+\sum_{j=1}^m r_jv(\vec{U}_j),\] and \[a(\vec{F})-a(\vec{H}) = M+\sum_{j=1}^m r_ja(\vec{U}_j).\] The first identity follows because \(\vec{F}_0\) consists of the distinguished copy of \(\vec{H}\) together with the non-isolated added components, while \(\vec{F}\setminus V(\vec{F}_0)\) consists exactly of the isolated vertices added in the sets \(L_v\). The second identity follows because the arcs of \(\vec{F}\) outside the distinguished copy of \(\vec{H}\) are exactly the internal arcs of the added components together with the \(M\) attachment arcs.
Thus \[\hom(\vec{F},\vec{T}) \leq (1/2)^{a(\vec{F})-a(\vec{H})} n^{v(\vec{F})-v(\vec{H})} \hom(\vec{H},\vec{T}),\] which is equivalent to 6 .
Since \(a(\vec{F})=(q+1)a(\vec{H})>a(\vec{H})\), the lower bound 4 and the upper bound 6 together show that \(\vec{F}\) satisfies the hypotheses of Lemma 1. Therefore Lemma 1 implies that \(\vec{H}\) is tournament anti-Sidorenko. ◻
5 Paths With Restricted Block Lengths↩︎
Our goal in this section is to prove Theorem 1 by exhibiting a sandwich for every oriented path \(\vec{P}\) in which every block has length at least two and every internal block has length divisible by four. Our strategy is to find \(\vec{P}_k\)-sandwiches for each \(k\in\{2,3,4,5\}\) with additional properties which allow us to “glue” them together to yield a sandwich for any such \(\vec{P}\). We start by presenting a special \(\vec{P}_4\)-sandwich that handles the internal blocks of \(\vec{P}\).
Construction 1. There exists a \(\vec{P}_4\)-sandwich \(\mathcal{S}_4^*=(\vec{D}_4^*,\psi_4^*,\omega_4^*,\pi_4^*)\) such that \(\mathop{\mathrm{cov}}_{\mathcal{S}_4^*}(v_0)=\mathop{\mathrm{cov}}_{\mathcal{S}_4^*}(v_4)=\frac{1}{2}\).
Proof. The oriented tree \(\vec{D}_4^*\) is shown in Figure 7 in Appendix 8. It is obtained from \(\vec{P}_4\) by adding
eight vertices \(u_0^+,u_1^0,u_2^-,u_3^2,u_1^2,u_2^+,u_3^4\) and \(u_4^-\), and
eight arcs \((u_0^+,v_1),(u_0^+,u_1^0),(v_1,u_2^-),(u_2^-,u_3^2),(u_1^2,u_2^+),(u_2^+,v_3),(v_3,u_4^-)\) and \((u_3^4,u_4^-)\).
The homomorphism \(\psi_4^*\) is obtained by mapping each vertex of \(\vec{D}_4^*\) to the vertex of \(\vec{P}_4\) with the same subscript. The weight function \(\omega_4^*\) assigns each component of \(\vec{D}_4^*\setminus V(\vec{P}_4)\) to weight \(1/2\). Finally, \(\pi_4^*\) is the involution on \(V(\vec{D}_4^*)\setminus V(\vec{P}_4)\) defined by \(\pi_4^*(u_0^+)=u_2^-, \pi_4^*(u_1^0)=u_3^2,\pi_4^*(u_1^2)=u_3^4\) and \(\pi_4^*(u_2^+)=u_4^-\). It is easily checked that \((\vec{D}_4^*,\psi_4^*,\omega_4^*,\pi_4^*)\) is a \(\vec{P}_4\)-sandwich and that \(\mathop{\mathrm{cov}}_{\mathcal{S}_4^*}(v_0)=\mathop{\mathrm{cov}}_{\mathcal{S}_4^*}(v_4)=\frac{1}{2}\). ◻
Next, we present \(\vec{P}_k\)-sandwiches for \(k\in\{2,3,5\}\). These are used for handling the extreme ends of the path in the proof of Theorem 1. Unlike the case \(k=4\), for these cases, we are only able to get the weight mapped to one (not two) of the endpoints to be at most \(1/2\).
Construction 1. For each \(k\in\{2,3,5\}\), there exists a \(\vec{P}_k\)-sandwich \(\mathcal{S}_k^*=(\vec{D}_k^*,\psi_k^*,\omega_k^*,\pi_k^*)\) such that \(\mathop{\mathrm{cov}}_{\mathcal{S}_k^*}(v_0)=\frac{1}{2}\).
Proof. First, consider \(k=2\). Let \(\vec{D}_2^*\) be the oriented forest depicted in Figure 8 in Appendix 8. It is obtained from \(\vec{P}_2\) by
adding five vertices \(u_0,u_1,u_1',u_2,u_2'\)
adding four arcs \((u_0,u_1),(u_0,u_1'),(u_1,u_2),(u_1',u_2')\).
The homomorphism \(\psi_2^*\) is obtained by mapping each vertex of \(\vec{D}_2^*\) to the vertex of \(\vec{P}_2\) with the same subscript. The weight function \(\omega_2^*\) assigns the unique component of \(\vec{D}_2^*\setminus V(\vec{P}_2)\) to weight \(1/2\). Finally, \(\pi_2^*\) is the identity function on \(V(\vec{D}_2^*)\setminus V(\vec{P}_2)\). All of the properties of Definition 1 are easily shown to hold for \((\vec{D}_2^*,\psi_2^*,\omega_2^*,\pi_2^*)\), where [eq:anti-Sidcomponents] holds by Proposition 1. Clearly, this construction satisfies \(\mathop{\mathrm{cov}}_{\mathcal{S}_2^*}(v_0)=\frac{1}{2}\).
Next, consider \(k=3\). Let \(\vec{D}_3^*\) be the oriented forest depicted in Figure 9 in Appendix 8. It is obtained from \(\vec{P}_3\) by
adding ten vertices \(u_0^+,u_1^0,u_2^-,u_3^2,u_1^+,u_3^-,w_1,w_2,w_2'\) and \(w_3'\), and
adding eight arcs \((u_0^+,v_1),(u_0^+,u_1^0),(v_1,u_2^-),(u_2^-,u_3^2),(u_1^+,v_2),(v_2,u_3^-),(w_1,w_2)\) and \((w_2',w_3')\).
The homomorphism \(\psi_3^*\) is obtained by mapping each vertex of \(\vec{D}_3^*\) to the vertex of \(\vec{P}_3\) with the same subscript. The weight function \(\omega_3^*\) assigns weight \(1/2\) to the components \(\{u_0^+,u_1^0\}\) and \(\{u_2^-,u_3^2\}\) of \(\vec{D}_3^*\setminus V(\vec{P}_3)\) and weight \(1/4\) to all other components. Finally, \(\pi_3^*\) is the involution on \(V(\vec{D}_3^*)\setminus V(\vec{P}_3)\) which fixes \(w_1,w_2,w_2'\) and \(w_3'\) and satisfies \(\pi_3^*(u_0^+)=u_2^-, \pi_3^*(u_1^0)=u_3^2,\pi_3^*(u_1^+)=u_3^-\). All of the properties of Definition 1 are easily shown to hold for \((\vec{D}_3^*,\psi_3^*,\omega_3^*,\pi_3^*)\). Clearly, this construction satisfies \(\mathop{\mathrm{cov}}_{\mathcal{S}_3^*}(v_0)=\frac{1}{2}\).
Finally, suppose that \(k=5\). Let \(\vec{D}_5^*\) be the oriented forest depicted in Figure 10 in Appendix 8. This construction is rather involved and so we will not describe all of the vertices and arcs added and simply refer to the picture.
The homomorphism \(\psi_5^*\) is obtained by mapping each vertex of \(\vec{D}_5^*\) to the vertex of \(\vec{P}_5\) with the same subscript. The weight function \(\omega_5^*\) assigns weight \(1/4\) to the components \(\{u_0^+,u_1^0\},\{u_2^-,u_3^2\},\{u_1^2,u_2^+\}\) and \(\{u_3^4,u_4^-\}\) of \(\vec{D}_5^*\setminus V(\vec{P}_5)\) and weight \(1/8\) to all other components. Let \(\pi_5^*\) be the involution on \(V(\vec{D}_5^*)\setminus V(\vec{P}_5)\) which fixes all twelve of the \(w\) vertices and satisfies \[(\pi_5^*(u_0^+),\pi_5^*(u_1^0),\pi_5^*(u_2^+),\pi_5^*(u_1^2)) = (u_2^-,u_3^2,u_4^-,u_3^4)\] and \[(\pi_5^*(z_1^+),\pi_5^*(z_2^1),\pi_5^*(z_3^1),\pi_5^*(z_0^+),\pi_5^*(z_1^0),\pi_5^*(z_2^0)) = (z_3^-,z_4^3,z_5^3,z_2^-,z_3^2,z_4^2).\] Clearly, this construction satisfies \(\mathop{\mathrm{cov}}_{\mathcal{S}_5^*}(v_0)=\frac{1}{2}\). All of the properties of Definition 1, apart from [eq:anti-Sidcomponents], are easily shown to hold for \((\vec{D}_5^*,\psi_5^*,\omega_5^*,\pi_5^*)\). To show that [eq:anti-Sidcomponents] holds, we observe that \(\vec{D}_5^*\setminus V(\vec{P}_5)\) has four 1-vertex components, four 2-vertex components and eight 3-vertex components, four of which are isomorphic to \(\vec{P}_2\) and four of which are isomorphic to \(\reflectbox{\vec{\reflectbox{P}}}_{1,1}\). Partition the components so that each component with one or two vertices is in its own partition class and there are four partition classes consisting of two 3-vertex components each, one of each type. The fact that [eq:anti-Sidcomponents] holds now follows from Proposition 1 and Lemma 1. ◻
We now prove Theorem 1.
Proof of Theorem 1. Let \(\vec{P}\) be an oriented path in which every block has length at least two and every internal block has length divisible by four. We can therefore divide \(\vec{P}\) into directed subpaths in which the first and last subpath have length \(2,3,4\) or \(5\) and all other subpaths have length \(4\).
We use Constructions 1 and 1 to build a \(\vec{P}\)-sandwich. Let the first and last subpaths have lengths \(k\) and \(\ell\), respectively. Thus \(k,\ell\in\{2,3,4,5\}\). For the first subpath, we use a copy of \(\vec{D}_k^*\) with the order of the path labels reversed, so that the low-cover endpoint lies at the gluing vertex. For the last subpath, we use a copy of \(\vec{D}_\ell^*\) with its usual labeling. For each subpath, if its orientation disagrees with the orientation of the corresponding subpath of \(\vec{P}\), then reverse all of its arcs. We then glue together these oriented forests by identifying the vertex \(v_k\) from the first subpath with the vertex \(v_0\) in the second, and so on.
The functions \(\psi,\omega\) and \(\pi\) are inherited from the constituent sandwiches in the natural way. Since each constituent is a sandwich, every arc of \(\vec{P}\) is covered with total weight \(1\). At every glued vertex, the two contributions to \(\mathop{\mathrm{cov}}\) are at most \(1/2\) each, by Constructions 1 and 1. All other vertices of the path are only covered by vertices within the unique sandwich that contains it. Thus the vertex-covering inequality [eq:coveredv] in Definition 1 holds, and all remaining properties are inherited from the constituent sandwiches. Hence \((\vec{D},\psi,\omega,\pi)\) is a \(\vec{P}\)-sandwich, and the theorem follows from Lemma 1. ◻
By combining Theorem 1 with the results of the previous section, we can now complete the proof of Theorem 1.
Proof of Theorem 1. Consider the path \(\vec{P}_{a,b}\) where \(a+b\geq3\). If \(a\geq2\) and \(b\geq2\), then \(\vec{P}_{a,b}\) is tournament anti-Sidorenko by Theorem 1.
So, we assume that \(a=1\) or \(b=1\). By reflecting the path if necessary and then applying Lemma 1, we may assume that \(a=1\) and \(b\geq2\). If \(b\in\{2,3,4\}\), then we are done by Proposition 1, 1 or 1, respectively. If \(b\geq5\), then we are done by Lemma 1 and the fact that we have already settled the cases in which \(a,b\geq2\) in the previous paragraph. Thus, the proof is complete. ◻
6 3-Spiders↩︎
In this section, we prove that every \(3\)-spider admits a tournament anti-Sidorenko orientation. The key input is Lemma 1 below, which supplies sandwiches for paths in which one prescribed internal vertex is covered by vertices of weight at most \(1/2\). We first use this lemma to prove Theorem 1. After that, the remainder of the section is devoted to the certificate constructions needed for Lemma 1. The proof of the lemma is a finite congruence-class analysis; each case is handled by one of the displayed certificates together with the four-block extension lemma below.
Lemma 1. Let \(k\geq4\) and \(2\leq a\leq k-2\). Suppose that one of the following holds:
\(k\equiv 0\bmod 4\) and \(a\equiv 0\bmod 4\).
\(k\equiv 0\bmod 4\) and \(a\equiv 2\bmod 4\).
\(k\equiv 2\bmod 4\) and \(a\equiv 1\bmod 4\).
\(k\equiv 2\bmod 4\) and \(a\equiv 3\bmod 4\).
\(k\equiv 3\bmod 4\) and \(a\equiv 0\bmod 4\).
\(k\equiv 3\bmod 4\) and \(a\equiv 1\bmod 4\).
Then there exists \(0\leq \ell\leq k-1\) and a \(\vec{P}_{k-\ell,\ell}\)-sandwich \(\mathcal{S}_k^a=(\vec{D}_{k}^a,\psi_{k}^a,\omega_{k}^a,\pi_{k}^a)\) such that \[\label{eq:covera}\mathop{\mathrm{cov}}_{\mathcal{S}_k^a}(v_a)\leq\frac{1}{2}.\qquad{(3)}\]
Proof of Theorem 1. Consider the \((a,b,c)\)-spider where \(a,b,c\geq1\). Note that, if any of \(a,b\) or \(c\) is equal to \(1\), then the spider is a caterpillar, and the result follows from [1]. So, we may assume that \(a,b,c\geq2\).
By the pigeonhole principle, at least two of \(a,b,c\) must be congruent to \(0\) or \(3\) modulo \(4\), or at least two of \(a,b,c\) must be congruent to \(1\) or \(2\) modulo \(4\). By symmetry, we assume that either \(a\) and \(b\) are both congruent to \(0\) or \(3\) or that both of \(a\) and \(b\) are congruent to \(1\) or \(2\). Define \(k=a+b\). After possibly swapping \(a\) and \(b\), for each of the six possible pairs of congruence classes of \(a\) and \(b\), the congruence classes for \(k\) and \(a\) fall into one of the cases listed in Lemma 1: namely \((a,b)=(0,0)\) gives [eq:00], \((0,3)\) gives [eq:30], \((3,3)\) gives [eq:23], \((1,1)\) gives [eq:21], \((1,2)\) gives [eq:31], and \((2,2)\) gives [eq:02]. Thus Lemma 1 gives a \(\vec{P}_{k-\ell,\ell}\)-sandwich \((\vec{D}_k^a,\psi_k^a,\omega_k^a,\pi_k^a)\) satisfying ?? for some \(0\leq \ell\leq k-1\). Since \(c\geq2\), we obtain a \(\vec{P}_c\)-sandwich \(\mathcal{S}_c=(\vec{D}_c,\psi_c,\omega_c,\pi_c)\) with the property that \(\mathop{\mathrm{cov}}_{\mathcal{S}_c}(v_0)\leq\frac{1}{2}\) by using one of Construction 1, for \(k\in\{2,3,5\}\), or Construction 1, according to the residue of \(c\bmod4\), and then gluing on copies of Construction 1. Thus, by taking the disjoint union of \(\vec{D}_k^a\) and \(\vec{D}_c\) and then identifying vertex \(v_a\) from \(\vec{D}_k^a\) with \(v_0\) from \(\vec{D}_c\), we get a sandwich for an orientation of the \((a,b,c)\)-spider. Thus, the proof is complete by Lemma 1. ◻
From here forward, we focus on the proof of Lemma 1.
6.1 Two “Repeating Block” Gadgets↩︎
We now turn our attention to proving Lemma 1. We start by presenting a gadget that is useful for extending existing constructions.
Construction 1. There exists a partial \(\vec{P}_4\)-sandwich \(\mathcal{S}_4^\dagger=(\vec{D}_4^\dagger,\psi_4^\dagger,\omega_4^\dagger,\pi_4^\dagger)\) such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_4^\dagger}(v_{i})= \begin{cases} 1/4&\text{if }i=0,\\ 3/4&\text{if }i\in\{1,3,4\},\\ 1&\text{if }i=2, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_4^\dagger}(e_i)= \begin{cases} 3/4&\text{if }i\in \{0,3\},\\ 1&\text{otherwise}. \end{cases}\]
Proof. The oriented graph \(\vec{D}_4^\dagger\) is shown in Figure 11 in Appendix 8. Each component of \(\vec{D}_4^\dagger\setminus V(\vec{P}_4)\) is assigned a weight of \(1/4\) by \(\omega_4^\dagger\). Summing the component weights gives the stated values of \(\mathop{\mathrm{cov}}_{\mathcal{S}_4^\dagger}\), and the verification of [eq:anti-Sidcomponents] uses Proposition 1. ◻
The key property of the construction in the previous proposition is that multiple copies of it can be “chained together” to get a partial sandwich of a longer path. The next proposition makes this more precise.
Construction 1. For each \(t\geq1\), there exists a partial \(\vec{P}_{4t}\)-sandwich \[\mathcal{S}_{4t}^\ddag=(\vec{D}_{4t}^\ddag,\psi_{4t}^\ddag,\omega_{4t}^\ddag,\pi_{4t}^\ddag)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_{4t}^\ddag}(v_{i})= \begin{cases} 1/4&\text{if }i=0,\\ 3/4&\text{if }i\in\{1,4t-1,4t\},\\ 1&\text{otherwise}, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{4t}^\ddag}(e_i)= \begin{cases} 3/4&\text{if }i\in\{0,4t-1\},\\ 1&\text{otherwise}. \end{cases}\]
Proof. The construction of \(\vec{D}_{4t}^\ddag\) is as follows. Take \(t\) disjoint copies of the oriented forest \(\vec{D}_4^\dagger\) from Construction 1 and identify the vertex corresponding to \(v_4\) in each of the first \(t-1\) copies with the vertex corresponding to \(v_0\) in the next copy. Note that the copies of \(\vec{P}_4\) in the copies of \(\vec{D}_{4t}^\ddag\) now form a copy of \(\vec{P}_{4t}\); relabel these vertices \(v_0,\dots,v_{4t}\) in the order that they come on the path. Next, for each \(1\leq j\leq t-1\), add two vertices \(y_{4j-1}^+\) and \(y_{4j+1}^-\) and arcs \((y_{4j-1}^+,v_{4j})\) and \((v_{4j},y_{4j+1}^-)\). See Figure 12 in Appendix 8 for a depiction of this in the case \(t=3\). All components of \(\vec{D}_{4t}^\ddag\setminus V(\vec{P}_{4t})\) are assigned weight \(1/4\). The functions \(\psi_{4t}^\ddag,\omega_{4t}^\ddag\) and \(\pi_{4t}^\ddag\) are inherited from \(\psi_4^\dagger,\omega_4^\dagger\) and \(\pi_4^\dagger\) in the natural way, where \(\pi_{4t}^\ddag(y_{4j-1}^+)=y_{4j+1}^-\) for all \(1\leq j\leq t-1\). ◻
The preceding construction will be used to extend existing constructions via the following lemmas. Throughout the rest of this section, if an oriented path has vertices \(v_0,\dots,v_k\), then \(e_i\) denotes the arc of the path with endpoints \(v_i\) and \(v_{i+1}\), with its actual orientation.
Lemma 1. Let \(\vec{Q}\) be an oriented path with vertices \(v_0,\dots,v_k\), and let \(\mathcal{S}=(\vec{D},\psi,\omega,\pi)\) be a partial \(\vec{Q}\)-sandwich. If \[\mathop{\mathrm{cov}}_{\mathcal{S}}(v_{k-1})\leq 3/4, \quad \mathop{\mathrm{cov}}_{\mathcal{S}}(v_{k})\leq 3/4, \quad\mathop{\mathrm{cov}}_{\mathcal{S}}(e_{k-1})=3/4,\] then, for all \(t\geq0\), there exists a partial sandwich \(\mathcal{S}_{+4t}=(\vec{D}_{+4t},\psi_{+4t},\omega_{+4t},\pi_{+4t})\) for the path obtained from \(\vec{Q}\) by extending the right endpoint by a directed block of length \(4t\) such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(v_{i})=\mathop{\mathrm{cov}}_{\mathcal{S}}(v_{i})\text{ for all }0\leq i\leq k-2,\] \[\mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(e_i)=\mathop{\mathrm{cov}}_{\mathcal{S}}(e_i)\text{ for all }0\leq i\leq k-2,\] \[\mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(v_{k-1})=\mathop{\mathrm{cov}}_{\mathcal{S}}(v_{k-1})+1/4,\quad \mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(v_{k})=\mathop{\mathrm{cov}}_{\mathcal{S}}(v_{k})+1/4,\quad \mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(e_{k-1})=1,\] \[\mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(v_{i})=1\text{ for all }k+1\leq i\leq k+4t,\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(e_i)=1\text{ for all }k\leq i\leq k+4t-1.\]
Proof. Without loss of generality, we can assume \(e_{k-1}=(v_{k-1},v_k)\), as the case \(e_{k-1}=(v_k,v_{k-1})\) is obtained by reversing all arcs in the construction below.
First suppose that \(t=0\). Let \(r_{k-1}\) and \(r_k\) be two new vertices, and add the arc \((r_{k-1},r_k)\). Define \[\psi_{+0}(r_{k-1})=v_{k-1} \qquad\text{and}\qquad \psi_{+0}(r_k)=v_k.\] We assign the component \(\{r_{k-1},r_k\}\) to weight \(1/4\), and let \(\pi_{+0}\) fix both \(r_{k-1}\) and \(r_k\). On all vertices and components already present in \(\vec{D}\), let \(\psi_{+0},\omega_{+0}\) and \(\pi_{+0}\) agree with \(\psi,\omega\) and \(\pi\). The new disjoint arc contributes \(1/4\) to the cover of \(v_{k-1}\), \(v_k\) and \(e_{k-1}\), and changes no other covers. This proves the result when \(t=0\).
Now assume that \(t\geq1\). Let \(\mathcal{S}_{4t}^{\ddag} = (\vec{D}_{4t}^{\ddag},\psi_{4t}^{\ddag},\omega_{4t}^{\ddag},\pi_{4t}^{\ddag})\) be the partial \(\vec{P}_{4t}\)-sandwich from Construction 1. Form a new oriented graph by taking the disjoint union of \(\vec{D}\) and this copy of \(\vec{D}_{4t}^{\ddag}\). On the copy of \(\vec{D}_{4t}^{\ddag}\), relabel the vertices on its central path by \(v_k,v_{k+1},\dots,v_{k+4t}\) and then identify the vertex \(v_k\) in \(\vec{D}\) with the vertex that is now labeled \(v_k\) in \(\vec{D}_{4t}^{\ddag}\).
Next add two new one-vertex components \(p_{k-1}\) and \(p_{k+1}\), each of weight \(1/4\), with \[\psi_{+4t}(p_{k-1})=v_{k-1} \qquad\text{and}\qquad \psi_{+4t}(p_{k+1})=v_{k+1}.\] Add the two attachment arcs \[(p_{k-1},v_k) \qquad\text{and}\qquad (v_k,p_{k+1}).\] Finally, add two new vertices \(r_{k+4t-1}\) and \(r_{k+4t}\), with \[\psi_{+4t}(r_{k+4t-1})=v_{k+4t-1} \qquad\text{and}\qquad \psi_{+4t}(r_{k+4t})=v_{k+4t},\] and add the disjoint arc \[(r_{k+4t-1},r_{k+4t}).\] Give the component \(\{r_{k+4t-1},r_{k+4t}\}\) weight \(1/4\).
We now define the maps and weights. On the original copy of \(\vec{D}\), set \[\psi_{+4t}=\psi,\qquad \omega_{+4t}=\omega,\qquad \pi_{+4t}=\pi.\] On the copy of \(\vec{D}_{4t}^{\ddag}\), use \(\psi_{4t}^{\ddag},\omega_{4t}^{\ddag}\) and \(\pi_{4t}^{\ddag}\), where the domains of these functions are adjusted to account for the fact that the vertices of \(\vec{D}_{4t}^{\ddag}\) have been relabeled \(v_k,\dots,v_{k+4t}\). On the newly added one-vertex components, set \[\pi_{+4t}(p_{k-1})=p_{k+1} \qquad\text{and}\qquad \pi_{+4t}(p_{k+1})=p_{k-1}.\] On the final disjoint arc component, set \[\pi_{+4t}(r_{k+4t-1})=r_{k+4t-1} \qquad\text{and}\qquad \pi_{+4t}(r_{k+4t})=r_{k+4t}.\]
It remains to check the covers. On the old part of the path away from the right endpoint, nothing has changed, so \[\mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(v_i)=\mathop{\mathrm{cov}}_{\mathcal{S}}(v_i) \quad\text{for all }0\leq i\leq k-2,\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(e_i)=\mathop{\mathrm{cov}}_{\mathcal{S}}(e_i) \quad\text{for all }0\leq i\leq k-2.\] The vertex \(p_{k-1}\) contributes \(1/4\) to the cover of \(v_{k-1}\), while the copy of \(\vec{D}_{4t}^{\ddag}\) contributes \(1/4\) to the cover of \(v_k\), since \[\mathop{\mathrm{cov}}_{\mathcal{S}_{4t}^{\ddag}}(v_0)=1/4\] by Construction 1. Therefore \[\mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(v_{k-1}) = \mathop{\mathrm{cov}}_{\mathcal{S}}(v_{k-1})+1/4\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(v_k) = \mathop{\mathrm{cov}}_{\mathcal{S}}(v_k)+1/4.\] The arc \((p_{k-1},v_k)\) maps under \(\psi_{+4t}\) to \((v_{k-1},v_k)=e_{k-1}\), so it supplies the missing \(1/4\) on \(e_{k-1}\). Hence \[\mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(e_{k-1})=1.\]
For the added block, Construction 1 gives cover \(3/4\) at the vertices \(v_{k+1},v_{k+4t-1}\) and \(v_{k+4t}\), and cover \(1\) at all other new vertices. The component \(p_{k+1}\) contributes \(1/4\) to \(v_{k+1}\), while the final disjoint arc component contributes \(1/4\) to both \(v_{k+4t-1}\) and \(v_{k+4t}\). Thus \[\mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(v_i)=1 \quad\text{for all }k+1\leq i\leq k+4t.\] Similarly, Construction 1 gives cover \(3/4\) on the first and last arcs of the added block and cover \(1\) on all other arcs of the added block. The arc \((v_k,p_{k+1})\) maps under \(\psi_{+4t}\) to \((v_k,v_{k+1})=e_k\), so it supplies the missing \(1/4\) on \(e_k\). The disjoint arc \((r_{k+4t-1},r_{k+4t})\) maps to \(e_{k+4t-1}\), so it supplies the missing \(1/4\) on the last arc of the added block. Hence \[\mathop{\mathrm{cov}}_{\mathcal{S}_{+4t}}(e_i)=1 \quad\text{for all }k\leq i\leq k+4t-1.\]
Finally, all remaining properties of a partial sandwich are inherited from \(\mathcal{S}\) and Construction 1, together with the definitions above. The two one-vertex components \(p_{k-1}\) and \(p_{k+1}\) are paired by \(\pi_{+4t}\), have the same weight, and their attachment arcs are reversed around the path vertex \(v_k\). The final two-vertex component is disjoint from the path and is fixed by \(\pi_{+4t}\). The new components are either isolated vertices or a directed arc, and hence satisfy the required anti-Sidorenko component condition. Therefore \[\mathcal{S}_{+4t} = (\vec{D}_{+4t},\psi_{+4t},\omega_{+4t},\pi_{+4t})\] is the desired partial sandwich. ◻
The next lemma is proved in the same way as Lemma 1, applied at the left endpoint instead of the right endpoint. Equivalently, one may reverse the order of the vertices of the path, apply Lemma 1, and then reverse the order back.
Lemma 1. Let \(\vec{Q}\) be an oriented path with vertices \(v_0,\dots,v_k\), and let \(\mathcal{S}=(\vec{D},\psi,\omega,\pi)\) be a partial \(\vec{Q}\)-sandwich. If \[\mathop{\mathrm{cov}}_{\mathcal{S}}(v_0)\leq 3/4, \quad \mathop{\mathrm{cov}}_{\mathcal{S}}(v_1)\leq 3/4, \quad\mathop{\mathrm{cov}}_{\mathcal{S}}(e_0)=3/4,\] then, for all \(t\geq0\), there exists a partial sandwich \(\mathcal{S}_{-4t}=(\vec{D}_{-4t},\psi_{-4t},\omega_{-4t},\pi_{-4t})\) for the path obtained from \(\vec{Q}\) by extending the left endpoint by a directed block of length \(4t\) such that, after relabeling the old vertex \(v_i\) as \(v_{i+4t}\), \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4t}}(v_i)=1\text{ for all }0\leq i\leq 4t-1,\] \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4t}}(e_i)=1\text{ for all }0\leq i\leq 4t-1,\] \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4t}}(v_{4t})=\mathop{\mathrm{cov}}_{\mathcal{S}}(v_0)+1/4,\quad \mathop{\mathrm{cov}}_{\mathcal{S}_{-4t}}(v_{4t+1})=\mathop{\mathrm{cov}}_{\mathcal{S}}(v_1)+1/4,\quad \mathop{\mathrm{cov}}_{\mathcal{S}_{-4t}}(e_{4t})=1,\] \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4t}}(v_{i+4t})=\mathop{\mathrm{cov}}_{\mathcal{S}}(v_i)\text{ for all }2\leq i\leq k,\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4t}}(e_{i+4t})=\mathop{\mathrm{cov}}_{\mathcal{S}}(e_i)\text{ for all }1\leq i\leq k-1.\]
The next lemma is obtained by applying Lemmas 1 and 1 on the left and right side, respectively.
Lemma 1. Let \(\vec{Q}\) be an oriented path with vertices \(v_0,\dots,v_k\), and let \(\mathcal{S}=(\vec{D},\psi,\omega,\pi)\) be a partial \(\vec{Q}\)-sandwich. If \[\mathop{\mathrm{cov}}_{\mathcal{S}}(v_0)\leq 3/4, \quad \mathop{\mathrm{cov}}_{\mathcal{S}}(v_1)\leq 3/4, \quad\mathop{\mathrm{cov}}_{\mathcal{S}}(e_0)=3/4,\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}}(v_{k-1})\leq 3/4, \quad \mathop{\mathrm{cov}}_{\mathcal{S}}(v_k)\leq 3/4, \quad\mathop{\mathrm{cov}}_{\mathcal{S}}(e_{k-1})=3/4,\] then, for all \(s,t\geq0\), there exists a partial sandwich \[\mathcal{S}_{-4s,+4t}=(\vec{D}_{-4s,+4t},\psi_{-4s,+4t},\omega_{-4s,+4t},\pi_{-4s,+4t})\] for the path obtained from \(\vec{Q}\) by extending the left endpoint by a directed block of length \(4s\) and the right endpoint by a directed block of length \(4t\) such that, after relabeling the old vertex \(v_i\) as \(v_{i+4s}\), \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4s,+4t}}(v_i)=1\text{ for all }0\leq i\leq 4s-1,\] \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4s,+4t}}(e_i)=1\text{ for all }0\leq i\leq 4s-1,\] \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4s,+4t}}(v_{4s})=\mathop{\mathrm{cov}}_{\mathcal{S}}(v_0)+1/4,\quad \mathop{\mathrm{cov}}_{\mathcal{S}_{-4s,+4t}}(v_{4s+1})=\mathop{\mathrm{cov}}_{\mathcal{S}}(v_1)+1/4,\quad \mathop{\mathrm{cov}}_{\mathcal{S}_{-4s,+4t}}(e_{4s})=1,\] \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4s,+4t}}(v_{i+4s})=\mathop{\mathrm{cov}}_{\mathcal{S}}(v_i)\text{ for all }2\leq i\leq k-2,\] \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4s,+4t}}(e_{i+4s})=\mathop{\mathrm{cov}}_{\mathcal{S}}(e_i)\text{ for all }1\leq i\leq k-2,\] \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4s,+4t}}(v_{k+4s-1})=\mathop{\mathrm{cov}}_{\mathcal{S}}(v_{k-1})+1/4,\quad \mathop{\mathrm{cov}}_{\mathcal{S}_{-4s,+4t}}(v_{k+4s})=\mathop{\mathrm{cov}}_{\mathcal{S}}(v_k)+1/4,\quad \mathop{\mathrm{cov}}_{\mathcal{S}_{-4s,+4t}}(e_{k+4s-1})=1,\] \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4s,+4t}}(v_i)=1\text{ for all }k+4s+1\leq i\leq k+4s+4t,\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{-4s,+4t}}(e_i)=1 \text{ for all }k+4s\leq i\leq k+4s+4t-1.\]
Next, we present a second repeating block gadget and then we show how they can be chained together.
Construction 1. There exists a partial \(\reflectbox{\vec{\reflectbox{P}}}_4\)-sandwich \[\mathcal{S}_4^\mid=(\vec{D}_4^\mid,\psi_4^\mid,\omega_4^\mid,\pi_4^\mid)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_4^\mid}(v_{i})= \begin{cases} 1/5&\text{if }i=0,\\ 4/5&\text{if }i=2,\\ 3/5&\text{otherwise}, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_4^\mid}(v_{i+1},v_i)= \begin{cases} 1&\text{if }i=1,\\ 3/5&\text{otherwise}. \end{cases}\]
Proof. The oriented graph \(\vec{D}_4^\mid\) is shown in Figure 13 in Appendix 8. Each component of \(\vec{D}_4^\mid\setminus V(\reflectbox{\vec{\reflectbox{P}}}_4)\) is assigned a weight of \(1/5\) by \(\omega_4^\mid\). Summing the indicated component weights gives the stated values of \(\mathop{\mathrm{cov}}\), and the verification of [eq:anti-Sidcomponents] uses Proposition 1. ◻
Construction 1. For each \(t\geq1\), there exists a partial \(\reflectbox{\vec{\reflectbox{P}}}_{4t}\)-sandwich \[\mathcal{S}_{4t}^\parallel=(\vec{D}_{4t}^\parallel,\psi_{4t}^\parallel,\omega_{4t}^\parallel,\pi_{4t}^\parallel)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_{4t}^\parallel}(v_{i})= \begin{cases} 1/5&\text{if }i=0,\\ 3/5&\text{if }i\in\{1,4t-1,4t\},\\ 4/5&\text{if }i=4t-2,\\ 1&\text{otherwise}, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{4t}^\parallel}(v_{i+1},v_i)= \begin{cases} 3/5&\text{if }i=0,\\ 1&\text{otherwise}. \end{cases}\]
Proof. The construction of \(\vec{D}_{4t}^\parallel\) is as follows. Take \(t\) disjoint copies of the oriented forest \(\vec{D}_4^\mid\) from Construction 1 and identify the vertex corresponding to \(v_4\) in each of the first \(t-1\) copies with the vertex corresponding to \(v_0\) in the next copy. Note that the copies of \(\reflectbox{\vec{\reflectbox{P}}}_4\) in the copies of \(\vec{D}_{4t}^\parallel\) now form a copy of \(\reflectbox{\vec{\reflectbox{P}}}_{4t}\); relabel these vertices \(v_0,\dots,v_{4t}\) in the order that they come on the path. Next, for each \(1\leq j\leq t-1\), add two vertices \(y_{4j-1}^+\) and \(y_{4j+1}^-\) and arcs \((y_{4j-1}^+,v_{4j})\) and \((v_{4j},y_{4j+1}^-)\). Also, for each \(1\leq j\leq t-1\), add four vertices \(z_{4j-2}^+,z_{4j-1}^{4j-2},z_{4j}^-\) and \(z_{4j+1}^{4j}\) and four arcs \((v_{4j-1},z_{4j-2}^+),(z_{4j-1}^{4j-2},z_{4j-2}^+),(z_{4j}^-,v_{4j-1})\) and \((z_{4j+1}^{4j},z_{4j}^-)\). See Figure 14 in Appendix 8 for a depiction of this in the case \(t=3\). All components of \(\vec{D}_{4t}^\parallel\setminus V(\reflectbox{\vec{\reflectbox{P}}}_{4t})\) are assigned weight \(1/5\). The functions \(\psi_{4t}^\parallel,\omega_{4t}^\parallel\) and \(\pi_{4t}^\parallel\) are inherited from \(\psi_4^\mid,\omega_4^\mid\) and \(\pi_4^\mid\) in the natural way, where \[\pi_{4t}^\parallel(z_{4j-2}^+)=z_{4j}^-, \qquad \pi_{4t}^\parallel(z_{4j-1}^{4j-2})=z_{4j+1}^{4j}\] for all \(1\leq j\leq t-1\). ◻
In the next six subsections, we prove the six cases of Lemma 1, one by one.
6.2 Case [eq:00] of Lemma 1↩︎
We consider the first case of Lemma 1: \(k\equiv 0\bmod 4\) and \(a\equiv 0\bmod 4\). We exhibit a partial \(\vec{P}_8\)-sandwich which is used with Lemma 1 to deal with this case. Recall that, throughout this section, \(e_i\) is the arc between \(v_i\) and \(v_{i+1}\), in one direction or the other.
Construction 1. There exists a partial \(\vec{P}_8\)-sandwich \[\mathcal{S}_8^\S=(\vec{D}_8^\S,\psi_8^\S,\omega_8^\S,\pi_8^\S)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_8^\S}(v_{i})= \begin{cases} 1/2&\text{if }i=4,\\ 3/4&\text{if }i\in\{0,1,7,8\},\\ 1&\text{otherwise}, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_8^\S}(e_i)= \begin{cases} 3/4&\text{if }i\in \{0,7\},\\ 1&\text{otherwise}. \end{cases}\]
Proof. The oriented graph \(\vec{D}_8^\S\) is shown in Figure 15 in Appendix 8. Each component of \(\vec{D}_8^\S\setminus V(\vec{P}_8)\) is assigned a weight of \(1/4\) by \(\omega_8^\S\). Summing the indicated component weights gives the stated values of \(\mathop{\mathrm{cov}}\), and the verification of [eq:anti-Sidcomponents] uses Proposition 1. ◻
Proof of Lemma 1 [eq:00]. Let \(k\) and \(a\) be such that \(2\leq a\leq k-2\), \(k\equiv0\bmod4\) and \(a\equiv0\bmod4\). Thus \(4\leq a\leq k-4\) and \(k\geq8\). Start with the partial sandwich \(\mathcal{S}_8^\S\) from Construction 1. Its distinguished vertex is \(v_4\), and it has the endpoint cover pattern required by Lemma 1 at both endpoints.
Extend this certificate to the left by \(a-4\) arcs and to the right by \(k-a-4\) arcs using Lemma 1. After relabeling the central path as \(v_0,\dots,v_k\), the vertex \(v_4\) of the original copy of \(\vec{D}_8^\S\) becomes \(v_a\). The extension lemma shows that all arc covers are equal to \(1\) and all vertex covers are at most \(1\), while the cover of this distinguished vertex remains \(1/2\). Thus the resulting tuple is the desired sandwich satisfying ?? . ◻
6.3 Case [eq:02] of Lemma 1↩︎
Next, we tackle the second case of Lemma 1: \(k\equiv 0\bmod 4\) and \(a\equiv 2\bmod 4\). For this, we require separate constructions for the case that \((k,a)=(4,2)\), that \(a\in\{2,k-2\}\) and \(k\geq8\), or that \(a\notin\{2,k-2\}\).
Construction 1. There exists a partial \(\vec{P}_{1,3}\)-sandwich \[\mathcal{S}_{1,3}^\S=(\vec{D}_{1,3}^\S,\psi_{1,3}^\S,\omega_{1,3}^\S,\pi_{1,3}^\S)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_{1,3}^\S}(v_{i})= \begin{cases} 0&\text{if }i=2,\\ 1&\text{otherwise}, \end{cases}\] and \(\mathop{\mathrm{cov}}_{\mathcal{S}_{1,3}^\S}(e_i)=1\) for all \(0\leq i\leq3\).
Proof. The oriented graph \(\vec{D}_{1,3}^\S\) is shown in Figure 16 in Appendix 8. Each component of \(\vec{D}_{1,3}^\S\setminus V(\vec{P}_{1,3})\) is assigned a weight of \(1\) by \(\omega_{1,3}^\S\). Summing the indicated component weights gives the stated values of \(\mathop{\mathrm{cov}}\). ◻
Construction 1. There exists a partial \(\vec{P}_{3,5}\)-sandwich \[\mathcal{S}_{3,5}^\S=(\vec{D}_{3,5}^\S,\psi_{3,5}^\S,\omega_{3,5}^\S,\pi_{3,5}^\S)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_{3,5}^\S}(v_{i})= \begin{cases} 3/8&\text{if }i=2,\\ 3/4&\text{if }i\in\{7,8\},\\ 1&\text{otherwise}, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{3,5}^\S}(e_i)= \begin{cases} 3/4&\text{if }i=7,\\ 1&\text{otherwise}. \end{cases}\]
Proof. The oriented graph \(\vec{D}_{3,5}^\S\) is shown in Figure 17 in Appendix 8. Each component of \(\vec{D}_{3,5}^\S\setminus V(\vec{P}_{3,5})\) is assigned a weight of \(1/8,2/8,3/8\) or \(5/8\) by \(\omega_{3,5}^\S\), as indicated in the figure. Summing the indicated component weights gives the stated values of \(\mathop{\mathrm{cov}}\) and the verification of [eq:anti-Sidcomponents] uses Proposition 1 and Proposition 1. ◻
Construction 1. Let \(a\geq6\) such that \(a\equiv 2\bmod 4\). There exists a partial \(\vec{P}_{a-1,a+1}\)-sandwich \[\mathcal{S}_{a-1,a+1}^\S=(\vec{D}_{a-1,a+1}^\S,\psi_{a-1,a+1}^\S,\omega_{a-1,a+1}^\S,\pi_{a-1,a+1}^\S)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_{a-1,a+1}^\S}(v_{i})= \begin{cases} 3/4&\text{if }i\in\{0,1\},\\ 1/2&\text{if }i=a,\\ 1&\text{otherwise}, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{a-1,a+1}^\S}(e_i)= \begin{cases} 3/4&\text{if }i=0,\\ 1&\text{otherwise}. \end{cases}\]
Proof. Write \(a=4t+2\), where \(t\geq 1\). The construction is shown in Figure 18 in Appendix 8 in the case \(a=10\) (i.e. \(t=2\)). The general construction is obtained from the same diagram by extending the repeated \(4\)-edge gadgets on the left and on the right. More precisely, the left side consists of the initial two one-vertex components of weight \(5/54\) and a disjoint arc of weight \(1/36\), followed by \(t\) copies of the \(\vec{D}_4^\dagger\)-type gadget used in Construction 1, each component of which has weight \(5/54\), linked by the one-vertex connector components of weight \(5/54\), as in the proof of Construction 1. The right side is obtained analogously using \(\vec{D}_4^\mid\)-type gadgets similar to the proof of Construction 1, where every component has weight \(4/54\), and there is a disjoint copy of \(\vec{P}_{2,2}\) of weight \(4/54\) at the end. The central part of the construction is the part of the diagram around the columns \(a-2,a-1,a,a+1,a+2,a+3\) depicted in blue in the diagram; it is unchanged, up to translating the indices. Finally, there are two copies of \(\vec{P}_{a-1,a-1}\) where the first copy has its leaves in column \(0\) and centre vertex in column \(a-1\) and the second has its leaves in column \(2a\) and centre vertex in column \(a+1\). There is an arc from \(v_a\) to the centre vertex of the first copy and an arc from the centre vertex of the second copy to \(v_a\). These paths receive weight \(17/54\) and arcs are depicted in red in the figure.
Let \(\vec{D}_{a-1,a+1}^\S\) be the resulting oriented forest. We define \(\psi_{a-1,a+1}^\S:\vec{D}_{a-1,a+1}^\S\to \vec{P}_{a-1,a+1}\) by sending every vertex drawn in column \(i\) to \(v_i\); in particular, \(\psi_{a-1,a+1}^\S\) fixes the copy of \(\vec{P}_{a-1,a+1}\). The weight function \(\omega_{a-1,a+1}^\S\) assigns to each component of \(\vec{D}_{a-1,a+1}^\S\setminus V(\vec{P}_{a-1,a+1})\) the weight indicated on that component in the figure. The involution \(\pi_{a-1,a+1}^\S\) pairs the components in the evident way: each component attached to the path by an outgoing arc is paired with an isomorphic component of the same weight attached by the reversed incoming arc.
It is immediate from the construction that \(\psi_{a-1,a+1}^\S\) is a homomorphism and that \(\pi_{a-1,a+1}^\S\) satisfies the required reversal condition for arcs between the path and the components. Also, every component of \(\vec{D}_{a-1,a+1}^\S\setminus V(\vec{P}_{a-1,a+1})\) has at most one arc to the path. The verification of [eq:anti-Sidcomponents] uses Proposition 1, Proposition 1, and Lemma 1, exactly as in the preceding constructions. It also uses Theorem 1, which ensures that \(\vec{P}_{a-1,a-1}\) is anti-Sidorenko.
Summing the indicated weights column by column gives the stated values of \(\mathop{\mathrm{cov}}\). The repeated \(4\)-edge gadgets contribute total weight \(1\) to every internal vertex and arc in their range, the central components contribute total vertex-cover \(1/2\) in column \(a\), and the red rail components supply the missing cover near the two ends. This proves that \(\mathcal{S}_{a-1,a+1}^\S\) is the desired partial \(\vec{P}_{a-1,a+1}\)-sandwich. ◻
Using the constructions described in this section, we prove Lemma 1 [eq:02].
Proof of Lemma 1 [eq:02]. Let \(k\equiv0\bmod4\) and \(a\equiv2\bmod4\), where \(2\leq a\leq k-2\). If \(k=4\) and \(a=2\), then Construction 1 gives the desired sandwich.
Suppose next that one of \(a\) and \(k-a\) is equal to \(2\). By reversing the labels on the central path if necessary, we may assume that \(a=2\). Start with the partial sandwich \(\mathcal{S}_{3,5}^\S\) from Construction 1. The distinguished vertex is \(v_2\), and the right endpoint has the cover pattern required by Lemma 1. Extend to the right by \(k-8\) arcs using Lemma 1. The distinguished vertex remains \(v_2\), so ?? holds.
It remains to consider the case \(6\leq a\leq k-6\). By reversing the labels on the central path if necessary, we may assume that \(a\geq k/2\). Put \(b:=k-a\). Then \(b\equiv2\bmod4\) and \(b\geq6\). Start with the partial sandwich \(\mathcal{S}_{b-1,b+1}^\S\) from Construction 1; its distinguished vertex is the vertex in column \(b\). Extend this certificate to the left by \(a-b\) arcs using Lemma 1. After relabeling, the distinguished vertex is \(v_a\). The extension lemma preserves the stated cover at the distinguished vertex and fills all newly created arcs, so the resulting tuple is the desired sandwich satisfying ?? . ◻
6.4 Case [eq:21] of Lemma 1↩︎
Next, we obtain a construction that is useful for the third case of Lemma 1.
Construction 1. There exists a partial \(\vec{P}_{10}\)-sandwich \[\mathcal{S}_{10}^\S=(\vec{D}_{10}^\S,\psi_{10}^\S,\omega_{10}^\S,\pi_{10}^\S)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_{10}^\S}(v_{i})= \begin{cases} 1/2&\text{if }i=5,\\ 3/4&\text{if }i\in\{0,1,9,10\},\\ 1&\text{otherwise}, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{10}^\S}(e_i)= \begin{cases} 3/4&\text{if }i\in \{0,9\},\\ 1&\text{otherwise}. \end{cases}\]
Proof. The oriented graph \(\vec{D}_{10}^\S\) is shown in Figure 19 in Appendix 8. Each component of \(\vec{D}_{10}^\S\setminus V(\vec{P}_{10})\) is assigned a weight of \(1/4\) by \(\omega_{10}^\S\) except for \(\{y_4^+\}\) and \(\{y_6^-\}\) which have weight \(1/2\). Summing the indicated component weights gives the stated values of \(\mathop{\mathrm{cov}}\) and the verification of [eq:anti-Sidcomponents] uses Proposition 1. ◻
Proof of Lemma 1 [eq:21]. Let \(k\equiv2\bmod4\) and \(a\equiv1\bmod4\), where \(2\leq a\leq k-2\). Then \(a\geq5\) and \(k-a\geq5\). Start with the partial sandwich \(\mathcal{S}_{10}^\S\) from Construction 1. Its distinguished vertex is \(v_5\), and it has the endpoint cover pattern required by Lemma 1 at both endpoints.
Extend this certificate to the left by \(a-5\) arcs and to the right by \(k-a-5\) arcs using Lemma 1. After relabeling the central path as \(v_0,\dots,v_k\), the vertex \(v_5\) of the original copy of \(\vec{D}_{10}^\S\) becomes \(v_a\). Thus the distinguished vertex has cover \(1/2\), all arc covers are equal to \(1\), and all vertex covers are at most \(1\). This gives the desired sandwich. ◻
6.5 Case [eq:23] of Lemma 1↩︎
Next, we present two constructions that are used to establish the fourth case of Lemma 1.
Construction 1. There exists a partial \(\vec{P}_{2,4}\)-sandwich \[\mathcal{S}_{2,4}^\S=(\vec{D}_{2,4}^\S,\psi_{2,4}^\S,\omega_{2,4}^\S,\pi_{2,4}^\S)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_{2,4}^\S}(v_{i})= \begin{cases} 1/2&\text{if }i=3,\\ 3/4&\text{if }i\in\{0,1\},\\ 1&\text{otherwise}, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{2,4}^\S}(e_i)= \begin{cases} 3/4&\text{if }i=0,\\ 1&\text{otherwise}. \end{cases}\]
Proof. The oriented graph \(\vec{D}_{2,4}^\S\) is shown in Figure 20 in Appendix 8. Each component of \(\vec{D}_{2,4}^\S\setminus V(\vec{P}_{2,4})\) is assigned a weight of \(1/4\) by \(\omega_{2,4}^\S\). Summing the indicated component weights gives the stated values of \(\mathop{\mathrm{cov}}\) and the verification of [eq:anti-Sidcomponents] uses Proposition 1. ◻
Construction 1. There exists a partial \(\vec{P}_{4,4,6}\)-sandwich \[\mathcal{S}_{4,4,6}^\S=(\vec{D}_{4,4,6}^\S,\psi_{4,4,6}^\S,\omega_{4,4,6}^\S,\pi_{4,4,6}^\S)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_{4,4,6}^\S}(v_{i})= \begin{cases} 1/2&\text{if }i=7,\\ 3/4&\text{if }i\in\{0,1,13,14\},\\ 1&\text{otherwise}, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{4,4,6}^\S}(e_i)= \begin{cases} 3/4&\text{if }i\in\{0,13\},\\ 1&\text{otherwise}. \end{cases}\]
Proof. The oriented graph \(\vec{D}_{4,4,6}^\S\) is shown in Figure 21 in Appendix 8. Each component of \(\vec{D}_{4,4,6}^\S\setminus V(\vec{P}_{4,4,6})\) is assigned a weight of \(1/16,2/16\) or \(4/16\) by \(\omega_{4,4,6}^\S\), as indicated in the figure. Summing the indicated component weights gives the stated values of \(\mathop{\mathrm{cov}}\) and the verification of [eq:anti-Sidcomponents] uses Propositions 1 and 1. ◻
Proof of Lemma 1 [eq:23]. Let \(k\equiv2\bmod4\) and \(a\equiv3\bmod4\), where \(2\leq a\leq k-2\). Then \(k-a\equiv3\bmod4\) as well.
First suppose that one of \(a\) and \(k-a\) is equal to \(3\). By reversing the labels on the central path if necessary, we may assume that \(k-a=3\). Start with the partial sandwich \(\mathcal{S}_{2,4}^\S\) from Construction 1, relabeled so that its distinguished vertex \(v_3\) becomes \(v_a\). Extend to the left by \(a-3\) arcs using Lemma 1. This gives the desired sandwich.
Now suppose that \(a\geq7\) and \(k-a\geq7\). Start with the partial sandwich \(\mathcal{S}_{4,4,6}^\S\) from Construction 1, relabeled so that its distinguished vertex \(v_7\) becomes \(v_a\). Extend to the left by \(a-7\) arcs and to the right by \(k-a-7\) arcs using Lemma 1. The extension lemma preserves the cover \(1/2\) at the distinguished vertex and fills all endpoint and gluing deficits. Hence the resulting tuple satisfies ?? . ◻
6.6 Case [eq:30] of Lemma 1↩︎
We present two constructions which are used to establish the fifth case of Lemma 1.
Construction 1. There exists a partial \(\vec{P}_{3,4}\)-sandwich \[\mathcal{S}_{3,4}^\S=(\vec{D}_{3,4}^\S,\psi_{3,4}^\S,\omega_{3,4}^\S,\pi_{3,4}^\S)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_{3,4}^\S}(v_{i})= \begin{cases} 1/2&\text{if }i=4,\\ 3/4&\text{if }i\in\{0,1\},\\ 15/16&\text{if }i=7,\\ 1&\text{otherwise}, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{3,4}^\S}(e_i)= \begin{cases} 3/4&\text{if }i=0,\\ 1&\text{otherwise}. \end{cases}\]
Proof. The oriented graph \(\vec{D}_{3,4}^\S\) is shown in Figure 22 in Appendix 8. Each component of \(\vec{D}_{3,4}^\S\setminus V(\vec{P}_{3,4})\) is assigned a weight of \(1/32,2/32,4/32,5/32,8/32\) or \(10/32\) by \(\omega_{3,4}^\S\), as indicated in the figure. Summing the indicated component weights gives the stated values of \(\mathop{\mathrm{cov}}\) and, in the verification of [eq:anti-Sidcomponents], we partition the components so that each \(2\)-arc path with two blocks with another \(2\)-arc path with one block which has the same weight and apply Proposition 1. ◻
Construction 1. There exists a partial \(\vec{P}_{3,8}\)-sandwich \[\mathcal{S}_{3,8}^\S=(\vec{D}_{3,8}^\S,\psi_{3,8}^\S,\omega_{3,8}^\S,\pi_{3,8}^\S)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_{3,8}^\S}(v_{i})= \begin{cases} 1/2&\text{if }i=4,\\ 3/4&\text{if }i\in\{0,1,10,11\},\\ 1&\text{otherwise}, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{3,8}^\S}(e_i)= \begin{cases} 3/4&\text{if }i\in\{0,10\},\\ 1&\text{otherwise}. \end{cases}\]
Proof. The oriented graph \(\vec{D}_{3,8}^\S\) is shown in Figure 23 in Appendix 8. Each component of \(\vec{D}_{3,8}^\S\setminus V(\vec{P}_{3,8})\) is assigned a weight of \(1/4\) or \(1/8\) by \(\omega_{3,8}^\S\), as indicated in the figure. Summing the indicated component weights gives the stated values of \(\mathop{\mathrm{cov}}\) and, as in the proof of Construction 1, the verification of [eq:anti-Sidcomponents] uses Proposition 1 and the fact that the path consisting of a block of length one and a block of length two is tournament anti-Sidorenko. ◻
Proof of Lemma 1 [eq:30]. Let \(k\equiv3\bmod4\) and \(a\equiv0\bmod4\), where \(2\leq a\leq k-2\). Thus \(a\geq4\).
First suppose that \(a=k-3\). Start with the partial sandwich \(\mathcal{S}_{3,4}^\S\) from Construction 1, relabeled so that its distinguished vertex \(v_4\) becomes \(v_a\). Extend to the left by \(a-4\) arcs using Lemma 1. The distinguished vertex has cover \(1/2\), so ?? holds.
Now suppose that \(a\leq k-7\). Start with the partial sandwich \(\mathcal{S}_{3,8}^\S\) from Construction 1, relabeled so that its distinguished vertex \(v_4\) becomes \(v_a\). Extend to the left by \(a-4\) arcs and to the right by \(k-a-7\) arcs using Lemma 1. Again the distinguished vertex has cover \(1/2\), and the extension lemma gives the required arc and vertex covers everywhere else. ◻
6.7 Case [eq:31] of Lemma 1↩︎
Next, we obtain a construction that is useful for the sixth case of Lemma 1.
Construction 1. There exists a partial \(\vec{P}_{4,3}\)-sandwich \[\mathcal{S}_{4,3}^\S=(\vec{D}_{4,3}^\S,\psi_{4,3}^\S,\omega_{4,3}^\S,\pi_{4,3}^\S)\] such that \[\mathop{\mathrm{cov}}_{\mathcal{S}_{4,3}^\S}(v_{i})= \begin{cases} 1/2&\text{if }i=5,\\ 3/4&\text{if }i\in\{0,1,6,7\},\\ 1&\text{otherwise}, \end{cases}\] and \[\mathop{\mathrm{cov}}_{\mathcal{S}_{4,3}^\S}(e_i)= \begin{cases} 3/4&\text{if }i\in\{0,6\},\\ 1&\text{otherwise}. \end{cases}\]
Proof. The oriented graph \(\vec{D}_{4,3}^\S\) is shown in Figure 24 in Appendix 8. Each component of \(\vec{D}_{4,3}^\S\setminus V(\vec{P}_{4,3})\) is assigned a weight of \(1/4\) by \(\omega_{4,3}^\S\). Summing the indicated component weights gives the stated values of \(\mathop{\mathrm{cov}}\) and, as in the proof of Construction 1, the verification of [eq:anti-Sidcomponents] uses Proposition 1. ◻
Proof of Lemma 1 [eq:31]. Let \(k\equiv3\bmod4\) and \(a\equiv1\bmod4\), where \(2\leq a\leq k-2\). Then \(a\geq5\) and \(k-a\geq2\). Start with the partial sandwich \(\mathcal{S}_{4,3}^\S\) from Construction 1. Its distinguished vertex is \(v_5\), and it has the endpoint cover pattern required by Lemma 1 at both endpoints.
Extend this certificate to the left by \(a-5\) arcs and to the right by \(k-a-2\) arcs using Lemma 1. After relabeling, the distinguished vertex is \(v_a\), and its cover is still \(1/2\). Thus we obtain the desired sandwich satisfying ?? . ◻
7 Conclusion↩︎
We mention some related independent work. During discussions on Sidorenko and anti-Sidorenko phenomena while Kráľ was visiting the University of Victoria, we learned that Kráľ, Kučerák and Lidický [30] have obtained further examples of tournament anti-Sidorenko orientations of trees by different methods, based on Taylor-type expansions and the analysis of subgraph counts. In particular, their arguments give a tournament anti-Sidorenko orientation of the \((2,3,4)\)-spider, which is a special case of Theorem 1, and also show that the canonical orientation of the \((2,2,2,2)\)-spider obtained as the union of two directed paths is tournament anti-Sidorenko. The latter clarifies the scope of Remark 5.3 in [2]; it seems that this statement should be interpreted as applying only for sufficiently large \(k\).
8 Atlas of Sandwiches↩︎
This appendix contains the explicit sandwich certificates used in Sections 5 and 6. All figures follow the convention described in Remark 1. The values of \(\mathop{\mathrm{cov}}\) in the corresponding propositions are obtained by summing these component weights column by column and between consecutive columns.
References↩︎
School of Mathematical Sciences, University of Science and Technology of China, Hefei, Anhui, 230026, China. E-mail:
mathsch@mail.ustc.edu.cn. This work was completed while the first author was visiting the University of Victoria. Research supported by National Key Research and Development Program of China 2023YFA1010201, National Natural Science Foundation of China grant 12125106 and China Scholarship Council No. 202406340066.↩︎Department of Mathematics and Statistics, University of Victoria, Victoria, B.C., Canada.↩︎
E-mail:
fclemen@uvic.ca. Research supported by PIMS Postdoctoral Fellowship PIMS-20260513-PDF.↩︎E-mail:
noelj@uvic.ca. Research supported by NSERC Discovery Grant RGPIN-2021-02460.↩︎Problem 1.6 from [1] was also solved independently by another group; see the remarks in Section 7.↩︎
It would also be equivalent to work in the setting of tournament limits as in [13], [15], [21], [22]; however, for the purposes of this paper, this would introduce several technicalities and would not bring any advantages.↩︎
Technically, Lemma 1 was only proved for homomorphisms to tournaments, not for general matrices. However, it is well known, and easy to see, that it holds for general matrices as well.↩︎
We use the term “sandwich” because the diagrams in this paper typically consist of \(\vec{H}\) with additional structures drawn above and below \(\vec{H}\); so, it is like a sandwich in which \(\vec{H}\) is the filling.↩︎