{'fraction_non_alphanumeric': 0.05474182049200579, 'fraction_numerical': 0.01616489605760068, 'mean_word_length': 3.6131553239986975, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 30, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Impartial digraphs

We prove a conjecture of Fox, Huang, and Lee that characterizes directed graphs that have constant density in all tournaments: they are disjoint unions of trees that are each constructed in a certain recursive way.


Introduction
In this paper we give a complete answer to the following question (our notation: H with an arrow on top denotes a directed graph, or digraph, and H without the arrow denotes the underlying undirected graph of H; we write |H| for the number of vertices of H): Which directed graphs H have the property that for some n ≥ |H|, all n-vertex tournaments contain the same number of copies of H as subgraphs? We say that a digraph H is impartial if it has the above property. Note that if the above property holds for some n 0 ≥ |H|, then it holds for all n ≥ n 0 , due to a double-counting argument considering all n 0 -vertex subsets of H. Example 1.1. A single directed edge is clearly impartial. The following graph is also impartial. (1) Indeed, all tournaments on n vertices have the same number of copies of and each such subgraph uniquely extends to a copy of (1).
We can continue this recursive argument and deduce that (2) is impartial. Indeed, the digraph obtained by removing the middle edge from (2) is impartial by earlier observations, and any copy (2) without the middle edge in a tournament can be uniquely extended to a copy of (2).
The above argument generalizes to all directed graphs that can be constructed in the following recursive manner. Definition 1.2. We say that a digraph T is recursively bridge-mirrored if it can be constructed recursively in the following manner: • The tree with one vertex is recursively bridge-mirrored; • Suppose T is recursively bridge-mirrored. Mark an arbitrary vertex of T as its root, and create a new graph by taking two identical copies of this rooted T and adding a new directed edge from one root to the other. The resulting digraph is also said to be recursively bridge-mirrored.
Zhao was supported by NSF Awards DMS-1362326 and DMS-1764176, the MIT Solomon Buchsbaum Fund, and a Sloan Research Fellowship.
Zhou was supported by the MIT Undergraduate Research Opportunities Program.
We say that an undirected graph T is recursively bridge-mirrored if it can be constructed as above but forgetting edge orientations.
Here is a sequence of recursively bridge-mirrored digraphs constructed recursively as in the definition.
All recursively bridge-mirrored graphs are trees. The earlier argument easily generalizes to show that all recursively bridge-mirrored digraphs are impartial. Our main result proves the converse.
Theorem 1.4. A directed graph is impartial if and only if it is a disjoint union of recursively bridge-mirrored digraphs.
Remark. It then follows that if H is impartial, then for every n, all n-vertex tournaments K have the same number of copies of H.
Background and motivation. The first author learned of this problem from Jacob Fox, who had proposed it together with Hao Huang and Choongbum Lee around 2013 when they considered density problems for digraphs and tournaments, including variants of Sidorenko's conjecture and the inducibility problem, where one wishes to maximize or minimize the number of copies of a fixed digraph in a tournament. They formulated Theorem 1.4 as a conjecture after computer experiments, and proved that every impartial digraph must be a disjoint union of trees whose number of vertices is a power of 2; see Proposition 2.1. (The name "impartial" is ours.) For undirected graphs, conjectures of Sidorenko [14] and Erdős-Simonovits [7] (commonly referred to as Sidorenko's conjecture) say that for every bipartite graph H, the H-density in a graph of fixed density is minimized asymptotically by a random graph. Lately the conjecture has been proved for many families of H [2,3,4,5,8,9,10,15], though the conjecture remains open in general. In particular, the case H = K 5,5 \ C 10 is open.
Our main theorem can be viewed as an "equality case" of the directed analog of Sidorenko's conjecture, which turns out to be already quite intricate. In Section 8, we propose several directions that are worth further investigation, including "positive" and "negative" digraphs, as well as generalizations to hypergraphs.
Outline. Our proof of Theorem 1.4 proceeds in several steps: • By comparing the density of H in a transitive tournament and a random tournament, along with some integer divisibility considerations, H is shown to be a forest (Section 2). • Using a graph limit argument, we convert impartiality to a polynomial identity (Section 3), and equating the coefficient leads us to subgraph statistics of impartial graphs (Section 4). • Then, we establish that the undirected structure of H is recursively bridge-mirrored (Section 5). • Once we have the undirected structure, we establish the directed structure of H (Section 6), and this step requires some additional analysis of undirected recursively bridgemirrored trees (Section 7).

