{'fraction_non_alphanumeric': 0.04472843450479233, 'fraction_numerical': 0.013257699245832519, 'mean_word_length': 3.7834494230169455, 'pattern_counts': {'":': 0, '<': 4, '<?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': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cubic Preferences and the Character Admissibility Problem

In multiple-question referendum elections, the separability problem occurs when a voter's preferences on some questions or proposals depend on the predicted outcomes of others. The notion of separability formalizes the study of interdependence in multidimensional preferences, and the character admissibility problem deals with the construction of voter preferences with given separability structures. In this paper, we develop a graph theoretic approach to the character admissibilty problem, using Hamiltonian paths to generate voter preferences. We apply this method specifically to the hypercube graph, defining the class of cubic preferences. We then explore how the algebraic structure of the group of symmetries of the hypercube impacts the separability structures exhibited by cubic preferences. We prove that the characters of cubic preferences satisfy set theoretic properties distinct from those produced by previous methods, and we define two functions to construct cubic preferences. Our results have potential applications to experimental work involving election simulation.


Introduction
In referendum elections, voters are often required to cast simultaneous ballots on multiple questions or proposals. The separability problem [2] occurs when voters' preferences on some sets of questions depend on the outcomes of others.
For example, a voter may support a property tax increase, but only if a proposal to improve roads is also approved. In a simultaneous election, voters have no way to express such interdependencies, which can lead to election outcomes that are unsatisfactory or even paradoxical. One classic example is due to Lacy and Niou [6], who demonstrate the possibility of an election in which the winning combination of outcomes is the last choice of every voter.
The notion of separability formalizes the study of interdependence in multidimensional preferences and is important in many fields, including economics, social choice theory, operations research, and computer science. Here we focus on the structure of interedependent preferences in multiple-criteria binary decision processes such as referendum elections. In this context, a voter's preferences on a set of questions are said to be separable if they do not depend on the outcome of other questions in the election (and nonseparable otherwise).
Given a convenient representation of a voter's preferences (we use preference matrices), it is relatively straightforward to determine the sets of questions that are separable with respect to that voter. The collection of all such sets is called the voter's character. However, the corresponding inverse problem is more complex. In fact, there are no general methods for constructing a preference order with a given character, and it is sometimes impossible to determine whether such a preference order even exists. If such an order does exist, the associated character is said to be admissible. Past research has focused on classifying and constructing admissible characters. Bradley, Hodge, and Kilgour [1] proved results implying that admissible characters are always closed under intersections but may not be closed under other set operations. Hodge and TerHaar [5] determined all admissible characters for question sets of size 4 or less; they also proved the existence of nontrivial inadmissible characters-that is, collections of sets that are closed under intersections and yet cannot occur as a voter's character-for question sets of size 4 or more. Most recently, Hodge, Krines, and Lahr [4] developed the technique of preseparable extensions to construct preferences with certain classes of characters.
In this paper, we introduce a new method that uses vertex-edge graphs to generate preference orders. In Section 2, we introduce this method and apply it the n-dimensional hypercube graph, defining a class of preferences, called cubic preferences. In Section 3, we prove results that relate the separability structures associated with cubic preferences to the algebraic structure of the hypercube graph. In Section 4, we present methods for constructing cubic preferences and prove results about the resulting characters. Importantly, we show that the characters associated with cubic preferences are distinct from those generated by Hodge, Krines, and Lahr's method of preseparable extensions. We conclude in Section 5 with a brief discussion of the potential applications of our methods to election simulation and the character admissibility problem.

Preference Matrices and Separability
Throughout this paper, we will limit our attention to decision-making processes involving a finite number of binary (yes-no) decisions, using the language of referendum elections to ground our work in a familiar context. In a referendum election with n yes-no questions, there are 2 n possible results for the election as a whole, which we refer to as outcomes. If we let Q n = {1, 2, . . . , n} denote the question set, then an outcome is simply an element of {0, 1} n (the Cartesian product of n copies of {0, 1}), which we denote by X. For each question, we associate a value of 1 with an outcome of yes and 0 with an outcome of no. Given a subset S ⊆ Q n with |S| = m, we can define an outcome on S in a similar manner-namely, as an element of {0, 1} m . We use the notation X S to represent the set of all possible outcomes on S.
Consistent with previous research, we use a total order on X, displayed in convenient form as a preference matrix, to represent the preferences of each voter. In particular, for each voter we list the 2 n possible outcomes as the rows of a 2 n × n matrix, with the voter's most preferred outcome as the first row and the voter's least preferred outcome as the last row.
As an example, consider the following preference matrix for an election on n = 2 questions: 1 This matrix represents the preferences of a voter whose most preferred outcome is yes on the first question and no on the second, and whose least preferred outcome is no on both questions. Written horizontally, the corresponding total order is (1, 0) (1, 1) (0, 1) (0, 0), or simply 10 11 01 00.
(We will typically omit tuple notation except in cases where it is necessary for clarity.) A subset S ⊂ Q n is said to be separable with respect to a given voter if that voter's preferences on questions in S do not depend on the outcome of questions outside of S. In other words, we can determine the separability of the set S by successively fixing all possible outcomes on Q n − S and checking to see if the preferences induced on S are the same for each of these outcomes. 1 The examples involving matrix A, here and below, first appeared in [5].
To illustrate, consider the matrix A again, and suppose we restrict our attention to the outcomes in which the result on the second question is 0. These outcomes correspond to the top and bottom rows of the matrix, inducing an order of 1 0 on the first question. Likewise, the middle two rows represent outcomes in which the result on the second question is 1, and these two rows again induce an order of 1 0 on the first question. The fact that these in- We will begin, as an example, by determining whether or not the set {1, 2} is separable. In order to do so, we must compare the induced preference orders on {1, 2} when the outcomes of 1 and 0, respectively, are fixed on the set {3}.
It is convenient to represent these induced preference orders as follows: can itself be viewed as a preference matrix for an election on S. We can then define the separability of S as follows: Definition 1. Let P be a preference matrix for the question set Q n , and let S be a nonempty, proper subset of Q n . Then S is said to be separable with respect to P if ,y] for all x, y ∈ X Qn−S , and nonseparable otherwise.
We consider Q n and ∅ to be trivially separable with respect to any preference matrix. Applying Definition 1 to all possible nontrivial subsets of Q n yields the character of the matrix, defined formally below.
Definition 2. Let P be a preference matrix for the question set Q n . The character of P , denoted char(P ), is the set of all subsets of Q n that are separable with respect to P . If char(P ) = P(Q n ) (the power set of Q n ), then P is said to be completely separable. If char(P ) = {∅, Q n }, then P is said to be completely nonseparable. Observe that for any S ∈ char(P ), the definition of separability induces a fixed ordering on X S . As before, we use the symbol to denote this induced ordering (for example 1 0), relying on context to indicate that the ordering is on X S and not X.
In addition to considering the characters of specific preference matrices, it will be convenient for us to use the term character to refer to any collection of subsets of Q n . A character C is then said to be admissible if there exists a preference matrix P such that char(P ) = C. The fact that inadmissible characters exist, and that it is not known how to identify them based on settheoretic properties of the characters alone, is an interesting problem in itself [5]. Our approach to the character admissibility problem centers on constructing preference matrices from Hamiltonian paths in graphs.

A Graph Theoretic Model
Recall that, for an election on n yes-or-no questions, there are 2 n possible outcomes. Therefore, any graph with 2 n vertices can be labeled with these outcomes. Moreover, any Hamiltonian path in such a graph-that is, a path that includes each vertex exactly once-traverses the (labeled) vertices in an order that can be thought of as generating a preference matrix. The next definition formalizes this idea.
Definition 3. Let G be a graph on 2 n vertices, each labeled with a different outcome for an election on n questions, and let H be a Hamiltonian path on G.
Let P be the preference matrix whose rows, from top to bottom, are the labels of the vertices of G, in the order traversed by H. Then H is said to generate P .
For example, the Hamiltonian path shown in Figure 1 generates preference matrix M .   It is clear that, for any given graph on 2 n vertices, each Hamiltonian path will generate a unique preference matrix. However, graphs often contain multiple Hamiltonian paths, thereby generating multiple preference matrices. This in turn motivates the following definitions: Definition 4. Given a preference matrix P for an election on n questions and a labeled graph G with 2 n vertices, we say that G and P are consistent if and only if G contains a Hamiltonian path that generates P . (We may also say that G is consistent with P or that P is consistent with G.) The set of all preference matrices consistent with G is called the consistency set of G, denoted by C(G).
Note that the consistency set of a graph G depends on both the structure of G and its labeling. Indeed, it is possible for two different labelings of the same graph to yield entirely different consistency sets.
It is also important to note that finding the entire consistency set of a graph is, in general, a computationally demanding task-particularly for larger graphs.
Indeed, simply determining whether or not a Hamiltonian path exists on a given graph is an NP-complete problem [7]. However, there are some interesting classes of graphs for which it is possible to enumerate all Hamiltonian paths; in particular, it is helpful when the structure of a graph suggests a natural labeling corresponding to the outcomes of an appropriately-sized election.
One such example is the n-dimensional hypercube graph (with 2 n vertices), labeled so that each pair of adjacent vertices differ on exactly one question (or bit). Since this labeling is often called the Gray code labeling [8], we will use the notation G n to denote such graphs, which we will call Gray graphs. Elements of the consistency set C(G n ) will then be referred to as cubic preferences.
To illustrate, note that the graph shown in Figure 1 is in fact G 3 , and the matrix C is one of many elements of C(G 3 ). For an arbitrary P ∈ C(G n ), each row of P differs by exactly one bit from the rows immediately preceding and following it. Therefore, given a subset S of Q n , we say that S changes from one row to the next if the column containing the bit that differs between the two rows is in S. Moreover, if the outcomes on S for these two differing rows are x and y respectively, with x above y, we say that S changes from x to y.
With these definitions, we may now begin to study cubic preferences in earnest. We begin by partitioning C(G n ) into natural equivalence classes, and then enumerate all elements of C(G n ) for small n.

Character and Path Classes
In order to construct C(G n ), it will be convenient for us to consider characters that differ only by a permutation of the questions to be equivalent, or isomorphic. We define character isomorphism formally below.
Definition 5. Let σ ∈ S n (the symmetric group of degree n), and let C be any collection of subsets of Q n . Then we define where σ(S) = {σ(i) : i ∈ S}. Moreover, two characters C 1 and C 2 are said to be isomorphic if and only if there exists some σ ∈ S n such that C 2 = σ(C 1 ).
Since character isomorphism is clearly an equivalence relation, it partitions any set of characters into equivalence classes. Likewise, character isomorphism also induces an equivalence relation on any set of preference matrices. The corresponding equivalence classes are called character classes, defined formally below.
Definition 6. Let M be a collection of preference matrices, and let ∼ be the equivalence relation defined on M by P 1 ∼ P 2 if and only if char(P 1 ) and char(P 2 ) are isomorphic. A character class is an equivalence class of the ∼ relation.
Partitioning preference matrices into character classes simplifies the task of enumerating the characters corresponding to a given graph's consistency set.
In the case of C(G n ), this set can be further partitioned-into what we will call path classes-by appealing to the algebraic properties of the automorphism group of G n .
The automorphism group of the n-dimensional hypercube is the hyperoctahedral group, which we represent as the subgroup H n of GL n (Z) consisting of all n × n matrices whose only nonzero entries are ±1 and for which each row and each column contains exactly one nonzero entry. With a small adjustment to the entries of the matrices in C(G n )-specifically, replacing each 0 with −1we can show that H n acts on C(G n ) by right multiplication, which intuitively corresponds to permuting and taking bitwise complements of the columns. As an example, let Replacing each 0 with −1 in P and then multiplying on the right by M yields Now replacing each −1 with 0 in the product yields the matrix Therefore, we see that the action of M on P was to apply the permutation (132) to the columns of P and then take the bitwise complement of the new third column. (Note that the order in which these two components of the action are performed is important.) Formally, for any matrix P with entries consisting only of 0 and ±1, let P denote the matrix obtained by replacing each 0 with −1 and each −1 with 0. Note that P = P . Then define the map φ : Lemma 1. The map φ as defined above is a (right) group action of H n on Proof. By the definition of a group action, we must establish that φ satisfies both the identity and compatibility (associativity) axioms. For the former, let I n denote the identity matrix. Then for all P ∈ C(G n ), φ(P, I n ) = P I n = P = P.
For compatibility, note that if M 1 and M 2 are elements of H n , then associativity of matrix multiplication implies that for all P ∈ C(G n ). This completes the proof.
We will use standard · notation to denote the action defined by φ, abrreviating φ(P, M ) by P · M . Recall that, for a group G acting on a set X, the orbit of an element x ∈ X is the set {x · g : g ∈ G}. In the case of the hyperoctahderal group H n acting on C(G n ), the orbits include matrices generated by paths that differ from one another only by symmetries of the hypercube. The next theorem elucidates the relationship between character classes and path classes.
Theorem 2. Let A, B ∈ C(G n ) be in the same path class. Then A and B are also in the same character class.
Proof. First note that any element M of H n can be written as a product where M σ is a permutation matrix, and M τ is a signature matrix-that is, a matrix of the form Since A and B are in the same path class, there exists , and let C = char(A · M σ ). Since M σ is a permutation matrix, C and C are isomorphic. Moreover, M τ acts on A · M σ by taking bitwise complements of some subset of the columns of A · M σ -an action that has no impact on separability and therefore preserves character. It follows that which proves that A and B are in the same character class.
Note that the converse of Theorem 2 is not true; that is, a character class may contain several path classes (as shown in Tables 3 and 4). In general, the collection of path classes is a refinement of the partition of C(G n ) formed by character classes. Moreover, each of the path classes for a given G n has the same cardinality, as demonstrated by the following results.
Lemma 3. For every preference matrix P , the columns of P are distinct. Furthermore, no pair of columns of P are bitwise complements of each other.
Proof. Suppose two columns of P are identical. Then none of the outcomes that differ on the corresponding questions occur in P , and thus P is not a valid preference matrix. A similar argument shows that no pair of columns of P are bitwise complements.
Furthermore, each path class has cardinality |H n | = 2 n · n!, and so C(G n ) has exactly |C(Gn)| 2 n ·n! path classes.
Proof. For P ∈ C(G n ), we denote its path class as the orbit O P . Furthermore, we denote the stabilizer subgroup of P in H n as We wish to show that, for all P ∈ C(G n ), |O P | = 2 n n!. By the Orbit-Stabilizer Theorem and Lagrange's Theorem, Since we know that |H n | = 2 n · n!, it suffices to show that for all P ∈ C(G n ), where I n denotes the identity matrix.
Let P ∈ C(G n ) and suppose P · M = P for some M ∈ H n . Then P M = P , which implies that P M = P . Now let M = M σ M τ , where, as before, M σ is a permutation matrix and M τ is a signature matrix. Then P M σ M τ = P .
Then P M σ = P ; otherwise, P would have two identical columns, in violation of Lemma 3. But since we also know that (P M σ )M τ = P , this means that P M σ and P differ only by bitwise complements of columns. This, however, implies that P has two columns that are bitwise complements of each other, again a contradiction to Lemma 3. It follows that M σ = I n . Thus, |G P | = 1, from which the result follows.
These results are important for a number of reasons. First, they show how the separability structures within cubic preferences are related to the hypercube graphs that generate these preferences. Second, they help us to conceive of the consistency set of G n in a more organized fashion by partitioning it into equalsized sets with known separability properties.

Enumeration by Direct Computation
For small values of n, direct computation can be used to enumerate the elements of C(G n ). Tables 1-4 list the total number of matrices in C(G n ), for 2 ≤ n ≤ 5, divided into character and path classes. The computations were performed by computer, using a Python script to generate preference matrices in C(G n ) (at least one per path class) and a program developed by TerHaar (one of the first researchers to study the character admissibility problem; see [5]) to calculate the character of each matrix.
We use a notation for character classes wherein a, b, c, . . . represent arbitrary, distinct elements of Q n . Furthermore, we omit the trivial subsets for conciseness (except in the case of the class of completely nonseparable characters, which we denote ∅).
Character Class Total Matrices Path Classes

Separability Properties
Each of the characters in Tables 1-4 is nested, meaning that for each pair of separable subsets A and B, either A ⊆ B or B ⊆ A. We will now show that   That is, if A, B ∈ char(P ), then A ∩ B ∈ char(P ).
Lemma 6. Let P ∈ C(G), and let S be a proper, nonempty subset of Q n such that S ∈ char(P ). Furthermore, let x be the outcome on S corresponding to the first row of P . Then the first time any outcome on Q n − S occurs in P , the outcome on S in the corresponding row must be x.

Lemma 7.
Let P ∈ C(G) and let S be a proper, nonempty subset of Q n such that S ∈ char(P ). Then the bit that changes from the first to the second row of P is not in S.
Proof. Assume, to the contrary, that S is separable and S contains the first bit to change in P . Then where x 1 and x 2 are outcomes on S, y 1 and y 2 are outcomes on Q n −S, and x j is the outcome on S that occurs in the first pair of rows in which Q n − S changes. 2 Note that the first row of P [Qn−S,y2] is x j and the first row of P [Qn−S,y1] is x 1 .
Because S is separable, this means that x j = x 1 , which is a contradiction since x 1 y 1 would then appear twice in P . Therefore, if S is separable, the first bit to change is not in S.
We are now ready to state and prove our main result about the characters of cubic preferences.
Proof. We will use a proof by contradiction, divided into cases.
A = A − Z, and B = B − Z. By Lemma 7, the first bit to change can be in neither A nor B. Hence, the first bit to change must be in C. Therefore, C = ∅. This is a contradiction (and therefore establishes the result) when n = 2. Throughout the remainder of the proof, we will assume n ≥ 3 and use the notation a i , b i , c i , and z i to denote outcomes on A , B , C, and Z, respectively.
Consider the following two cases: Note then that A = A and B = B. We already know that the first bit to change must be in C. Without loss of generality, assume that A changes before B. Then P has the following form, where a 2 b 1 c k is the highest row in which a 2 appears, for some 1 < k < 2 |C| : Let a j b 2 c h be the highest row in which b 2 appears, which must appear below the row a 2 b 1 c k by the assumption that A changes before B. Then by Lemma 6 and the fact that A is separable, j = 1. In other words, before B changes to b 2 , A must change back to a 1 . Let a 1 b 1 c p be the first row after a 2 b 1 c k in which A changes back to a 1 , where c p is some outcome on C so that the row a 1 b 1 c p has not yet appeared in P . Since only one bit changes at a time and, by assumption, this change occurs in A, the row immediately above a 1 b 1 c p is a z b 1 c p , for some z = 1. Hence P has the following form: Fixing the outcome b 1 c p on B ∪ C induces a preference of a z a 1 on A.
But by the separability of A, a 1 must be the most preferred outcome on A for any outcome fixed on B ∪ C. Thus we have a contradiction, which rules out this case.
Case 2. We now consider the case that Z = ∅. As before, the first bit to change must be in C, but now that Z = ∅, we have: Note that, by Lemma 5, Z = A∩B is separable. Therefore, by Lemma 6, the first time an outcome on Q n − A, Q n − B, or Q n − Z occurs, the corresponding outcome on A, B, or Z must be a 1 z 1 , z 1 b 1 , or z 1 , respectively. Without loss of generality, assume that A changes for the first time before B . Let a 2 and b 2 be the second outcomes that occur on A and B , respectively. Note that it is possible for Z to change before either A or B changes; however, Z will have to change back to z 1 prior to the first time either A or B changes (by Lemma 6, as noted above, and the fact that only one bit can change at a time). Therefore, P has the following form, where c 3 and c 4 are distinct outcomes on C not equal to c 1 . where a 3 = a 1 (it may or may not be the case that a 3 = a 2 ), and z 2 and c 5 are outcomes on Z and C, respectively, which-for the time being-may or may not be distinct from z 1 and c 4 : Choose the lowest such pair of rows-that is, the last pair of rows before a 1 z 1 b 1 c 4 in which A changes back to a 1 . Then P has the following form: This gives us the following outcomes on the lower rows of the matrix P : Now consider the row immediately above a 1 z 1 b 1 c 6 . Applying the argument of the preceding two paragraphs with c 6 in place of c 4 shows that this row must be equal to a 1 z 1 b 1 c 7 for some new outcome c 7 on C. And in fact, this pattern continues for each successive row above a 1 z 1 b 1 c 4 . Therefore, we must eventually obtain the following pair of rows in P , where c j = c 5 : But since z 1 = z 2 (as shown previously), we have two bits changing at the same time, a contradiction to the fact that P ∈ C(G n ).
We have now shown that in both cases (Z = ∅ and Z = ∅), the assumption that A ⊆ B and B ⊆ A leads to a contradiction; therefore, it must be the case The following corollaries follow immediately from Theorem 8.
Corollary 9. Let P ∈ C(G n ), and let S be a nonempty, proper subset of Q n .
Then S and Q n − S cannot both be separable.
Corollary 10. For all n ≥ 2 and all P ∈ C(G n ), P is not completely separable.
Theorem 8 places narrow limits on the kinds of characters that can be associated with cubic preferences. In particular, the nested structure of cubic characters sets them apart from the characters generated by Hodge, Krines, and Lahr's [4] method of preseparable extensions, which always contain both a nontrivial subset of Q n and its complement. Therefore, any method to construct cubic preference matrices will necessarily yield different separability structures than those obtained by previous work. In the next section, we introduce two such methods.
It is important to note that the necessary condition provided by Theorem 8 is not sufficient.  Table 4. Thus, it remains an open question to completely classify cubic preferences for arbitrary n according to their path and/or character classes.

Constructing Cubic Preferences
Given the rapid growth of the size of C(G n ) as n increases, it is infeasible in general to construct all cubic preference matrices by brute force computation. Here, we address this issue by introducing two functions-called stack and weave-which generate cubic preferences recursively by mapping elements of C(G n ) to C(G n+1 ). These functions behave predictably in that the characters of the constructed matrices are completely determined by the characters of the input matrices. While the stack and weave functions do not generate all possible cubic preferences-and thus, they do not completely characterize the consistency sets of Gray graphs-they do allow us to construct matrices with predictable characters, and thus to study cubic preferences in a more concrete way.

The Stack Function
The first function, which we call the stack function, combines pairs of matrices in C(G n ) to form a single matrix in C(G n+1 ). To illustrate the intuitive idea behind the stack function, we will consider a simple example.
First, we choose two matrices, P 1 , P 2 ∈ C(G n ), such that the first row of P 2 is equal to the last row of P 1 . Next, we stack P 1 on top of P 2 to form a new 2 n+1 × n matrix. Finally, we insert a column vector of the form 1 1 · · · 0 0 or 0 0 · · · 1 1 , either as the first or last column of the matrix or in between two other columns.
Applying this process with , and the column vector c = 1 1 1 1 0 0 0 0 inserted as the second column, we obtain the matrix which is an element of C(G 3 ).
The formal definition of the stack function makes this intuitive process more precise. In order to ensure a well-defined domain, we must first define which matrices can be stacked on top of one another. We now provide the formal definition of the stack function.
Definition 9. Let A ∈ C(G n ), B ∈ S(A), and k ∈ {1, . . . , n + 1}. We define A 1 k B = C to be the (2 n+1 ) × (n + 1) matrix whose entries are given by: where a i,j and b i,j denote the entries of A and B, respectively. We define A 0 k B in the same manner as A 1 k B, except with the bitwise complement taken of the k th column.
Since separability is unaffected by taking bitwise complements of columns, we need only consider A 1 k B in the results that follow, as similar arguments apply to A 0 k B. For convenience, given any set T ⊆ Q n and any k with 1 ≤ k ≤ n + 1, we will define the notation T k as follows: T k = {q ∈ T : q < k} ∪ {q + 1 : q ∈ T and q ≥ k}.
We will now show that for all A ∈ C(G n ) and all B ∈ S(A), the character of C = A 1 k B is uniquely determined by char(A), char(B), and k. Moreover, we will demonstrate explicitly how char(C) may be computed given this information. This proof involves several intermediate results, beginning with the lemma below.
Proof. Without loss of generality, assume k = n + 1. Let T ⊆ Q n+1 be given, with T = ∅ and k / ∈ T . Then T ⊆ Q n . By the definition of the stack function, where x 1 and x 2 are distinct outcomes on T and y is an outcome on Q n − T .
(Note that if T = Q n , and therefore Q n − T is empty, the remainder of the proof still follows, simply ignoring the middle column of P 1 1 k P 2 .) Fixing an outcome of (y, 1) on Q n+1 − T = (Q n − T ) ∪ {n + 1} induces a preference of x 1 x 2 on T , while fixing an outcome of (y, 0) on Q n+1 −T induces a preference of x 2 x 1 on T . Therefore, T is not separable with respect to P 1 1 k P 2 , and T / ∈ char(P 1 1 k P 2 ).
Lemma 11 implies that the stack function preserves nonseparability. Indeed, for stackable matrices P 1 and P 2 , every element of char(P 1 1 k P 2 ) must include the question, k, corresponding to the added column. Therefore, if T is nonseparable with respect to P 1 or P 2 , then T k is nonseparable with respect to P 1 1 k P 2 . (The same conclusion could be made if T was separable, but the point here is that the property of nonseparability is in fact preserved.) Since we have established which sets must be nonseparable in a matrix produced by the stack function, we will now turn our attention to the sets that can be separable.
Proof. We begin by proving that if T k ∪{k} ∈ char(P 1 1 k P 2 ), then T ∈ C 1 ∩C 2 .
We will do so by proving the contrapositive: if T / ∈ C 1 ∩ C 2 , then T k ∪ {k} / ∈ char(P 1 1 k P 2 ). Suppose T / ∈ C 1 ∩ C 2 . Without loss of generality, let T / ∈ C 1 . Then there exist outcomes x and y on Q n − T such that Without loss of generality, let k = n + 1.
Then, by construction, it may be seen that , it follows that A = B. Therefore, by the definition of separability, T k ∪ {k} is not separable with respect to P 1 1 k P 2 , and so T k ∪ {k} / ∈ char(P 1 1 k P 2 ). Next, we will prove that if T ∈ C 1 ∩ C 2 , then T k ∪ {k} ∈ char(P 1 1 k P 2 ). Suppose T ∈ C 1 ∩ C 2 . Then we have three cases: , it follows that A = B. Since x and y were chosen arbitrarily, the definition of separability implies that T k ∪ {k} is separable with respect to P 1 1 k P 2 . Thus, T k ∪ {k} ∈ char(P 1 1 k P 2 ). Having proven the implication in both directions, we have established that Lemma 11 establishes that every nonempty set S ∈ char(P 1 1 k P 2 ) must contain k, and therefore can be written in the form T k ∪ {k} for some T ⊆ Q n . Moreover, Lemma 12 demonstrates that a set of this form belongs to char(P 1 1 k P 2 ) if and only if T is an element of both char(P 1 ) and char(P 2 ). Together, these two results establish the following theorem, which describes the character of the stacked matrix P 1 1 k P 2 in terms of the characters of the two matrices, P 1 and P 2 , used to construct it.
Theorem 13. Let P 1 ∈ C(G n ) and P 2 ∈ S(P 1 ) and let char(P 1 ) = C 1 and char(P 2 ) = C 2 . Let 1 ≤ k ≤ n + 1. Then In addition to determining the characters of stacked matrices, the stack function illuminates more general properties of cubic preferences. In particular, observe in Theorem 13 how the question corresponding to the added column k is always separable. In fact, the converse of this result holds as well. In particular, if an individual question is separable with respect to a cubic preference matrix, then that matrix is necessarily stacked.
Theorem 14. Let P ∈ C(G n ), and let k ∈ Q n . Then the following are equivalent: 1. The set {k} is separable with respect to P .
3. The matrix P is equal to P 1 1 k P 2 or P 1 0 k P 2 for some P 1 ∈ C(G n−1 ) and P 2 ∈ S(P 1 ).
Without loss of generality, let k = n, and let the first entry of k be 1. Since k = 1 0 , we know that the top half of the matrix must include at least one row with an entry of 0 in column k. Let (x, 0) be the first such row. There must be some row after (x, 0) with an entry of 1 in column k. Let (y, 1) be the first such row. Note that x = y since since each outcome must appear exactly once in P and only one bit can change between any two rows. Thus, P must have the following form: where x, and y are outcomes on Q n − {k}.
Observe that fixing an outcome of x on Q n − {k} induces a preference of 1 0 on {k}, but fixing an outcome of y on Q n − {k} induces a preference of 0 1. Therefore, {k} is nonseparable.
For 2 → 3, assume without loss of generality that k = n and k = 1 0 .
Since P ∈ C(G n ) and the first 2 n−1 rows of P agree on k, it must be that each pair of consecutive rows in P 1 differ on exactly one question. Thus, P 1 ∈ C(G n−1 ). Likewise, P 2 ∈ C(G n−1 ). Furthermore, since the middle two rows of P differ on k, it must be that the last row of P 1 is identical to the first row of P 2 . Therefore, P 2 ∈ S(P 1 ), and it follows that P = P 1 1 k P 2 . That 3 → 1 follows immediately from Theorem 13.
The following corollary is an immediate consequence of Theorem 8, but may also be proven independently using Theorem 14 and Lemma 3.

The Weave Function
We will now turn our attention to a second function, called the weave function, which maps each individual matrix in C(G n ) to a larger matrix in C(G n+1 ).
As with the stack function, we will begin with an example.
First, we select a preference matrix P 1 ∈ C(G n ). Then we duplicate each row to create a 2 n+1 × n matrix in which rows i and i + 1 are equal for all odd i. Finally, we insert any column of zeros and ones that preserves the Gray code by allowing only one bit to change from each row to the next.
Applying this process to the matrix with the column vector 0 1 1 0 0 1 1 0 inserted as the third column, we obtain the matrix  which belongs to C(G 3 ).
The next definition formalizes this intuitive "weaving" process.
Proof. Without loss of generality, assume that k = n + 1. Let S ⊂ Q n+1 with k ∈ S. We will show that S is nonseparable. Since S = Q n+1 , Q n+1 − S = ∅.
Moreover, since Q n+1 − S must change at some point, 1 k (P ) must have the following form: where x 1 and x 2 are outcomes on Q n+1 −S, y is an outcome on S −{k}, and z ∈ {0, 1}. Note that fixing x 1 on Q n+1 − S induces an ordering of (y, z) (y, 1 − z) on S. However, fixing x 2 on Q n+1 − S induces an ordering of (y, 1 − z) (y, z) on S. Therefore, S is nonseparable.
Both the stack and weave functions increase the dimension of the resulting matrix by adding a certain type of column. In the case of the stack function, the question corresponding to this added column must be included in every nontrivial separable set. In the case of the weave function, however, the question corresponding to the added column is never included in a separable set (with the exception of Q n+1 ). Interestingly, while the stack function preserves nonseparability, the weave function preserves separability, as shown below.
Lemma 17. Let P ∈ C(G n ), and let T ⊆ Q n . Then T ∈ char(P ) if and only if T k ∈ char( 1 k (P )).
Proof. Let P * = 1 k (P ). If T = ∅, then the proof is trivial. Likewise, if T = Q n , note that Q n is always an element of char(P ), and Q k n is always an element of char(P * ) since Q n+1 − Q k n = {k} and by the definition of the weave function. Now assume that T is a nonempty, proper subset of Q n . For each direction, we will prove the contrapositive. That is, we will prove that T / ∈ char(P ) if and only if T k / ∈ char(P * ). With the preceding lemmas, we can now prove that the character of the matrix output by the weave function is uniquely determined by the character of the input matrix.
Theorem 18. Let P ∈ C(G n ) and let char(P ) = C . Then, Proof. First, let S ∈ char( 1 k (P )). We must show that S = Q n+1 or that there exists T ∈ C such that T k = S. Suppose S = Q n+1 . If S = ∅, then S = ∅ k and ∅ ∈ C. If S = ∅, then Lemma 16 implies that k / ∈ S. Now let T = {q : q ∈ S and q < k} ∪ {q − 1 : q ∈ S and q > k}.
Then, T k = S, and by Lemma 17, T ∈ C.
For the reverse inclusion, first note that if S = Q n+1 , then S ∈ char( 1 k (P )) trivially. On the other hand, if S = T k for some T ⊆ Q n with T ∈ C, then Lemma 17 implies that S ∈ char( 1 k (P )), which completes the proof.
Like the stack function, the weave function always yields a matrix with a special column-one whose structure allows us to make conclusions about the separability of certain related sets. It is also the case that the existence of such a column guarantees that the matrix in question is in fact woven. The following result, which is analogous to Theorem 14, formalizes this claim.
Theorem 19. Let P ∈ C(G n ), and let k ∈ Q n . Then the following are equivalent: 1. The set Q n − {k} is separable with respect to P .
3. The matrix P is equal to 1 k (P 1 ) or 0 k (P 1 ) for some P 1 ∈ C(G n−1 ).
To prove 1 → 2, let k denote the k th column of P . We will assume, to the contrary, that Q n −{k} is separable and that k = w (or its bitwise complement).
We will consider cases based on the possible forms of k. In each case, the same argument applies to the bitwise complement of k.
Case 1: Suppose k = · · · 1 0 1 · · · , where the omitted entries may be anything. Then, because P ∈ C(G n ) and therefore consecutive rows must differ on exactly one question, P must have the following form for some outcome z on Q n − {k}: This, however, is a contradiction, since the row (1, z) is repeated.
Case 2: Suppose k = · · · 1 1 1 0 · · · , where, again, the omitted entries may be anything. Then P must be of the following form for some distinct outcomes x, y, and z on Q n − {k}: Thus, fixing an outcome of 1 on {k} induces the preference order x y z on Q n − {k}. Since we have assumed that Q n − {k} is separable, the same preference order must be induced by fixing 0 on {k}. Therefore, P must have the following form: Observe that if the outcome 0 occurs on {k} in any row between (0, y) and (1, x), then Q n − {k} will no longer be separable. Furthermore, there must exist at least one row between (0, y) and (1, x), in order to preserve the Gray code.
The first such row, therefore, must have an outcome of 1 on k and an outcome of y on Q n − {k}, as shown below: This, however, is a contradiction, since the row (1, y) is repeated.
Case 3: If k does not satisfy the conditions of the previous cases, then it must be the case that there is no entry that is both immediately preceded and followed by different entries (Case 1), nor are there any instances in which three or more consecutive entries are identical (Case 2). This implies that all of the entries in k must be preceded by a 1 and followed by a 0, or vice versa. Consider that for any column satisfying this property, all entries-except possibly the first and the last, since they do not have entries both preceding and following them-must come in alternating pairs of identical entries. The weave column w satisfies this property, but we have already assumed that k = w (or its bitwise complement). Thus, we must construct a column vector that is not w, does not contain entries repeated three or more times, and must have pairs of alternating identical entries. The only column vector that satisfies these properties is k = 1 1 0 0 · · · 1 1 0 0 or its bitwise complement.
Now there are exactly 2 n−1 distinct outcomes on Q n − {k}, which we denote x 1 , x 2 , . . . , x 2 n−1 . In order to preserve the Gray code labeling, these outcomes must be arranged in the following manner within P : Observe that fixing an outcome of 1 on k makes x 1 the most preferred outcome on Q n − {k}, whereas fixing 0 on k makes x 1 the least preferred outcome on Q n − {k}. Therefore, by definition, Q n − {k} is nonseparable, which contradicts our assumption.
In each of these cases, we obtain a contradiction. Therefore, if Q n − {k} is separable, it must be that k is equal to w or its bitwise complement.
To establish that 2 → 3, let P be any matrix in C(G n ) whose k th column has the form w = 1 0 0 1 1 · · · 0 0 1 (or its bitwise complement).
In order to preserve the Gray code, rows i and i + 1 must agree on Q n − {k} for all odd i (since these rows differ on {k}). Thus, we have the equality P [{k},1] = P [{k},0] . Call this matrix P 1 . Then P = 1 k (P 1 ), as desired. Finally, for 3 → 1, suppose P is equal to 1 k (P 1 ) or 0 k (P 1 ) for some P 1 ∈ C(G n−1 ). Since P 1 ∈ C(G n−1 ), Q n−1 is trivially separable with respect to P 1 .
Moreover, Q n − {k} = Q k n−1 , which implies by Theorem 18 that Q n − {k} is separable with respect to P .
The following corollary is immediate from Theorem 8, but may also be proven independently using Theorem 19 and Lemma 3.
Given the value of |C(G n−1 )|, it is relatively straightforward calculate the number of matrices in |C(G n )| that are generated by the stack and weave functions. However, the fact that |C(G n )| is not known in general makes asymptotic analysis more difficult. Results for small n suggest that the proportion of all matrices in C(G n ) that can be produced by the stack and/or weave functions approaches 0 as n increases. (For example, this proportion is approximately 0.667 for n = 3, 0.231 for n = 4, and 0.028 for n = 5.) It is worth noting in particular that, by Theorems 13 and 18, the stack and weave functions can never produce a completely nonseparable preference matrix. In general, it is known (see [5]) that as n → ∞, the probability of a random preference matrix being completely nonseparable approaches 1. Our computational data (Tables 1-4) suggest that this trend is also true for cubic preferences, although we have not yet proved this result. We do know, however, that C(G n ) always contains at least one completely nonseparable preference matrix. This conclusion follows from recent work by Chew and Warner [3], who proved that the consistency set of any Hamiltonian graph always contains a completely nonseparable preference matrix. Therefore, we can conclude that the stack and weave functions, while useful in generating a wide variety of cubic preferences, cannot generate all such preferences. On the other hand, since completely nonseparable preferences are prevalent, it is a potential benefit that the stack and weave functions avoid them altogether and instead generate preferences within the rarer subclasses of partially separable cubic preferences.

Using Stack and Weave to Prove Admissibility
We will now present a brief example to illustrate how the stack and weave functions can be used to prove the admissibility of higher-dimensional characters. Consider the following character for an election on 7 questions: Since C is nested (in the sense of Theorem 8), it is possible that C = char(P ) for some P ∈ C(G 7 ). We will suppose that such a matrix P exists and work backwards to determine its form. Note that Q 7 − {5} = {1, 2, 3, 4, 6, 7} ∈ C.
Note that all of these steps are reversible. Therefore, if we can find P 1 and P 2 satisfying the above condition, we will have proved the admissibility of the original character C. It is clear from Table 3 that there exists a matrix as desired. Theorems 13 and 18 now imply that if P = 1 5 ( 1 1 (P 1 1 5 P 2 )), then char(P ) = C. Thus, C is admissible.

Conclusion
In this paper, we introduced a new method of generating multidimensional binary preferences by associating them with Hamiltonian paths in graphs. Applying our method to the hypercube graph, we defined the class of cubic preferences and studied its properties. We showed how the algebraic structure of the hypercube influences the separability structure of the preference matrices it generates, and we proved that the character of any cubic preference matrix must be nested-a significant distinction from the characters of preferences generated by previous methods such as preseparable extensions. Finally, we defined two functions that can be used to construct cubic preferences with predictable characters, and these functions gave us broader insights into the types of characters that can be associated with cubic preferences.
Our work here stopped short of completely classifying cubic preferences, and further research is needed to describe in full generality the kinds of characters that can be associated with cubic preferences. In addition, some interesting combinatorial questions remain open. For example, it seems likely-but has not yet been proved-that for cubic preferences, the probability of complete nonseparability approaches 1 as n → ∞.
Beyond cubic preferences, the graph theoretic approach to preference generation provides a new method for addressing the character admissibility problem by allowing for the systematic construction of preference matrices with certain given characters. Different graphs will necessarily lead to different classes of preferences, which could then be studied using the methods developed here.
This work, and the character admissibility problem in general, has potential applications to experimental work involving election simulation. In order to accurately assess the impact of nonseparability on the outcomes of referendum elections, and to test methods for alleviating the separability problem, it is necessary to generate electorates with a diverse range of interdependence structures. Therefore, cubic preferences, and others generated via Hamiltonian paths in graphs, could be incorporated into future simulations to test both the effects of nonseparability and the robustness of alternative voting schemes.