Reduction to forests
We begin with a short argument due to Fox, Huang, and Lee (unpublished) that proves that every impartial digraph has a forest undirected structure.
By a component of a digraph we mean a weakly connected component (so its meaning is compatible with the undirected structure). Proposition 2.1. Every component of an impartial digraph is a tree whose number of vertices is a power of 2.
Proof. Let H be an impartial digraph, and n ≥ |H| such that every tournament on n vertices has exactly the same number of copies of H.
Suppose that H has k components, and the i-th component has n i vertices, m i edges, and exactly ℓ i linear extensions. The number of labeled copies of H in a transitive tournament on n vertices is exactly n n 1 , n 2 , . . . , n k , n − n 1 − · · · − n k ℓ 1 · · · ℓ k .
On the other hand, the expected number of labeled copies of H in a uniform random tournament on n vertices is, by linearity of expectations, n n 1 , n 2 , . . . , n k , n − n 1 − · · · − n k 2 −m 1 −···−m k n 1 ! · · · n k !.
On the other hand, the highest power of 2 that divides into n i ! has exponent ⌊n i /2⌋ + ⌊n i /4⌋ + · · · ≤ n i − 1, with equality whenever n i is a power of 2. Since 2 −m 1 −···−m k n 1 ! · · · n k ! = ℓ 1 · · · ℓ k is an integer, for every i, n i is a power of 2 and m i = n i − 1, so every component is a tree.

A graph limit argument
In this section, using tools from graph limit theory, we deduce some internal properties of an impartial digraph.
Adapting the notion of a graphon from graph limit theory [11], we define a tourneyon to be a measurable function W : [0, 1] 2 → [0, 1] satisfying W (x, y) + W (y, x) = 1 for all x, y ∈ [0, 1]. Just as graphons are the analytic limit objects for sequences of graphs, tourneyons are the limit objects for sequences of tournaments.
We write V (H) for the vertex set and E( H) the edge set of H. Directed edges are given by ordered pairs (u, v).
We define the density of a digraph H in W to be Let us first prove the "only if" direction (the relevant direction for our main theorem) and defer the proof of the "if" direction until a bit later.
Proof. ("Only if" direction) By standard arguments in graph limit theory [11,Chapter 10], for each tourneyon W there exists a sequence of n-vertex tournaments that approaches W in the cut metric as n grows to infinity, and thus by the counting lemma, they have H-densities approaching t( H, W ). Hence by impartiality, t( H, W ) is constant for every tourneyon W . The conclusion follows from noting that the constant tourneyon W ≡ 1/2 has H-density 2 −|E(H)| .
For every digraph H and positive integer n, define the following polynomial with variables a = (a 1 , . . . , a n ) and b = (b ij ) 1≤i<j≤n associated to H: (3) For a i ∈ [0, 1] and b ij ∈ [−1, 1] for all i, j and satisfying a 1 + · · · + a n = 1, the tourneyon W obtained by partitioning [0, 1] into intervals I 1 , . . . , I n of lengths a 1 , . . . , a n , and setting W (x, y) = (1 + b ij )/2 whenever (x, y) ∈ I i × I j , satisfies t( H, W ) = 2 −e(H) P H,n (a; b). (4) Proof. With the above b-values, every edge-orientation respecting homomorphism π : H → K corresponds to a nonzero term on the right-hand side of (3), and the map is injective if and only if the a factor is square-free.
Proposition 3.4. Let H be a digraph and n ≥ |H|. Then H is impartial if and only if P H,n (a; b) = (a 1 + · · · + a n ) |H| .
as a polynomial identity in the variables a and b.
Proof. If H is impartial, then by Proposition 3.2 and (4), one has (5) for all a i ∈ [0, 1] and b ij ∈ [−1, 1] for all i, j and satisfying a 1 + · · · + a n = 1. Since (5) is homomgenous in a, it must be a polynomial identity. Conversely, suppose (5) holds. So P H,n (a; b) does not depend on b, and by Lemma 3.3, the number of copies of H is constant in all n-vertex tournaments. Hence H is impartial.
Proof of the "if " direction of Proposition 3.2. If t( H, W ) = 2 −|E(H)| for all tourneyons, then setting W as in (4), we see that H satisfies the polynomial identity (5) for all n, and hence H is impartial by Proposition 3.4.
Here is an immediate consequence of the algebraic characterization of impartiality.

Proposition 3.5.
A digraph is impartial if and only if all its weakly connected components are impartial.
By unique factorization of polynomials, along with noting the degree of a and checking constant factors, we have P H j ,n (a; b) = (a 1 + · · · + a n ) |H j | for each j = 1, . . . , ℓ, and thus by Proposition 3.4 again, every H j is impartial.

Odd automorphisms and odd graphs
In this section we derive some subgraph statistics of impartial digraphs from the polynomial characterization in the previous section.
Given digraphs F and H along with an undirected graph homomorphism σ : }| is the number of edges of F whose orientation is reversed under the map σ.
Let Aut(H) be the group of automorphisms of undirected graph H. For σ ∈ Aut(H), write sgn(σ) = sgn(σ; H, H) where H is an arbitrary orientation of the edges of H. Note that sgn(σ) does not depend on this choice of edge orientations, since reversing the orientation of a single edge of H does not change the sign. We say that the automorphism σ of H is odd if sgn(σ) = −1 and even if sgn(σ) = 1.
We call a graph or a digraph odd if its underlying undirected graph has an odd automorphism, and even if it has no odd automorphism. The classification of graphs as even or odd plays an important role in our arguments. Note a graph is odd if and only if it has an odd component.
Given undirected graphs F and H, we denote the set of subgraphs of H isomorphic to F by These are unlabeled copies of F in H. To be precise, In our applications, |F | = |H|, so that we are considering the collection of edge-subsets of H that are isomorphic to F . Given a digraph H, we write to denote the set of subgraphs of H (with the inherited edge-orientations) whose undirected structure is isomorphic to F . Then Sub F ( H) has cardinality 4 and consists of (we draw the vertex set of the subgraph in the same way as H above) if F is even.
Proof. By expanding (3), we see that the coefficient of a F b F in P H,n (a; b) equals to the sum of We can then partition this sum by cosets of the automorphisms group of F , and the conclusion then follows.
Example 4.5. Continuing Example 4.3, letting F denote the orientation of F inherited from H, we find that sgn( F , F ′ ) for the four listed elements F ′ ∈ Sub F ( H) are 1, 1, 1, −1.
The following subgraph statistics characterization of impartiality is the main property that we need in the rest of the proof of the main theorem.
Proposition 4.6. A digraph H is impartial if and only if for every even digraph F on |H| vertices with at least one edge, Proof. Suppose H is impartial. By (5), the coefficient of a F b F in P H is zero provided that F has at least one edge, and by Lemma 4.4 we obtain (7). Conversely, suppose (7) holds for all even F with at least one edge, so that the coefficient of a F b F in P H is zero by Lemma 4.4. It follows that the polynomial identity (5) holds term-by-term for all terms that are square-free in a, and thus by Lemma 3.3, H has the same number of copies in all n-vertex tournaments, and hence H is impartial.

Undirected structure
The main goal of this section is to establish the undirected structure of an impartial digraph.
Proposition 5.1. The undirected structure of every weakly connected impartial digraph is a recursively bridge-mirrored tree.
We saw from Proposition 2.1 that it suffices to consider trees. In this section we focus on undirected structure, and by default "tree" means undirected tree.
Definition 5.2 (Mirror-bridge). An edge f of a tree T is called a mirror-bridge if T has an automorphism that swaps the two endpoints of f . In this case, we call the two isomorphic components of T \ f (T with edge f removed but all vertices kept) half-branches of T , Example 5.3. The mirror-bridge of the first tree below is highlighted, while the second tree does not have a mirror-bridge. This is a half-branch of the first tree:

Lemma 5.4. A tree is odd if and only if it has a mirror-bridge.
Proof. An automorphism of a tree that reverses a mirror-bridge must be odd.
Conversely, suppose a tree T has an odd automorphism π. We will construct subtrees T 0 T 1 · · · T k iteratively such that π induces an automorphism on each T i .
is not a single vertex or an edge, then let L i denote the set of leaves of T i , and set T i−1 to be T i with all its leaves and pendent edges removed. When the process terminates at i = k, T k is either a single vertex or an edge. Since an automorphism preserves leaves, an easy induction argument shows that π induces an automorphism for every T i .
Make T into a directed graph by orienting T k arbitrarily and orienting all edges from L i to L i+1 for every i. Note that π preserves the orientations of all edges except possibly T k . Since π is odd, T k must be a single edge and reversed by π, so that it is a mirror-bridge of T . The following procedure produces a canonical even subgraph of a given forest.
Definition 5.7 (Recursive cutting). Let F be a forest. The recursive cutting procedure applied to F produces a sequence (F 0 , F 1 , . . . ) where F 0 = F , and each F i+1 is obtained from F i from removing the bridge from each odd component of F i . Let F rc denote the even forest that the sequence eventually stabilizes to.
For a digraph F , we write F rc for F rc with edge-orientations inherited from F .
Example 5.8. Here is an example of recursive cutting: If F = , then F rc = . Now we are ready to prove the main result of this section, that the undirected structure of an impartial tree is recursively bridge-mirrored.
Proof of Proposition 5.1. Let H be a weakly connected impartial digraph. By Proposition 2.1, H is a tree. If H rc has at least one edge, Proposition 4.6 with F = H rc yields a contradiction due to Lemma 5.9. Thus H rc is edgeless, and hence H is recursively bridge-mirrored, as desired.

Directed structure
Recall from Proposition 3.5 that a digraph is impartial if and only if all its weakly connected components are impartial. From Proposition 5.1 we know that the undirected structure of a weakly connected impartial tree is a recursively bridge-mirrored tree. The goal of this section is to complete the proof of our main result Theorem 1.4, which follows from the next claim showing that the edge-orientation of such a tree is compatible with the recursive bridge-mirroring. Proposition 6.1. Every weakly connected impartial digraph is recursively bridge-mirrored.
In fact, it suffices to show that the directed structure is compatible with the involution of the tree. Remark. An easy induction argument shows that every undirected recursively bridge-mirrored tree with at least one edge has exactly two automorphisms: the identity map, and the odd automorphism that swaps the two half-branches and reverses the mirror-bridge.
Proof of Proposition 6.1 assuming Lemma 6.2. We apply induction on |H|. There is nothing to show if |H| = 1. Now assume |H| > 1, so that Lemma 6.2 applies. Let H 1 denote H after removing its mirror-bridge. Then Lemma 6.2 implies that every copy of H 1 in a tournament can be extended uniquely to a copy of H, and hence H 1 must be impartial. By Proposition 3.5, each component of H 1 is impartial, and thus recursively bridge-mirrored by induction. By Lemma 6.2 again, we see that H is recursively bridge-mirrored as well.
In the rest of this section, we prove Lemma 6.2. By Proposition 5.1, H is a recursively bridgemirrored tree. Let T be a recursively bridge-mirrored digraph with the same undirected structure H = T . Let τ denote the odd automorphism of H.
For each undirected edge e ∈ E(H) = E(T ), let z e = 1 if the orientations of e on H and T agree, and z e = −1 otherwise. By modifying T if necessary, we may assume that z e = 1 for the mirror-bridge e of T . To prove Lemma 6.2, it remains to show that z e = z τ e for all e ∈ E(H).
Applying Proposition 4.6, for every even F with |H| vertices, | Sub F (H)| is even and Multiplying the two products together, we obtain that for every even F with at least one edge, We shall use (8) with F being T f := (T \ f ) rc for every edge f of T other than its mirror-bridge. Note that T f has at least one edge as long as f is not the mirror-bridge of T , since the recursive cutting procedure preserves the largest odd factor of the number of vertices of the components.
We are interested in which z e 's appear an odd number of times on the left-hand side of (8). Let Since z e = ±1, (8) implies that for all even F with at least one edge e∈S F z e = 1.
(9) Example 6.3. We work out the above computation explicitly for a small example. Let T be a path with 8 vertices. The next lemma shows that (9) can be made into an upper-triangular linear system (mod 2) with an appropriate choice and ordering of subgraphs F 's. Proof of Lemma 6.2 assuming Lemma 6.4. We see that S F is invariant under the automorphism τ of T for every F ⊆ T . Let T ′ be a half-branch of T . Write w e = z e z τ e for each e ∈ E(T ′ ). Then (9) gives Then by Lemma 6.4, this system is equivalent to a linear system of equations (mod 2) whose coefficient matrix is upper-triangular with 1's on the diagonal when the variables w e are sorted according to |E(T e )| (breaking ties arbitrarily). It follows that for all e ∈ E(T ′ ), w e = z e z τ e = 1, and hence τ preserves the orientation of e in H since τ does the same for T .
We shall prove Lemma 6.4 by pairing up copies of F in T by applying an odd automorphism on some subgraph of T . Lemma 6.5. Let F be an even subgraph of a forest G. Then Proof. Order the edges of G according to the order that they are removed when G is recursively cut, breaking ties arbitrarily, i.e., edges of G i \ G i−1 appear earlier than those of G i+1 \ G i+2 , with the edges of G rc appearing last.
Let F ′ be a copy of F in G but not contained in G rc . Let e be the first edge of G in the above order contained in F ′ , and k the largest integer such that F ′ ⊆ G k . Then e is a mirror-bridge of its component in G k . Let σ denote the automorphism of G k obtained by applying an odd automorphism on the component of e and leaving other components of G k fixed. Note that σ e does not induce an automorphism of F ′ , or else the component of F ′ containing e would be odd, contradicting F being even.
The same procedure applied to F ′ recovers the same e, and hence recovers the original F (as long as we pick a consistent choice of an odd automorphism for each connected odd subgraph). Thus we have paired up copies of F in G but not contained in G rc , thereby proving the lemma. Example 6.6. Let us illustrate the pairing in the above proof. Let G be the following graph, with the first three edges in the recursive cutting removal ordering labeled. Then the following two highlighted subgraphs are paired together in the proof via reflecting the right half-branch of G across edge 3 (highlighted) in G 1 = : Proof of Lemma 6.4. By Lemma 6.5, | Sub T f (T )| ≡ | Sub T f (T rc )| = 0 (mod 2) since T rc is edgeless and T f has edges. Also by Lemma 6.5 (recall T e = (T \ e) rc ),

Properties of undirected recursively bridge-mirrored trees
It remains to prove the following claim, which was invoked at the end of the previous section. Recall that T e := (T \ e) rc . Proposition 7.1. Let T be a recursively bridge-mirrored tree. Let e 1 and e 2 be two distinct edges in T . If T e 1 ∼ = T e 2 , then the odd automorphism of T carries e 1 to e 2 .
Lemma 7.2. Let T be a recursively bridge-mirrored tree with 2 k vertices whose recursive cutting results in (T 0 = T, T 1 , . . . , T k = T rc ). Then for each 1 ≤ i ≤ k, 2 k−i is the largest power of 2 that divides the number of vertices in a branch of T cut from an edge in T i−1 \ T i .
Proof. Induction on i (easy and omitted).
Lemma 7.3. Let T be a recursively bridge-mirrored tree. If two distinct branches of T have the same number of vertices, then they are cut from edges that do not share endpoints.
Proof. By Lemma 7.2, the two cut edges lie in the same T i \ T i+1 for some i, and no two edges of T i \ T i+1 share a vertex since they are the mirror-bridges of the components of T i . Remark. Here is an example of two branches (highlighted) where (A 1 , u 1 ) ∼ = (A 2 , u 2 ) but no automorphism of T carries one to the other: Proof. We apply induction on |T |, with |T | ≤ 2 being trivial. Let T ′ be a half-branch of T .
Applying an automorphism of T if necessary, we may assume that A 1 , A 2 ⊆ T ′ . If |A 1 | < |T |/4, then (a) follows by applying the induction hypothesis to |T ′ |. Now assume |T |/4 ≤ |A 1 | ≤ |T |/2. Then both A 1 and A 2 have at least |T ′ |/2 vertices and hence each contains at least one vertex of the mirror-bridge of T ′ . So u 1 and u 2 both lie on the path between the mirror-bridges of T and T ′ . It follows that u 1 = u 2 or else one of A 1 and A 2 would strictly contain the other, which is impossible as |A 1 | = |A 2 |. Hence (A 1 , u 1 ) = (A 2 , u 2 ), and the result follows recalling the automorphism we may have applied initially.
Lemma 7.5 (Majority branch). Let T be a recursively bridge-mirrored tree. Let (B 1 , v 1 ) and (B 2 , v 2 ) be two branches with T such that B 1 and B 2 are isomorphic and each has at least |T |/2 vertices. Then T has an automorphism carrying v 1 to v 2 .
We require some preparation before proving the above lemma.   For each i, as the edge e walks along P i from the mirror-bridge of T to f i , min(T \ e) is strictly decreasing. Also, by Lemma 7.3, the size of the smaller component of T \ e must differ at the first instance when P 1 and P 2 diverge, contradicting the claim at the end of the previous paragraph. Therefore f 1 = f 2 . Lemma 7.9. Let T be a recursively bridge-mirrored tree with at least two vertices. Let B 1 and B 2 be two branches of T with |B 1 | = |B 2 | ≥ |T |/2. If both B 1 and B 2 are odd, then T has an automorphism carrying B 1 to B 2 .
Proof. For each i = 1, 2, since B i is odd, it has a mirror-bridge e i by Lemma 5.4. Let (C i , r i ) be the half-branch of B i not containing the mirror-bridge of T . Since |T |/4 ≤ |C 1 | = |C 2 | ≤ |T |/2, by Lemma 7.4, T has an automorphism carrying (C 1 , r 1 ) to (C 2 , r 2 ). Since (C 1 , r 1 ) ∼ = (C 2 , r 2 ), we have B 1 ∼ = B 2 , and the conclusion follows by Lemma 7.5. Now we are ready to prove the main result of this section, thereby completing the proof of the main result Theorem 1.4 of this paper.
Proof of Proposition 7.1. For each i = 1, 2, let A i and B i be the two components of T \ e i , with |A i | ≤ |B i |.
If B 1 is even, then it is a component of T e 1 with at least half of the vertices. Since T e 1 ∼ = T e 2 , B 2 must also be an even component of T e 2 , and B 1 ∼ = B 2 , and the conclusion follows from Lemma 7.5.
So assume that both B 1 and B 2 are odd. Since T e 1 ∼ = T e 2 , we have |B 1 | = |B 2 | (note we can identify which components of T e 1 came from B 1 versus A 1 based on the largest odd factor of its order), and the conclusion then follows from Lemma 7.9. is positive, as it follows from the proof of Sidorenko's conjecture for a 3-edge path (see the responses to this MathOverflow post [12] for some nice and short proofs).
The remaining orientations and are impartial.
There are recursive ways to build up positive graphs. For example, construct H constructed by taking a disjoint union of H 1 and H 2 and adding a new directed edge from every vertex of H 1 to every vertex of H 2 . We leave it as a fun exercise 1 to show that if H 1 and H 2 are positive, then so is H.
As a corollary of the above recursive construction, we see that all transitive tournaments are positive, which was known [6]. Also, a positive tournament must be transitive since it has to embed into a transitive tournament.
It appears to be a challenging problem to classify all positive and negative digraphs. In particular, the problem of classifying positive digraphs includes Sidorenko's conjecture as a special case. The problem is somewhat reminiscent of the positive graph conjecture [1]. We say that a graph G is positive if t(H, W ) ≥ 0 for every measurable W : [0, 1] 2 → [−1, 1] (i.e., graphons but allowing negative values) with W (x, y) = W (y, x). For example, an application of the Cauchy-Schwarz inequality shows that H = C 4 is positive. A similar Cauchy-Schwarz application shows that any graph H obtained by gluing some graph to itself along an independent set is positive, and the conjecture says that every positive graph has this form.
Recently, a reverse Sidorenko inequality inequality was established [13], showing that, for instance, for a triangle-free d-regular graph H, the H-density in a graph is always upper-bounded by the appropriately normalized K d,d -density. It may be interesting to explore directed versions of such reverse Sidorenko inequalities.
1 Hint: by first fixing the embedding of H1, and applying the positivity of H2, we can replace H2 by an empty graph on |H2| vertices. Likewise with H1. Then it remains to show that the complete bipartite graph is positive, which follows from Hölder's inequality. 8.2. Directed hypergraphs. The notion of impartiality can also be generalized to hypergraphs. Here one needs to specify what is meant by a directed hypergraph and what is the analog of a tournament. What's a "directed edge"?
Here are two possible definitions for how to orient a triple in a 3-uniform hypergraph.
One possible definition of a directed triple is to pick one of the 6 permutations of the triple. Then the corresponding generalization of a tourneyon is a measurable function W : [0, 1] 3 → [0, 1] with W (x, y, z) + W (x, z, y) + W (y, x, z) + W (y, z, x) + W (z, x, y) + W (z, y, x) = 1.
Another possible definition of a directed triple is to pick one of the two possible signs for a permutation of a triple (i.e., pick one of the two equivalence classes of the 6 permutations). Then, on top of the earlier constraint for W , one should also add W (x, y, z) = W (y, z, x) = W (z, x, y) and W (x, z, y) = W (z, y, x) = W (y, x, z).
For either notion, we can define an impartial directed 3-uniform hypergraph H as one whose density t( H, W ) is constant for all 3-uniform hypertourneyons W . Similarly, we say that H is positive/negative if t( H, W ) is minimized/maximized by the constant tourneyon.
For k-uniform hypergraphs, we generalize the above discussion by selecting a proper normal subgroup N of the symmetric group S k , and "orienting" each k-tuple by selecting a coset of N acting on the k-tuple. The corresponding constraint for hypertourneyons is W (x 1 , . . . , x k ) = W (x σ(1) , . . . , x σ(k) ) for all σ ∈ N . Recall that the only normal subgroups of S k with k ≥ 2 are the trivial group and the alternating group, except k = 4 where there is also the Klein four group. In the k = 3 discussion earlier, the first possibility corresponds to N being the trivial group, and the second corresponds to N being the alternating group.
Problem 8.4. Determine all impartial directed hypergraphs for each notion of directed hypergraphs.
We can also ask for positive and negative directed hypergraphs. Though, we do not even know which undirected hypergraphs satisfy the generalization of Sidorenko's conjecture.