Laurent Bulteau

Pallavi Jain

Nimrod Talmon

Partition Aggregation for Budgeting

Motivated by certain aggregation tasks related to participatory budgeting, such as clustering projects and modeling project interactions, we study several variants of the following aggregation problem: Given a set P of m projects, and n partitions of P , the task is to aggregate these n partitions into one aggregated partition. We consider several aggregation methods for this setting, including utility-based methods and Condorcet-based methods and evaluate these methods by analyzing their computational complexity and their behavior with respect to certain relevant axiomatic properties.

Method

Complexity Unanimity Majority-based IIP Total-PA NP-h even for n = 3 (Prop. 1) or ≤ 2 (Prop. 2) Yes Yes No Egal-PA NP-h No

Introduction

In participatory budgeting (PB) [START_REF] Cabannes | Participatory budgeting: a significant contribution to participatory democracy[END_REF] the task is to aggregate voter preferences over a set of projects, to decide upon a bundle of those projects to fund. It has received quite extensive recent attention from the research community, resulting in some aggregation methods to be used for such settings [START_REF] Faliszewski | A framework for approval-based budgeting methods[END_REF][START_REF] Benade | Preference elicitation for participatory budgeting[END_REF][START_REF] Freeman | Truthful aggregation of budget proposals[END_REF][START_REF] Brandl | Donor coordination: Collective distribution of individual contributions[END_REF][START_REF] Aziz | Proportionally representative participatory budgeting: Axioms and algorithms[END_REF]. One aspect of PB which is neglected by existing methods is project interactions: E.g., consider a toy PB instance consisting of 3 projects -one school, s, and two parks, p1 and p2; in many cases, it is natural to assume that, while certain voters might wish to have one park built in their city, not many voters would feel that funding two parks (especially if these parks are geographically close to each other) is a good use of public funds. (The above example is of substitutions, as the two parks are substitutes for each other. Indeed, there could be other types of interactions, most notably complementarities, which correspond to positive interactions between projects; for presentation, we consider here only substitutions).

In this paper we are interested in figuring out the so-called substitution structure of the set of projects in a PB instance. E.g., in the toy example described above, it might indeed be the case that the two parks p1 and p2 are substitutes for most voters. So, the substitution structure of this example would be the partition {{s}, {p1, p2}}; each part (i.e., {s} and {p1, p2}) of this partition is referred to a substitution class). In particular, taking a utilitarian approach, assume that each voter has a utility for each bundle of projects; so, the utility of a voter from a set of projects P ⊆ {s, p1, p2} is u(P ). Then, the substitution structure means that the utility function is submodular wrt. projects of the same part in the partition: That is, u({p1, p2}) ≤ u({p1}) + u({p2}).

There are several ways by which an organizer of a PB instance might tackle this aspect of substitutions:

Dictatorial decision: One possibility would be for the organizer to decide herself upon the substitution structure -then, she might, e.g., ask voters to approve projects (i.e., define the election to be an approval one), but do not allow voters to approve more than one project in each substitution class. Explicit Exponential Elicitation: Another possibility would be for the organizer to allow each voter to explicitly specify her utility from each bundle of projects, however this would mean an exponential explosion and thus is probably not feasible. Preliminary Election: A yet another possibility would be for the organizer to perform a preliminary election, in which she asks from the voters -perhaps only a subset of the voters -to provide their substitution structures. Then, the organizer can aggregate those partitions provided by the voters and use the aggregated partition as the global substitution structure.

Here we choose the last option, thus concentrate on the subproblem of aggregating partitions. Here, one would be wondering why do we want to conduct election in two phases, that is, first asking for substitution structures from some voters, and then conduct standard election. The one reason is that elicitation cost is high. Since this is the preliminary step of participatory budgeting, it is natural that we only ask some people to give substitution structure, say only secretaries of different societies. Of course, the question of how to use the aggregated partition in the subsequent participatory budgeting election is central; we do not tackle it in the current paper, however, to maintain focus, we leave it as the main future work. We acknowledge one natural criticism of our approach, namely that we assume that the substitution structure is somehow global, in the sense that it can be fixed to be the same for all voters. While, indeed, this might not always be the case, we believe that in most PB instances it is roughly global. Verifying this intuition and identifying cases in which this intuition is true and other cases in which it is violated is, again, an interesting avenue for future research.

Finally, while here we concentrate on identifying aggregated partitions to be used for deciding on substitution structures for PB instances, we briefly mention other motivations for this task:

Visualizing projects: A PB organizer shall distribute a pamphlet explaining the projects to the voters. On each page only a certain number of projects can be explained, thus in fact the pamphlet partitions the projects into pages. Using a partition aggregation method might help here, in particular, as the presentation affects the preferences.

Community structure: Consider the task of identifying communities in a set of agents. One way to achieve this is to request each voter to provide a partition of the set of agents to communities and then using an algorithm for aggregating partitions. However, in some cases, asking people to vote for communities might yield distorted results.

Related Work

A special case of the partition aggregation problem is cluster ensembles [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF] which is also known as cluster aggregation [START_REF] Gionis | Clustering aggregation[END_REF] and consensus clustering [START_REF] Dörnfelder | On the parameterized complexity of consensus clustering[END_REF]. In cluster aggregation, we are given a set of clusterings, and the goal is to find a clustering which agrees with the input clusterings as much as possible. Cluster aggregation is polynomial-time solvable when the input has two partitions, while it is APX hard when we have three partitions [START_REF] Bonizzoni | On the approximation of correlation clustering and consensus clustering[END_REF]. Strehl and Ghosh [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF] proposed some techniques for cluster aggregation. In one of their approaches, given a set of clustering, they construct a hypergraph, and find a hyperedge separator that partitions the hypergraph into k unconnected components of approximately the same size. Gionis et al. [START_REF] Gionis | Clustering aggregation[END_REF] gave some approximation algorithms. They considered cluster aggregation problem and correlation clustering. In cluster aggregation, they measure the dissimilarity between the clusterings. Let V be the given set of objects, and C1, . . . , Cm be the set of clusterings. For two objects u and v in V , and two clusterings C1, C2, du,v(C1, C2) = 1, if u and v are in same part in C1 and different parts in C2, or vice-versa, otherwise 0. The dissimilarity between two clusterings C1 and C2 is defined as d(C1, C2) = u,v∈V du,v(C1, C2). The goal is to find a clustering C such that the total dissimilarity, m i=1 d(C, Ci), is minimized. This function is also known as total Mirkin distance. They also studied the maximization version of consensus clustering. Towards this, they defined similarity between two partitions C1 and C2, denoted by s(C1, C2), as the number of objects which either belong to the same part in both the partitions or in different parts in both partitions. The goal is to find a partition C such that m i=1 s(Ci, C) is maximised. Dornfelder et al. [START_REF] Dörnfelder | On the parameterized complexity of consensus clustering[END_REF] proved that cluster aggregation is NP-hard even when every partition contains at most two clusters. They proposed an FPT algorithm for cluster aggregation with respect to parameter average Mirkin distance. They also studied the local search variant of the problem, and showed that the problem is W [START_REF] Aziz | Egalitarian committee scoring rules[END_REF]-hard when parameterized by radius of the Mirkin-distance neighborhood.

We also mention work on aggregating graphs [START_REF] Endriss | Graph aggregation[END_REF], as aggregating partitions is equivalent to aggregating cluster graphs (graphs that are a collection of disjoint cliques).

Formal Model

Formally, we have a set, P = {p1, . . . , pm}, of projects, (In PB, there is a cost c(p) for each p ∈ P ; we do not include these in our formal model as they do not affect the substitution structure) and a set, V = {v1, . . . , vn}, of voters, where voter vi corresponds to a partition Pv i of P . A partition Pv is a disjoint set of parts whose union is P ; i.e., Pv = {p 1 , . . . , p z }, where for every i, j ∈ [z], p i ∩ p j = ∅ and ∪ j∈[z] p j = P . Each p j is referred to as a part of the partition Pv. A partition aggregation method is a function taking n partitions of P and returning a partition S of P , referred to as the aggregated partition. (We ignore issues of tie-breaking as they clutter the presentation without adding significant insights.) We denote an instance of partition aggregation as (P, C), where P is the set of projects and C is the collection of n partitions of P .

A Utilitiarian Approach

The main question we are studying is how to define a "good" partition. Here we take a utilitiarian approach: We assume that each voter v, based on her partition Pv, would derive a certain utility from each possible aggregated partition S. While these utilities are unknown, they might be estimated (similarly to set extensions, which are used to estimate utilities over committees based on utilities over single candidates in multiwinner elections). Given a specific way of estimating such utilities over the set of possible partitions, a natural partition aggregation method would return, as the aggregated partition, a partition which maximizes the sum -over the voters -of these utilities. Such a utilitarian approach has been applied successfully for many social choice settings, including multiwinner elections [START_REF] Faliszewski | Committee scoring rules: Axiomatic classification and hierarchy[END_REF] and participatory budgeting [START_REF] Faliszewski | A framework for approval-based budgeting methods[END_REF].

Example 1 Consider the set of projects P = {p1, p2, p3, p4} and a voter v with the partition Pv = {{p1, p2}, {p3, p4}}. It is natural to assume that the utility of voter v from the partition S1 = {{p1, p2}, {p3}, {p4}} would be fairly high, as Pv and S1 are quite similar. Furthermore, the utility of v from S2 = {{p1}, {p2}, {p3}, {p4}} might be less than her utility from S1, as S2 seems to be less similar to Pv than S1 is.

Our utilitarian approach is formally defined below.

Definition 1 (Utility function) Let P be a set of m projects and let P be the set of all partitions of P . A utility function is a function f : P × P → N. For a voter v and a possible aggregated partition p, f (v, p) is understood as the utility that voter v gets from p; the higher the better.

Two Utility Functions

We consider two utility functions. The PA utility function is perhaps the first utility function one might think of: The utility of a voter equals the number of pairs for which her vote agrees with the aggregated vote. The PAM utility function is slightly less natural as the utility is the number of pairs for which the voter agrees with the aggregated vote, minus the number of pairs not in the same partition in the voter's partition but in the same partition in the aggregated vote. Thus, in essence, we define a larger fine for merging a pair of projects unnecessarily (a fine of -1), than for splitting a pair of projects unnecessarily (a fine of 0). The reason for this asymmetry is our motivation from substitution structures: We believe that an aggregated partition that defines a set of projects as substitutions to each other, while most voters prefer not to have them defined as such is more harmful than an aggregated partition that simply fails to define a substitution in cases in which it should.

Number of pairwise agreements (PA): Let p1, p2 be two projects in P . For a voter v, and an aggregated partition S, let

δ PA v,S (p1, p2) =      1 if p1, p2 are in same (different) part(s)
in both Pv and S ; 0 otherwise . We define the Number of pairwise agreements (PA) utility function for voter v from S to be as follows:

f PA (v, S) = p 1 ,p 2 ∈P δ PA v,S (p1, p2) .
Number of pairwise agreements minus number of mergings (PAM): Let p1, p2 be two projects in P . For a voter v, and aggre-gated partition S, let We define the Number of pairwise agreements minus number of mergings (PAM) utility function for voter v from S to be:

δ PAM v,S (p1, p2) =                    1 if p1,
f PAM (v, S) = p 1 ,p 2 ∈P δ PAM v,S (p1, p2) .

Aggregation Goals

Given a utility function f , we consider two partition aggregation goals: Maximizing the sum of utilities (Total) and maximizing the minimum utility (Egal).

Definition 2 (Total Utility (Total)) Given a set of m projects, a collection of n partitions, P1, . . . , Pn, and a utility function f , the goal in Total Utility aggregation is to find a partition S such that

i∈[n] f (Pi, S) is maximized.
That is, in Total Utility aggregation we look for a partition that maximizes the total utility (i.e., i∈[n] f (Pi, S)). In the decision version of the problem, given an integer k additionally, we look for a partition that has total utility at least k. We use the same problem name for optimisation as well as decision version of the problem as it will be clear from the context.

We also consider egalitarian aggregation methods, in which we care for the least satisfied voter (similarly in spirit to egalitarian committee scoring rules [START_REF] Aziz | Egalitarian committee scoring rules[END_REF]).

Definition 3 (Egalitarian Utility (Egal)) Given a set of m projects, a collection of n partitions, P1, . . . , Pn, and a utility function f , in Egalitarian Utility aggregation the goal is to find a partition S such that min i∈[n] f (Pi, S) is maximized.

In the decision version of the problem, given an integer k additionally, we look for a partition that has Egalitarian Utility at least k.

Illustrating Example

Our two utility functions and two aggregation types define four aggregation methods: Total-PA, Egal-PA, Total-PAM, and Egal-PAM. Consider the following set of partitions to illustrate the difference between these methods. Let Pv 1 = {{p1, p2, p3}}, Pv 2 = {{p1}, {p2, p3}}, and Pv 3 = {{p1}, {p2}, {p3}}. Let S = {{p1, p2}, {p3}} be an aggregated partition. We first describe Total-PA. For the pair of projects p1, p2, δ PA v 1 ,S (p1, p2) = 1 as p1 and p2 are in same part in both the partitions; however δ PA v 1 ,S (p1, p3) = 0 as p1 and p3 are in same part for v1 and in different parts in S. Similarly, δ PA v 1 ,S (p2, p3) = 0. Hence, the PA utility for voter v1 from S, f PA (v1, S), is 1. Similarly, the PA utility for voter v2 and v3 from S are 1 and 2, respectively. The Total-PA utility from S is 4. The Egal-PA utility is 1. Next, we describe Total-PAM utility. For the pair of projects a, b, δ PAM S,v 1 (p1, p2) = 1; however δ PAM S,v 1 (p1, p3) = 0 and δ PAM S,v 1 (p2, p3) = 0. Hence, the PAM utility for v1 from S, f PAM (v1, S), is 1. Furthermore, δ PAM S,v 2 (p1, p2) = -1 as p1 and p2 are in different parts for v2, while they are in the same part in S; δ PAM S,v 2 (p1, p3) = 1 and δ PAM S,v 2 (p2, p3) = 0. Hence, the PAM utility for v2 from S is 0. Similarly, the PAM utility for v3 from S is 1. Therefore, the Total-PAM utility from S is 2, and the Egal-PAM utility is 0.

Computational Complexity

First, we study the computational complexity, and show intractability, of our partition aggregation methods.

Total-PA and Total-PAM

Recall that the problem of finding an aggregated partition with Maximum Total-PA is equivalent to the Consensus Clustering problem. Since Consensus Clustering is known to be NP-hard even for three partitions [START_REF] Dörnfelder | On the parameterized complexity of consensus clustering[END_REF], we have the following result.

Proposition 1 Total-PA is NP-hard even for three voters.

Consensus Clustering is also known to be NP-hard when every input partition has at most two parts [START_REF] Dörnfelder | On the parameterized complexity of consensus clustering[END_REF]. Hence, we have following result.

Proposition 2 Total-PA is NP-hard even when every voter has at most two parts.

We next present our intractability result for Total-PAM.

Theorem 1 Total-PAM is NP-hard even when each partition contains at most two parts.

Proof. We give a polynomial time reduction from the known NPhard problem Cluster Deletion (Given a graph G, and an integer k; we shall decide the existence of at most k-sized set of edges whose deletion from G results into a cluster graph(i.e., a disjoint union of cliques)) [START_REF] Shamir | Cluster graph modification problems[END_REF]. Let (G, k) be an instance of the Cluster Deletion problem. Let |V (G)| = n, |E(G)| = m. Without loss of generality, assume that n -2 = 2 , for some positive integer . We first construct the set of projects P . For each vertex u ∈ V (G), we add a project u in the set P . Now, we construct a collection of partitions, C, of projects. For every pair of vertices u, v ∈ V (G), we create a collection of partitions Cuv as follows.

If uv ∈ E(G), then |Cuv| = 3 • 2 2 -1 , otherwise |Cuv| = 3 • 2 4 -1 . If uv ∈ E(G),
then in every partition in Cuv, u and v are in same part; otherwise u and v are in different parts in every partition in Cuv. For every pair of vertices x, y ∈ V (G) \ {u, v}, there are |Cuv | /3 partitions in Cuv in which x and y are in different parts, and 2•|Cuv | /3 partitions in which x and y are in same part. This collection of partitions C can be construed in polynomial time, however we skip the justification due to space constraint. The intuitive idea for such a collection of partitions is that for a pair of project x, y, the total PAM utility due to partitions in Cuv, where u, v are distinct from x, y, is 2 2 -1 for any aggregated partition, as if x, y are in different parts in the aggregated partition, then the total PAM utility due to these partitions is

2•|Cuv | /3 -|Cuv | /3 = |Cuv | /3, otherwise |Cuv | /3.
In essence, the utility of pair of project for Cu,v does not depend on the parts to which x, y belongs in the aggregated partition. However, for project u, v, total PAM utility for Cu,v depends on their parts in the aggregated partition. The set of partitions in our instance is C = ∪ u,v∈V (G) Cuv. We set total PAM utility as

k =2 4 -1 n(n -1) 2 -m n(n -1) 2 + 2 + 2 2 -1 m n(n -1) 2 -m + n + 2 -3k
Next, we show the equivalence between the instance (G, k) of cluster deletion and the instance (P, C) of total PAM.

In the forward direction, let X be a subset of edges of size k such that G = G -X is a cluster graph. We construct an aggregated partition Y for the instance (P, C) as follows. Two projects u, v ∈ P are in same part in Y if and only if their corresponding vertices in G are in same clique. Note that the number of parts in Y is same as the number of cliques in G . Now, we show that the total PAM utility for Y is at least k . Recall that for any pair of projects u, v ∈ P , for all collections Cxy, where x, y

∈ V (G)\{u, v}, C∈Cxy δC,Y (u, v) = |Cxy | /3. Note that if uv / ∈ E(G), then uv / ∈ E(G ), as we only delete edges from G. Therefore, for u, v ∈ P , if (u, v) / ∈ E(G), then C∈C\Cuv δC,Y (u, v) = 2 4 -1 ( n(n-1) /2 -m -1) + 2 2 -1 m. Furthermore, C∈Cuv δC,Y (u, v) = 3 • 2 4 -1 . There- fore, if uv / ∈ E(G), then C∈C δC,Y (u, v) = 2 4 -1 ( n(n-1) /2 - m + 2) + 2 2 -1 m. We further note that if uv ∈ E(G ), then uv ∈ E(G), as we do not add any edge to G. Therefore, for u, v ∈ P , if (u, v) ∈ E(G), then C∈C\Cuv δC,Y (u, v) = 2 4 -1 ( n(n-1) /2 -m) + 2 2 -1 (m -1). Furthermore, if uv ∈ E(G ), then C∈Cuv δC,Y (u, v) = 3 • 2 2 -1 . Therefore, if uv ∈ E(G ), then C∈C δC,Y (u, v) = 2 4 -1 ( n(n-1) /2 -m) + 2 2 -1 (m + 2); and if uv ∈ E(G) but uv / ∈ E(G ), then C∈C δC,Y (u, v) = 2 4 -1 ( n(n-1) /2 -m) + 2 2 -1 (m -1)
. Since there can be at most k edges in G which are not in G , total PAM utility for P is

2 4 -1 n(n -1) 2 -m + 2 + 2 2 -1 m n(n -1) 2 -m + 2 4 -1 n(n -1) 2 -m + 2 2 -1 (m -1) m +3 • 2 2 -1 (m -k) = k
This completes the proof in the forward direction.

In the reverse direction, let Y be an aggregated partition to (P, C)

such that total PAM utility for Y is at least k . Let X = {uv ∈ E(G) | u and v are in different parts in Y }. Claim 1 If u and v belong to same part in Y , then uv ∈ E(G).

Proof.

Towards the contradiction, suppose that there exists projects u and v in a part in Y such that uv / ∈ E(G). Then,

C∈Cuv δC,Y (u, v) = -3 • 2 4 -1 (as u and v are in different parts in each partition in Cuv). Therefore, C∈C δC,Y (u, v) = 2 4 -1 n(n -1) 2 -m-1 +2 2 -1 m-3•2 4 -1
Hence, total PAM utility for Y is

2 4 -1 n(n -1) 2 -m + 2 + 2 2 -1 m n(n -1) 2 -m -1 + 2 4 -1 n(n -1) 2 -m -1 + 2 2 -1 m -3 • 2 4 -1 + 2 4 -1 n(n -1) 2 -m + 2 2 -1 (m -1) m + 3 • 2 2 -1 (m -k1) = 2 4 -1 n(n -1) 2 -m n(n -1) 2 + 2 -6 • 2 4 -1 + 2 2 -1 m n(n -1) 2 -m + n + 2 -3k1 < k as k < m ≤ 2 2 +1
, a contradiction to the assumption that Y is a solution to (P, C). Hence, G -X is a cluster graph. Next, we show the size bound on X.

Claim 2 |X| ≤ k.

Proof. Towards the contradiction, suppose that

|X| > k. Since G -X is a cluster graph, if uv / ∈ E(G), then uv / ∈ E(G -X). Since |X| > k, there are at least k + 1 pairs u, v ∈ V (G)
such that u and v are in same part in each partition in Cuv but in different parts in Y . We can show that in this case the total PAM utility for Y is less than k , a contradiction to that Y is a solution to (P, C). The reverse direction follows from Claim 1 and 2.

Egalitarian-PA and Egalitarian-PAM

Proposition 3 Egalitarian-PA and Egalitarian-PAM are NP-hard.

Proof.

Due to lack of space, we only give a sketch of the reduction. We reduce from Unary Bin Packing, seen as a partition problem (one seeks a partition of [kB] into k parts of size B where items, represented as disjoint subsets, must be included in single parts). We use [kB] as the set of projects, and first build two voters: R := {[kB]} and S := {{1}, . . . , {kB}}. We can enforce that the solution must have utility at least tR := k B 2 with R and tS := kB 2 -tR with S (tS := kB 2 -2tR in the PAM model). These two thresholds yield a partition with k blocks of size B. Then, for each pair of elements e = (x, y) from the same item, we enforce that both elements are in the same part using a partition Qe = {{x}, {y}, [kB] \ {x, y}} with utility threshold tQ := tR + 2(m -2B) + 3 (or tQ := tR + 4(m -2B) + 6 in the PAM model). Together, these constraints ensure that the target solution is a valid bin packing of the original instance (we achieve distinct utility thresholds with additional gadgets appended to each partition).

Here we consider various axiomatic properties that are relevant for partition aggregation methods, and test our partition aggregation methods against them. While it is possible to define many axiomatic properties, we chose axioms that seem especially relevant, with the application of aggregating substitution structures in mind. Our results, regarding both the computational complexity and the axiomatic properties of our four partition aggregation methods -Total-PA, Egal-PA, Total-PAM, and Egal-PAM -are summarized in Table 1.

The axiom of Unanimity, defined next, says that if all voters agree on whether some two projects shall be in the same part or in different parts (i.e., all voters are unanimous wrt. to this pair of projects), then the aggregated partition shall also agree with the voters regarding these two projects.

Definition 4 (Unanimity) A partition aggregation method R satisfies Unanimity if the following hold: Let P1, . . . , Pn be the set of partitions of projects P = {p1, . . . , pm}. If two projects pi and pj, i, j ∈ [m], belong to the same part in Pi, for all i ∈ [n], then pi, pj belong to the same part in the aggregated partition. Similarly, if pi, pj belong to different parts in Pi, for all i ∈ [n], then pi, pj belong to different parts in the aggregated partition.

While Unanimity requires that the aggregated partition agrees with the voters on those pairs of projects for which all voters are in complete agreement, majority-based aggregation considers pairs of projects with majority agreement among the voters. As we show next, such aggregated partitions need not exist; thus, we require an aggregation method to output such partitions only when they exist. Definition 5 (Majority based aggregation) An aggregated partition P is majority-based if any two projects p1, p2 are in the same part in P if and only if p1 and p2 are placed in the same part for more than half of the voters. A partition aggregation method R satisfies Majority-based aggregation if it always outputs majority-based aggregated partitions, whenever such an aggregated partition exists.

Remark 1 One might consider a continuum of axioms between

Majority-based aggregation and Unanimity, by employing supermajorities: An aggregated partition p would place a pair of projects in the same partition iff at least a δ-Supermajority among the voters does so.

We also consider an adaptation of the fundamental axiom of Independent of Irrelevant Alternatives to our setting of aggregating partitions: We refer to our adaptation as Independent of Irrelevant Projects. In essence, it means that if the restriction of some two profiles to a pair of projects is the same, then the restriction to this pair of projects of both aggregated partition shall be the same.

Definition 6 (Independent of Irrelevant Projects) A partition aggregation method R satisfies Independent of Irrelevant Projects if the following holds: Let P and P be two partition profiles and let s and s be their aggregated partitions according to R. Let p1 and p2 be two projects such that the number of voters that places them in the same part in P and in P are the same. Then, s and s shall either both place p1 and p2 in the same part or in different parts.

Unanimity

Here we compare our four aggregation methods wrt. to the axiom of Unanimity: We wish to identify which of our methods are Unanimous and which are not. First, we note that a unanimous partition always exists, and can be found in polynomial time:

Observation 1 A unanimous partition always exists, and can be found in polynomial time.

The proof follows from the fact that we can output any partition that is provided by some voter. Note that it is unanimous.

Next we show that Total-PA is also Unanimous. This is intuitively appealing, as, to maximize the total utility, it seems natural for the aggregated partition to agree with the voters at least on those pairs of projects for which the voters are in total agreement among themselves.

Theorem 2 Total-PA is unanimous.

Proof. Let S be an optimal aggregated partition for a set of voters, {v1, . . . , vn}, that maximizes total PA. Let p1 and p2 be two projects that are in same part in all the partitions while in different parts in S. We claim that there exists an aggregated partition S in which p1 and p2 are in same part and Total-PA utility for S is same as that of S.

We first create S as follows. Initially, S is same as S. Let S1 and S2 be two parts containing p1 and p2, respectively. We delete p2 from S2, and add it to S1. Next, we prove that Total-PA utility from S is larger than that from S. We denote new S1 and S2 as S 1 and S 2 , respectively. Consider parts S1 and S2 in the partition S. Let n i=1 p∈S 1 ∪S 2 δS,v i (p, p1) = n1 (number of pairwise agreements between project p1 and the projects in S1 ∪ S2), n i=1 p∈S 1 ∪S 2 δS,v i (p, p2) = n2 (number of pairwise agreements between project p2 and the projects in S1 ∪ S2). Now, we first claim that n1 = n2. Towards the contradiction, suppose that n1 > n2. Then, when we move p2 from S2 to S1, the utility for p2 and the vertices in S1 ∪ S2 is n1 as p1 and p2 are in same part in all the partitions. Note that the utility for other pairs of projects do not change. Therefore, the Total PA for this partition is greater than for S, a contradiction. Similarly, if n2 > n1, then by moving p1 from S1 to S2, we obtain a partition whose Total-PA is more than that from S, a contradiction. Therefore, n1 = n2, and hence, total PA utility for S is same as that of S.

Next, we consider the case when p1 and p2 are in different parts in all the partitions while in the same part, say S1, in S. Let n i=1 p∈S 1 δS,v i (p, p1) = n1 (number of pairwise agreements between project p1 and the projects in S1), and n i=1 p∈S 1 δS,v i (p, p2) = n2 (number of pairwise agreements between project p2 and the projects in S1). Since p1 and p2 are in different parts for all the voters, if p2 / ∈ S1,

n i=1 p∈S 1 δS,v i (p, p2) = n1. Similarly, if p1 / ∈ S1, n i=1 p∈S 1 δS,v i (p, p1) = n2.
Therefore, if n1 > n2, then deleting p2 from S1, and adding a part {p2} to S increase the total PA utility, a contradiction to that S maximises total utility. Similarly, if n2 > n1, then deleting p1 from S1, and adding a part {p1} to S increase the total PA utility, a contradiction. Hence, n1 = n2. Thus, if we create a partition by deleting p2 from S1, and adding a part {p2} to S, total PA utility remains same.

In contrast, Egal-PA is not Unanimous. This is also intuitively appealing, as egalitarian methods care for the least satisfied voter.

Proposition 4 Egalitarian-PA is not unanimous.

Proof.

We show this by an example. Suppose that we have 2 voters and 5 projects, p1, p2, p3, p4, p5. Let the partition for first voter be {{p1, p2, p3, p4, p5}}, and for second voter it is {{p1, p2}, {p3, p4, p5}}. Let us consider some possible aggregated partition. In particular, we consider all partitions in which p1 and p2 are in the same part, and one partition in which p1 and p2 are in different parts to show that any partition containing p1 and p2 in same part can not be optimal solution of Egal-PA. Note that partitions {{p1, p2, p3, p4}, {p5}}, {{p1, p2, p3, p4}, {p4}}, and {{p1, p2, p4, p5}, {p3}} have same PA utility for both the voters; therefore in Table 2, we only mention one of these. Similarly, we omit some partitions in the table that contains p1, p2 in same part but have same utilities as some partition in the table. Next we consider Total-PAM. While we show that, similarly to Total-PA, Total-PAM also satisfies Unanimity, we conjecture that Egal-PAM, similarly to Egal-PA, does not satisfy Unanimity.

Theorem 3 Total-PAM is unanimous.

Proof. Let S be an optimal aggregated partition for a set of voters, {v1, . . . , vn}. Let p1 and p2 be two projects which are in same part for all the voters, while in different parts, say S1, S2, respectively, in S. Let n i=1 p∈S 1 ∪S 2 δS,v i (p, p1) = n1 -n2 (number of pairwise agreements between project p1 and the projects in S1 ∪ S2 minus number of mergings), and n i=1 p∈S 1 ∪S 2 δS,v i (p, p2) = n3 -n4. Note that if n1 -n2 > n3 -n4, then moving p2 from S2 to S1 increases the total PAM utility, a contradiction to optimality of S. Similarly, if n3 -n4 > n1 -n2, then moving p1 from S1 to S2 increases the total PAM utility, a contradiction. Therefore, n1 -n2 = n3 -n4. Thus, moving p1 from S1 to S2 does not change the total PAM utility. Hence, there exists an optimal aggregated partition in which p1 and p2 are in same part.

Next, we show that if p1 and p2 are in different parts for all the voters, then p1 and p2 are not in the same part in any optimal aggregated partition. Towards the contradiction, suppose that there exists an optimal aggregated partition, S, in which p1 and p2 are in same part, say S1. Note that for a project p,

if n i=1 δS,v i (p, p1) = n1, then n i=1 δS,v i (p, p2) = -n1, and vice-versa. Let n i=1 p∈S 1 δS,v i (p, p1) = n1 -n2, and n i=1 p∈S 1 δS,v i (p, p2) = n3 -n4. Using above observation, n4 = n 4 + n1 and n2 = n 2 + n3. Note that n 2 = n 4 . Therefore, n1 -n2 +n3 -n4 < 0.
Let us consider two cases: either n1 -n2 < 0 or n1 -n2 ≥ 0. If n1 -n2 < 0, then we delete p1 from S1 and add it as a singleton in S. Note that now n i=1 δS,v i (p, p1) ≥ n (as only merging two projects gives negative terms, not splitting in two parts). Hence, n i=1 δS,v i (p, p1) + n i=1 δS,v i (p, p2) ≥ n + n3 -n4. Since n1 -n2 < 0, the total PAM utility from new partition is larger than from the former one. Consider the other case. Let n1 -n2 ≥ 0. In this case, we delete p2 from S1 and add it as a singleton in S. As argued above, here also total utility increases.

Majority-Based Aggregation

Next we consider Majority-based partitions. First, we show that, contrary to Unanimous partitions, Majority-based partitions do not always exist.

Proposition 5 A majority based aggregated partition need not exist.

Proof.

Consider three voters, v1, v2, v3, and three projects p1, p2, p3. Let the partitions corresponding to v1, v2, and v3 be Pv 1 = {{p1, p2}, {p3}, Pv 2 = {{p1, p2, p3}}, and Pv 3 = {{p1, p3}, {p2}}. According to the property of Majoritybased aggregation, we shall have the following: (1) p1, p3 shall be in the same part; (2) p1, p2 shall be in the same part; and (3) p2, p3 shall be in different parts. As the three constraints above cannot be simultaneously satisfied, we conclude that there is no Majority-based partition for this profile.

In a sense, the counterexample in the above proof is similar to the canonical counterexample showing the existence of Condorcetcycles in single-winner elections (i.e., voters a > b > c, b > c > a, and c > a > b, requiring the contradicting requirements of a > b, b > c, and c > a as the canonical example of Condorcet paradox.

Nevertheless, Majority-based aggregation exists for some profiles; for these profiles, it can be found in polynomial time.

Theorem 4 A majority based aggregated partition can be found in polynomial time, if it exists.

Proof. Let P be the set of projects. Let V be the set of voters. We construct an aggregated partition S iteratively as follows. Initially, let S = ∅. In each iteration i, we add a part Si in S as follows: consider a project x ∈ P \ (∪ i-1 j=1 Sj) (that is a project that has not been added in any part in previous iterations); add it in the part Si, and add all the projects x ∈ P \ (∪ i-1 j=1 Sj ∪ {x}), such that x and x are in same part for more than half of the voters, in Si. Now, we check whether every two projects in Si are in same part for more than half of the voters. If not, then the algorithm returns No. We also check whether there exists projects y ∈ Si and y ∈ Sj, where i = j, such that y and y are in different parts for at least half of the voters. If not, then the algorithm returns No. We repeat until there is a project which is not placed in any part in S; and return set S. Clearly, the algorithm runs in polynomial time.

Next we prove the correctness of the algorithm. Indeed, if the algorithm returns a partition S, then it is a majority based aggregated partition, as at every step the algorithm checks this property. Now, we show that if the algorithm returns No, then there is no majority based aggregated partition for V . Towards the contradiction, let S be a majority based aggregation for V . Note that the algorithm returns No in two cases: (1) there are two projects, say y, z, in a part, say Si, in S that are not in same part for more than half of the voters, or (2) there are two projects, say y, z, in different parts, say Si, Sj, respectively, of S that are in same part for more than half of the voters. Consider the case (1). Clearly, y and z are in different parts in S . Let the algorithm first added project x to Si. Thus, x, y and x, z are in same part for more than half of the voters, as the algorithm added y, z in Si, a contradiction that S is majority based aggregation. Next, consider case (2). Clearly, y, z are in same part in S . Let the algorithm first added project x to Si. Then, algorithm added y to Si but not z. This implies that x, y are in same part for more thant half of the voters but not x, z. Since the part containing y, z in S does not contain x as x, z are in different parts for at least half of the voters, a contradiction that S is a majority based aggregation, as x, y are in different parts in S .

We have following corollary from the algorithm described above.

Corollary 1

The existence of a Majority-based partition for a given profile can be decided in polynomial time.

Moreover, note that, if it exists, then a Majority-based aggregated partition is unique. Next, we check whether our partition aggregation methods output the Majority-based partition whenever it exists.

Theorem 5 If a majority based aggregated partition exists, then it maximizes Total-PA.

Proof. Let V be a set of partitions corresponding to all the voters. Let S be the majority based aggregated partition for V . Let S = S be an optimal solution of Total-PA for V . Since majority based aggregated partition is unique, S is not a majority based aggregated partition. Thus, either (1) there exists a part Si in S containing two projects that are not in same part for more than half of the voters, or (2) there exists two parts Si, Sj in S such that there is a project in Si and a project in Sj that are in same part for more than half of the voters.

Consider case (1). Let x and y be two projects in Si that are in different parts for at least half of the voters. Let Mx be the set of projects that are in same part with x for more than half of the voters, and Nx be the set of projects that are not in same part with x for more than half of the voters. Note that a pair of projects a, b, where a ∈ Mx and b ∈ Nx are not in same part for more than half of the voters, otherwise majority based aggregated partition does not exist. Also, note that every two projects in Mx are in same part for more than half of the voters, otherwise majority based aggregated partition does not exist. Now, create a new partition by deleting Nx from Si, and add a new set of projects Nx to S. Since every pair of project a, b, where a ∈ {x} ∪ Mx and b ∈ Nx, are in different parts for at least half of the voter; either the total PA utility of new partition is same as that of S or larger than that of S. It can not be larger as S is an optimal solution of Total-PA. We apply this step for all the parts in Si that contains at least two projects that are not in same part for more than half of the voters. Note that the total PA utility for new partition is same as that of S . Let us denote this new partition by S .

Next, we consider case [START_REF] Aziz | Proportionally representative participatory budgeting: Axioms and algorithms[END_REF]. Note that if there exists two parts Si, Sj in S such that there is a project in Si and a project in Sj that are in same part for more than half of the voters, then such parts also exist in S (because we have not merged any two parts). Let Sp and Sq be two parts in S that contains x and y, respectively, such that x and y are in same part for more than half of the voters. We merge parts Sp and Sq in the partition S . Since S does not contain any part that violates majority based aggregation property due to case (1), all the pair of projects in Sp(or Sq) are in same part for more than half of the voters. Note that every pair of projects a, b such that a ∈ Sp and b ∈ Sq are in same part for more than half of the voters, otherwise majority based aggregated partition does not exist. Therefore, merging Sp and Sq increases the total PA utility, a contradiction to the optimality of S. Hence, S does not contain parts that satisfies condition in case (2).

Using the same example as in Lemma 4, we have following result.

Proposition 6 Egalitarian-PA does not satisfy Majority-based aggregation.

We go on to consider Total-PAM and Egal-PAM.

Proposition 7 Total-PAM does not satisfy Majority-based aggregation.

Proof. We show this by a counterexample. Consider a set of 2 projects, {p1, p2}; and a set of 5 voters. Let the partition for 3 voters be {{p1, p2}}, and for 2 voters, the partition is {{p1}, {p2}}. Note that {{p1, p2}} is a majority based aggregated partition; its total PAM utility is 0. However, the total PAM utility for {{p1}, {p2}} is 1.

Using the same example as in Lemma 7, we have following result.

Proposition 8 Egalitarian-PAM does not satisfy the property of majority based aggregation.

Independent of Irrelevant Projects

Next we consider our adaptation of the axiom of Independence of Irrelevant Alternatives to our setting. Proposition 9 Total-PA does not satisfy Independence of Irrelevant Projects.

Proof. We show this by a counterexample. Let P and P be two profiles, and we have 3 voters. Suppose that the partitions for P are Pv 1 = {{p1, p2, p3}, {p4}}, Pv 2 = {{p1, p2, p3}, {p4}}, and Pv 3 = {{p1}, {p2, p3}, {p4}}; and for P , partitions are P v 1 = {{p1, p2, p3}, {p4}}, P v 2 = {{p1, p2, p4}, {p3}}, and P v 3 = {{p1, p3}, {p2, p4}}. We consider here pair of project p1, p2. In both the profiles p1 and p2 are in same part for 2 voters. Let S and S be aggregated partitions for P and P , respectively. Since Total-PA is unanimous (Lemma 2), projects p3 and p4 are in different parts in both the partitions S and S . Moreover, in S, {p4} is a singleton, and p2, p3 are in same part. Now, if p1 is in the same part as in p2, p3; total PA utility for S is 16, otherwise 14. Now, let us consider partition S . Suppose that p1 and p2 are in same part. Then, there are three cases: either S = {{p1, p2}, {p3}, {p4}} or S = {{p1, p2, p3}, {p4}} or S = {{p3}, {p1, p2, p4}}. In all the case total PA utility is 11. However, if S = {{p1, p3}, {p2, p4}}, then total PA utility is 12.

Observe that, if an aggregation rule is not unanimous, then it can not satisfy independent of irrelevant projects properties as we can have one profile in which all the projects are in the same part (or, equivalently, in different parts) for all voters, and another profile which is an instance that violates the Unanimity axiom. Hence, due to Lemma 4, we have following result.

Corollary 2 Egalitarian-PA does not satisfy Independence of Irrelevant Projects.

Outlook

We have studied several partition aggregation methods for the setting in which each voter provides an arbitrary partition over the same set of projects, and the aggregation goal is to output a single aggregated partition. Here we discuss few other variants of this setting and describe some use-cases for each of them.

Partitions with k Parts

In certain cases it might be desired to require that each input partition, as well as the output partition, shall consist of at most a given number k of parts. As a natural use-case, consider a set of projects for participatory budgeting where the election organizer wishes to partition the projects into thematic subjects, to ease the elicitation process. It is natural to require not-too-many parts, does requiring some upper bound of k parts. Such scenarios can be modeled as follows: Given n input partitions, each consisting of at most k parts, the aggregation method shall output a single aggregated partition, also consisting of at most k parts.

As a different example, of a different flavor, consider a system employing liquid democracy, in which the system wishes to cluster the proposals on the table into predefined subjects (say, education, health, etc.). Then, one approach would be to ask a subset of the voters to assign the proposals to the different, given subjects. Such a scenario can be modeled as follows: We have a set of k types and each voter shall partition the projects into these types. The aggregation method shall then output a partition of the projects into these types.

Observe that, in the first example, the k parts are indistinguishable, while, in the second example, these are distinguishable, as they have different IDs. We thus refer to the problem corresponding to the first example as partition into k anonymous parts, and to the problem corresponding to the second example as partition into k distinguishable parts.

k Anonymous Parts: The problem of partitioning a set of projects into k anonymous parts is formally equivalent to the we mainly study in this paper, with the only difference that we restrict the input partitions, as well as the output partition, to consist of at most k parts. Due to NP-hardness of Mirkin Distance Minimization given by Chen et al. [START_REF] Chen | A note on clustering aggregation[END_REF], Total PA is NP-hard even for k = 2.

An interesting approach to the problem of aggregating partitions into k anonymous parts is via clustering: For example, embed the set of projects into a metric space where each project pi is an element and the distance between a pair of projects pi and pj equals the number of voters placing pi and pj in different parts. Then, one can use, e.g., k-means algorithm to find k projects acting as centers, and, viewing each center as a representative of a part, assign to each center all projects that are the closest to this center among all k centers. Other option would be to define those k centers as the set of k projects that, if chosen as centers, would minimize the maximum distance between any pair of projects assigned to the same cluster; we mention that this aggregation method does not seem to be definable via voter-utilities of the sort we consider in this paper. Studying such clustering algorithm is left for future work.

k Distinguishable Parts: This problem variant is significantly different from the problem we mainly study in this paper, as we are not interested in standard partitions, but in partitions into distinguishable parts. In fact, we can view the input votes, as well as the aggregated output as strings: Each vote is a string of length m (recall that m is the number of projects) and each character i in such a string is a number between 1 to k, representing the type of the project pi. Thus, we have in fact that, for this variant, Egal-PA is equivalent to the NP-hard problem Closest String.

Aggregating Signed Partitions

Recall that the main motivation for our study of partition aggregation methods is of deciding on a substitution structure for participatory budgeting instances. A related task would be to decide upon a complementarities structure, in which projects inside a complementarity part in the output partition would enjoy supermodular relations (in contrast to projects inside a substitution structure, which should suffer from submodular relations). Indeed one can use our partition aggregation methods for deciding upon a complementarities structure as well as for deciding upon a substitution structure.

A more involved task would be to simultaneously aggregate substitution structures and complementarity structures: That is, given a set of projects, we would like to partition them into parts, and decide, for each part, whether it is a substitution part or a complementarity part. Modeling this task would be natural via studying signed-partitions aggregation methods: Each voter provides a signedpartition, which is a partition of the set of projects such that each partition is labeled with, say, either + (for complementarity part) or -(for substitution part); the task of a signed-partitions aggregation method would be to output a signed-partition over the same set of projects.

The problem of aggregating signed-partitions is fundamentally different than the problem we mainly study here (i.e., aggregation non-signed partitions), and we leave it as a natural future research direction.

Table 2 .

 2 = {{p 1 , p 2 , p 3 , p 4 , p 5 }} 10 4 S = {{p 1 , p 2 , p 3 , p 4 }, {p 5 }} 6 4 S = {{p 1 , p 2 , p 3 }, {p 4 }, {p 5 }} 3 5 S = {{p 1 , p 2 , p 3 }, {p 4 , p 5 }} 4 6 S = {{p 1 , p 2 }, {p 3 }, {p 4 , p 5 }} 2 7 S = {{p 1 , p 2 }, {p 3 }, {p 4 }, {p 5 }} 1 7 S = {{p 1 , p 2 }, {p 3 , p 4 , p 5 }} 4 10 S = {{p 1 , p 3 , p 4 , p 5 }, {p 2 }} 6 6 Example for non-unanimity of Egalitarian PA (Lemma 4)

	Aggregated Partition	PA utility 1st voter 2nd voter
	S

LIGM, CNRS, Univ Gustave Eiffel, Marne-la-Vallée, France , email: laurent.bulteau@upem.fr

[START_REF] Aziz | Proportionally representative participatory budgeting: Axioms and algorithms[END_REF] Ben-Gurion University of the Negev, Beer-Sheva, Israel, email: pallavi@post.bgu.ac.

il[START_REF] Benade | Preference elicitation for participatory budgeting[END_REF] Ben-Gurion University of the Negev, Beer-Sheva, Israel, email: talmonn@bgu.ac.il

No No Total-PAM NP-h even for ≤ 2 (


Gilles H Roche

Gudrun Bruckner

Dan G Dumitrescu

Joël J E Moreau

Arie Van Der Lee

Guillaume Wantz

Olivier J Dautel

Icgm

Structural Odd-Even Effect Impacting the Dimensionality of Transport in BTBT-CnOH Organic Field Effect Transistors

Keywords: organic semiconductor, OFET, odd-even effect

We report the synthesis and characterization of a series of [1]benzothieno [3,2b]benzothiophene (BTBT) molecules disubstituted by hydroxy aliphatic chains in positions 2 and 7 (BTBT-CnOH) where the intralayer molecular stacking alternates between a classical and an inverted herringbone mode as a function of whether the alkyl sides chains have an even or an odd number of carbon atoms. This odd-even effect does not only affect the interlayer distance of the lamellar structures and the melting points, but also the electronic properties. The BTBT-CnOH odd series develops a classical herringbone pattern with edgeto-edge S⋯S interaction chains linked together by face-to-edge S⋯S interaction chains with two-dimensional mobility. However, the even series has only edge-to-edge interactions in an inverted herringbone organization and thus only a one-dimensional conducting character.

These two types of herringbone patterns have different Field Effect Transistor characteristics and mobilities, those of the odd members being systematically higher than their even neighbors. This is the first example of an odd-even effect impacting the electronic properties of an organic semiconductor.

Introduction

The odd-even effect in organic chemistry is a widely occurring phenomenon which can be defined as the dependency of structural, chemical and/or physical properties on the odd or even number of structural units in a molecule. Alternating solid-state packings as a function of whether the alkyl side chains have an even or odd number of carbon atoms and their influence on notably the melting point have indeed been observed in n-alkane and end-substituted nalkanes. [1,2] This odd-even effect has been in particular studied in organic n-alkane selfassembled monolayers [3,4] and has been observed for electronic [5] , frictional [6] and electrochemical properties. [7] Although crystal packing alternations for odd and even members in a particular series have been shown to be present for a wide range of organic materials, little attention has been paid to the odd-even effect in organic semiconductors. The devices of organic electronics are based on -conjugated molecules capable of selfassembling in 1D, 2D or even 3D and controlling their organization allows to fine-tune their electronic properties and thus to optimize the resulting devices. [8] With this objective, conjugated chromophores have been functionalized by alkyl chains and steric bulky moieties not only to improve their solubility [9] but also to regulate their supramolecular organization and progress towards the control of performances of the resulting devices. [10,11] In most cases the aliphatic parts are simple alkyl chains or aromatic groups introducing weak van der Waals, -stacking or sulfur-sulfur interactions. These alkyl chains regulate many aspects of the solid-state packing and are, in turn, indirectly responsible for the electronic and optical properties of the resulting organic semiconductor materials. So far, how these moieties govern such characteristics is not fully understood. In order to optimize the performances of the devices the length of their solubilizing aliphatic substituents is varied until an optimum is found. [12] Until now, no rules could be established to predict the optimum of the number of CH 2 units.

In a couple of studies odd-and even-length side chain materials with π-bonded units were synthesized but the possibility of an optoelectronic property alternation was overlooked or not reported. For example, recently, Burnett et al. reported an odd-even effect [13] on the properties of a number of physicochemical properties in a series of (2,5-bis(3-alkylthiophen-2-yl) thieno [3,2-b]thiophenes; BTTT) monomers with odd and even numbered alkyl side chains. In this case, the melting point was found to depend on the odd or even number of CH 2 groups in the alkyl side chains, which could be correlated to different packing modes for BTTT with odd or even-numbered side chains. Another widely studied system is based on π-extended [1]benzothieno [3,2-b][1]benzothiophene (BTBT) containing aromatic compounds, which are known for their high charge carriers mobilities and perform as such among the best organic semiconductors for the field effect transistor application. [9,11,14] Ebata et al. [9] reported the synthesis, the characterization and the fabrication of field effect transistors (OFET) of a series of dialkyl [1]benzothieno [3,2-b] [1]benzothiophenes (BTBT-Cn, Scheme 1) with n = 5-14 (where n is the number of methylene units in the alkyl side chains) without studying the oddeven effect. They observed that the characteristic interlayer distance (the "d-spacing") depends on the length of the alkyl chains with larger d-spacings for longer alkyl chains. They concluded that all the derivatives have similar molecular packings, but only the crystal structure of the BTBT-C12 was solved and erroneously attributed to all the other molecules.

However, using their provided structural information, Burnett et al. [13] demonstrated that the out-of-plane d-spacing of the thin BTBT-Cn films was following an odd-even effect as shown in Fig. S45 suggesting that the molecular packing was after all not similar for all members of the BTBT-Cn series without providing a detailed structural evidence. Scheme 1. Chemical schemes of BTBT-Cn and BTBT-CnOH.

Here we report a complementary study of the BTBT-Cn series, focusing mainly on the correlation between the molecular packing and the device characteristics as a function of the number of CH 2 groups. We carried out single-crystal X-ray structure analyses for the not yet reported members of the BTBT-Cn series, i.e. for n=6, 7, and 9. However, since we did not find a real evidence of an impact of an odd-even effect of the structural organization on the optoelectronic properties of this family, we turned our attention to the BTBT-CnOH series of which we already reported the structures of the n=4 [15] and n=6 [16,17] members and the charge transport properties of the n=6 member. [16] The C n OH chains are as in BTBT-Cn attached to the 2 and 7 positions of the BTBT core (Scheme 1). In this study we report and compare the single-crystal structures of all n=5-10 members of the BTBT-CnOH series and we show the existence of a remarkable odd-even effect related to the orientation of the BTBT cores. We also report the optical properties and the FET mobilities of the devices of the complete series and correlate the structural features to these characteristics.

Results and discussion

The BTBT-Cn series

As already mentioned, all members of the BTBT-Cn series self-organize in a lamellar structure and by analogy with the X-ray structure of the BTBT-C12, the organization of their BTBT cores in a lamella was considered to be a herringbone arrangement [7,14]. [9,18] This was confirmed by Izawa et al. [10] who described and compared three crystal structures of the series (BTBT-C8, BTBT-C10 and BTBT-C12). Other BTBT-Cn structures, including odd members, have been studied recently [19] and we complete the series in this study. The crystal structure of the n=11 member could not be obtained. Table 1 gives an overview of the cell parameters and space group symmetries of all members. The herringbone layers themselves are packed along the crystallographic c-axis, but not in the same way for the odd and even members. The unit cell parameters for all compounds n=6-12 follow the same trend, i.e. an a-parameter around 5.8-5.9 Å, a b-parameter around 7.6-7.9 Å, a c-parameter which depends clearly on the length of the alkyl chain and a -angle close to 90°. All structures, except BTBT-C6, crystallize in space group n° 14, which in its standard setting is P2 1 /c [START_REF]International Tables for Crystallography[END_REF] , but are reported in the three different settings P2 1 /c, P2 1 /a, and P2 1 /n. This means that the structureswithout considering the different lengths of the alkyl chains are not isostructural, but do display different packings, except those reported in the same setting, i.e. the even members n=8, 10, 12, which are indeed isostructural and which include the n=6 member that is a slightly triclinically distorted variant of the structures of the other even members. Figure 1 shows the herringbone packed structures of all compounds with n >=6 projected along the a and c-axes. The projection along the a-axis shows clearly the different packing of the layers for odd and even members: whereas for all even numbers the two sulfur atoms of the BTBT core in different layers are arranged in a parallel fashion with respect to each other, they are anti-parallel for the odd members. In addition, the end-methyl groups that are opposite to each other adopt a staggered conformation which is much more pronounced for the odd members than for the even members. In the projection along the a-axis this shows up as a larger lateral shift in the b-direction for the odd members than for the even members.

Table 1. Cell parameters a, b, c, , , , and cell volume V of all BTBT-Cn compounds for which a structure determination from singe crystal X-ray data was reported. The different stacking of alkyl containing compounds with odd and even numbers of methylene groups is a known phenomenon and related to the lower possibility of alkyl chains with an odd number of methylene units to pack in a compact way in the zones where the methyl groups are opposite to each other than alkyl chains with an even number of methylene units. [2] It is possible to quantify the compactness of the packing of adjacent molecular BTBT-Cn layers by calculating the fraction of the 'free' or 'occupiable' volume relative to the unit cell volume by using a virtual spherical probe. [START_REF] Helmholdt | [END_REF] This computational procedure is usually employed for the calculation of porosity or solvent-accessible volumes, where probe radii between 1.2 and 1.6 Å are commonly employed. [22] In this case there is not any solvent accessible volume, since all BTBT-Cn compounds are strictly dense, but it appears that with a lower probe radiushere 0.95 Å -than the radius used for common intruding speciesuseful information can be obtained about the compactness of the packing of adjacent molecular BTBT-Cn layers and thus indirectly the Van der Waals interaction between the methyl contact planes. The virtual spherical probe method has the advantage that the subatomic-sized free volumes can be located within space, which is not the case for other methods that calculate the compactness of a crystal structure, such as the Kitajgorodskii packing index method. [START_REF] Kitajgorodskii | Molecular Crystals and Molecules[END_REF] Here MERCURY [START_REF] Macrae | [END_REF] was used for the calculations using a grid of 0.1 Å: all subatomic free volumes are indeed found in the methyl contact layer between opposite alkyl chains (Fig. S48-S53). Interestingly, for the structures n=2,3,4,5 which also pack layered-wise, but with a different arrangement of opposite alkyl chains, the subatomicsized free volumes are not found in the zones between the terminal methyl groups, but in between the alkyl chains within the layers. and confirming Boese's hypothesis [2] related to the lower compactness of the packing of adjacent molecular layers for odd-membered n-alkanes compared to even-membered nalkanes.

BTBT-Cn Cell parameters

 (gcm - 3 ) space group symmetry T (K) Reference/CSD refcode a b c    V  BTBT-C2
Figure 2 (a) % free volume per unit-cell volume versus number of methylene groups in BTBT-Cn for a probe radius of 0.95 Å and a grid-spacing of 0.1 Å. The blue markers are for the structures that stack according to the herringbone mode, whereas the red markers are for structures with other stackings. It is noted that the crystal structure of the n=11 member could not be obtained. A larger % free volume value means a less compact inter-layer space. (b) Mobilities of OFET BTBT-Cn devices evaluated under ambient conditions without any precautions to eliminate air and moisture produced from Table S1 and ref [9] . Experimental values from 10 different devices are found within the error bars. The projection along the c-axis in Figure 3 shows that all BTBT-Cn structures have the same type of BTBT core layer with the same orientation of the BTBT cores within herringbonemode packing but without any odd-even effect. This stacking will be denoted as the classical herringbone orientation in the following. [18,25] There exist two different intermolecular S⋯S contacts shorter than the Van der Waals diameter of sulfur atoms (3.70 Å) which connect the BTBT cores in an edge-to-edge manner or in a face-to-edge manner. The edge-to-edge S⋯S interaction chains have a short S⋯S distance of the order of 3.55 Å whereas the face-to-edge interaction have longer S⋯S distances of the order of 3.65 Å, both interactions conferring a two-dimensional character to the crystalline organization and a hence a 2D mobility.

Figure 2b

displays reported BTBT-Cn mobilities, μ OFET , according to the data available in the literature (Table S1). Although no pronounced dependence of μ OFET on alkyl group length was observed, BTBT-Cns with longer alkyl group tend to exhibit higher mobility values than the derivatives with shorter alkyl groups. For example, μ OFET for the well-known BTBT-C8 is higher by approximately on order of magnitude than that for BTBT-C5 but no odd-even discrimination can be observed, which is not surprising since the orientation of the BTBT cores remains identical throughout the series. The best mobilities among BTBT-Cn derivatives are for BTBT-C13 around 2.0 cm 2 V -1 s -1 [9] but recently devices with record-high mobilities at 17.2 cm 2 V -1 s -1 were reported, [26] close to the golden standard value of single crystal rubrene-based devices. The atomic structure of BTBT-C13 has not, however, yet been reported.

The BTBT-CnOH series

Despite the fact that an odd-even effect is obviously present in the d-spacings of the lamellar BTBT-Cn phases, no effect on the opto-electronic properties of the resulting devices can be identified because of the identical intra-layer structures. The supramolecular reason behind this behavior can most probably be found by considering the strength of the different interactions involved in the self-assembly of the supramolecular material. We can reasonably propose that the interlayer herringbone pattern is firstly formed involving - stacking and the S⋯S interactions and that the resulting semiconducting layers then self-assemble into a lamellar phase through van der Waals interactions between opposite alkyl chains, since the former interactions are stronger than the latter. Therefore, the organization of the conjugated cores is not controlled by the odd-even effect originating from the aliphatic insulating part.

A literature survey concerning compounds undergoing an odd-even effect influencing their physicochemical and electronic properties, [3] reveals the requirement for the effect to be present to have a strong interaction at the end of aliphatic chains, either by a covalent bond in the case of monolayers (Ag -CH 3 (CH 2 ) n SH , [27] Au -CH 3 (CH 2 ) n SH [28] ) or by a hydrogen bond interaction in the case of lamellar compounds such as CH 3 (CH 2 ) n-2 COOH, [29] HO(CH 2 ) n-1 CH 3 , or HO(CH 2 ) n-1 COOH. [30] In this case, the odd-even modification of the orientation of the end group is directed by the covalent or non-covalent bonds at the end of the alkyl chain and could also influence the supramolecular assembly as a function of the odd or even number of alkyl spacers. [31] In this context we decided to add a structure directing agent at both ends of the alkyl chains of The single-crystal structure of BTBT-C6OH was already reported before by us [16,17] and by comparison with the structure of BTBT-C8 it could be inferred that in BTBT-C6OH, BTBT half of the cores are rotated by 180° around their long axis in an inverted herringbone organization with only one type of S⋯S contact, viz. edge-to-edge S⋯S contacts with S⋯S distance of 3.545 Å, whereas face-to-edge S⋯S contacts are absent in this case. As a result, the structure of BTBT-C6OH has a more one-dimensional character than that of BTBT-C8.

BTBT

This was confirmed by the calculation of transfer integrals yielding strong interactions (65 meV) between BTBT cores in one direction of the herringbone layer and very low interactions in the other direction, [16] in contrast with BTBT-C8 which has a more homogeneous distribution of the transfer integrals in the layer.

We succeeded in growing single crystals for the n=4,5,7,8,9, and 10 members of the BTBT-CnOH series. The n=4 [15] member appeared to have an alternative stacking mode with a considerably denser structure, as have the low n-members of the BTBT-Cn series. The n=5 member crystallized in two polymorphic forms, of which one possesses the classical herringbone pattern. The n=5,6,7,8,9,10 members showed a remarkable odd-even effect in terms of diffraction quality, the even members displaying excellent diffracting efficiency, whereas the odd members had poor diffracting power, making the use of synchrotron radiation indispensable for the resolution of their atomic structures. All compounds crystallized as platelets, but the odd n=5, 7, 9 members were much thinner than the n=6, 8, 10 members. The lower probability to obtain crystals for organic compounds suitable to be analyzed by X-ray diffraction with an odd number of methylene spacers was noticed in several studies. [32] We have tried to obtain X-ray data for all compounds at ambient conditions, since these are the usual conditions for the functional devices made from these compounds. For some of the structures the data collected at room temperature did not result, however, in acceptable chemical structures and therefore data were collected at lower temperatures.

Table 2 gathers the cell parameters and the space group symmetries of all members. The n=6,8,10 members crystallize in the same monoclinic space group C2/c and are isostructural apart from the different alkyl chain lengths. The same holds for the n=7 and 9 members in the triclinic space group P-1, but the n=5 member has space group P2 1 /c with nevertheless the same packing mode as the two odd triclinic members. The structure of the n=5 member was also measured at low temperatures to ascertain that no phase transition takes place; it was indeed found that the space group at 100 K is also P2 1 /c [33] and its atomic arrangement isostructural with the room temperature structure. Whereas this study focusses on the inter and intramolecular packing mode which is mostly independent of temperature when there are no phase transitions, intermolecular interactions may be more or less dependent on temperature. This has been previously demonstrated by us for n=4,5,6 [15,17,33] and will be the topic of a forthcoming study. Notes: Cell lengths in Å; cell angles in °, cell volume in Å 3 . The CSD refcode refers to the identifier in the Cambridge Structural Database. The cell parameters of BTBT-C6OH have been reported elsewhere [17] in the equivalent setting I2/a of space group C2/c. BTBT-C5OH has a polymorph whose structure is reported elsewhere. [33] As already deduced from the out-of-plane XRD measured on evaporated thin films of BTBT-CnOH, all single crystal structures show a lamellar organization with an interlayer distance increasing with the number of methylene groups. (Figure 5). The 180° rotation of one half of the BTBT cores is present for all even members within the BTBT-CnOH series, whereas the odd members have all the same relative BTBT orientations as the members in the BTBT-Cn series. As in the structures of BTBT-Cn, an odd-even alternation for the BTBT core stacking between adjacent molecular layers is found for BTBT-CnOH (Figure 5; stacking schemes on the right, cf stacking schemes of BTBT-Cn in Figure 1), but not in the same way.

The BTBT cores of the odd members of BTBT-CnOH stack in the same way as those of the even members of BTBT-Cn, i.e. an in phase positioning of the sulphur 'dimers' between the top (t) layer and the bottom (b) layer, but an out of phase orientation within the layer. In the structure of the even members of BTBT-CnOH the S-S dimer orientation is in phase both within the layers and between the layers, whereas the odd members of BTBT-Cn have an out of phase orientation both within the layers and without the layers. These odd-even interlayer packing alternations for both the BTBT-Cn series and the BTBT-CnOH series have, however, no impact on the transport properties of these compounds, since they do not concern a structural alternation within the molecular layers where the transport takes place. The subatomic free volume between two adjacent molecular layers was calculated in the same way as for BTBT-Cn, where each layer in this case is bordered by hydroxyl moieties rather than methyl moieties as in the case of BTBT-Cn. The analysis for BTBT-CnOH, however, is more delicate, since the hydroxyl moieties are partially disordered over different positions, except in the case of BTBT-C5OH.

The hydrogen atoms of the terminate hydroxyl groups of the even members are disordered over two different positions, whereas the disorder for the odd members n=7, 9 is more complicated, involving the complete terminate alcohol groups. In order to do the free-volume distance in the order of 3.55 Å). This has already been discussed for the structure of BTBT-C6OH, [16] but can now be generalized as an odd-even effect. Figure 6 shows the herringbone patterns of all BTBT-CnOH members where the sulfur atoms which are in the background are orange colored and those in the foreground yellow.

Edge-to-edge S⋯S contacts are present in the structures of both the odd and the even members with distances in the 3.46-3.62 Å range, but the face-to-edge S⋯S contacts are absent for the even members. This visual observation can be quantified by calculating the torsion angles Cg1⋯S1⋯Cg2⋯S2 where Cgn refers to the center of gravity of the two carbon atoms opposite to the sulfur atom in a thiophene unit and the numbers n designate two different thiophene units stacked in herringbone mode. This is shown in Figure 7b where a very clear alternation is seen between odd and even members of the BTBT-CnOH series. The absence of the face-to-edge S⋯S contacts in the structures of the even BTBT-CnOH suggests that the mobility in these structures has a one-dimensional rather than a two-dimensional character as for the odd members and all members of the BTBT-Cn series.

The 180° rotation of one half of the BTBT cores for the even members of BTBT-CnOH can be related to different hydrogen-bond networks for the odd and even members which in turn could be the result of the less compact space between adjacent molecular layers for the odd members compared to that of the even members. The analysis of the hydrogen-bond networks is a bit delicate, since the hydrogen bond networks are for all members, except for n=5, disordered. The driving force for the supramolecular assembly is the set-up of the hydrogen-bonded network between the terminal hydroxyl groups, either between molecules within a layer or between layers, or both. The energetic 'choice' made by the even members is to maximize the interlayer interactions by rotating one out of two BTBT cores so that two pairs of hydroxyl groups come in a favorable position for a hydrogen-bond interaction crossing the interlayer gap. The odd members rotate one out of two terminal OH groups in order to establish an intralayer hydrogen-bond interaction, leaving one possibility for an interlayer interaction. The energetic difference between the two possibilities is small (0.6 eV for 200 atoms) as was found from periodic DFT calculation by flipping one BTBT core from a classical to an inverted herringbone structure. [33] Having established the presence of a remarkable odd-even effect in the relative orientation of the BTBT cores, we turned our attention to the optoelectronic properties of BTBT-CnOH.

Figure 9a gives the normalized UV-vis absorbance spectra of the n=5-10 members, determined on thin films evaporated on glass substrates and the position of the absorbance maximum as a function of the number of methylene units n. All maxima are red-shifted with the increase of the alkyl chain length (Figure 9b). The positions of the absorbance maxima of the even members appear to modulate on those of the odd members which display a linear behavior. Two different structural effects are in fact superimposed, since the increasing length of the alkyl chains alone often results in a continuous red-shift of the maxima (although this is not always the case, e.g. for BTTT [13] ), whereas the 180° rotation of the BTBT cores between odd and even members alone should result in an alternating red-blue shift of the maxima. as the output curves for the BTBT-CnOH FET-devices. Figure 10 shows that the mobility sharply increases with the length of the alkyl chains, in contrast with the mobilities of BTBT-Cn where the average increase is more moderate or nearly absent (Figure 2b). The two different superimposed structural effects (chains length and 180° rotation) evidenced on the UV-vis absorbance spectra (Figure 9) also control the mobilities of BTBT-CnOH.

According to the "Fastener Molecular" effect [34] , (i.e. an increase of the transfer integrals between the π-conjugated cores as the length of the alkyl chains increases), mobilities of both series (odd and even) should increase. [19] However, mobilities of the complete BTBT-CnOH series do not increase linearly with the chain length, but show instead a clear odd-even effect, the mobilities of the odd members being in all cases higher than their even neighbors. The most striking difference is observed between the average mobility of BTBT-C8OH being at 0.12 cm 2 V -1 s -1 whereas the mobility of BTBT-C9OH is nearly one order of magnitude higher at 1.04 cm 2 V -1 s -1 . This odd-even effect is certainly the result of the two types of herringbones (classical and inverted) found in the two different series (Fig. 6). While the classical herringbone exhibited by the odd series results in a two-dimensional S⋯S interaction network and as a consequence higher mobilities, the inverted herringbone found in the even series results in mono-dimensional network and consequently lower mobilities.

It is important to note that the devices based on BTBT-CnOH were highly reliable and reproducible even if the molecules were directly evaporated on the UVO-treated SiO 2 dielectric substrate without the use of any passivation layer. Hydroxy -SiO2 interactions might direct and stabilize the BTBT-CnOH layers on the substrate. BTBT-C10OH 0.32(4) 10 8 -5

Notes: Standard deviations estimated from measurements on different devices are given in parentheses on the scale of the least significant digits of the numerical value.

Conclusions

We have designed a new family of compounds consisting of BTBT cores appended with variable-length alkyl chains and terminated by a structure directing hydroxyl group. The oddeven structural effect which is inherently present in layered alkyl chain containing compounds is dramatically amplified through the use of a structure-directing terminal hydroxyl group which causes the BTBT-cores to have alternating relative orientations depending on whether n is odd or even. An unprecedented directed 180° rotation of the optoelectronically active moiety as a function of the odd or even number of methylene spacers results in a pronounced odd-even effect on the semiconducting properties of the BTBT-CnOH family of compounds.

For the first time, the odd-even effect controls the performances of devices. The alternating odd-even intra-layer assembly directly affects the transport properties in Organic Field Effect

Transistors. The odd series shows significantly higher mobilities than the even series, because the conduction in the former series is two-dimensional rather than one-dimensional as for the even members. The use of structure directing terminal groups as an odd-even tool could be useful for other organic semiconductors to turn one-dimensional transport into twodimensional transport.

More insight in how the packing influences the mobilities can be obtained from calculations of intermolecular interaction energies and transfer integrals; this will be the topic of a forthcoming study.

Experimental section 4.1 Synthesis and NMR characterization

All chemicals and solvents were of reagent grade unless otherwise indicated.

Dichloromethane (DCM) and N,N-dimethylformamide (DMF) were dried over 4 Å molecular sieves and acetic acid over 3 Å molecular sieves. Tetrahydrofuran (THF) was distilled under nitrogen over sodium benzophenone ketyl. BTBT and BTBT-C6OH were synthesized as described in our previous work [16] . All reactions were performed under nitrogen. Detailed descriptions of the syntheses can be found in the Supplementary Material, Section I.

Figure 1 .

 1 Figure 1. Projections of the structures of BTBT-Cn for n=6,7,8,9,10, 12 along the a-axis. The crystal structure of the n=11 member could not be obtained. The b-axis points in all cases to the right and the c-axis downwards. Hydrogen atoms are omitted in all figures for clarity. The schemes at the right represent the vertical stacking modes of S-S pairs between the top (t) and bottom (b) molecular layers for the even and the odd members, respectively.

Figure 2Erreur !

 2Erreur Source du renvoi introuvable.a gives the results of the calculations for n=6-12 showing a clear odd-even effect,

Figure 3 .

 3 Figure 3. Projections of the BTBT-Cn structures for n=6,7,8,9,10, 12 along the c-axis. It is noted that the crystal structure of the n=11 member could not be obtained. For clarity, hydrogen atoms and alkyl chains are omitted in all sub-figures. The yellow sulfur atoms are in the foreground, whereas the orange sulfur atoms are in the background. They all present the classical herringbone pattern.

-

  Cn and for that purpose the OH function was selected, because the resulting hydrogen bond should be strong enough to promote the formation of a hydrogen bond network and weak enough to preserve the solubility of this BTBT-CnOH series (Scheme 1). Their synthesis involves a Friedel and Kraft addition of two Br(CH 2 ) n COCl on position 2 and 7 of the BTBT core (see supporting information), followed by the conversion of the bromines into acetates. Finally, the use of hydrazine hydrate can conjointly reduce the carbonyl functions located in position 2 and 7 and realize the hydrolysis of the acetate to generate the hydroxy function.Out-of-plane X-ray diffraction realized in Bragg-Brentano configuration on thin BTBT-CnOH films vacuum evaporated on silicon wafers reveal that all members are self-organized according to a lamellar structure developing perpendicular to the substrate with characteristic d-spacings connected to the interlayer spacing that increase with the length of the alkyl chains (Figure4a). As in the case of the BTBT-Cn compounds, a slight crystal-packing odd-even alternation is observed (Figure4). The much more effective cohesion between the layers in BTBT-CnOH is demonstrated by their much smaller interlayer-spacing compared to the BTBT-Cn compound with the same number of spacers, i.e. BTBT-C(n+1). This difference increases steadily from 1.4 Å for the pair BTBT-C5OH/BTBT-C6 (23.1/24.5 Å) to 2.6 Å for the pair BTBT-C10OH/BTBT-C11(33.3/35.9 Å). A small fraction of these differences is caused by the shorter C-O distance (1.4 Å) compared to the C-C distance (1.5 Å), but the main contribution comes from the efficient OH⋯O bonding network between adjacent molecular BTBT-CnOH layers. The much reported melting point alternation for compounds containing long alkyl chains is equally well confirmed for the BTBT-CnOH series (Fig.S44).

Figure 4

 4 Figure 4 (a) Out-of-plane XRD realized at ambient conditions on thin films of the BTBT-CnOH series with systematically varied side-chain length evaporated on silicon wafers (this work). The first group of peaks corresponds to the first reflection harmonic related to the characteristic interlayer distance (the "d-spacing"), whereas the second group corresponds to the second harmonic of the same reflection peak. The vertical scale is a square-root scale. (b) Out-of-plane d-spacings of the BTBT-CnOH obtained from the out-of-plane XRD. For comparison the d-spacings reported for BTBT-Cn (reproduced with permission from Chem. Mater. 2019, 31, 6900-6907 Copyright (2019) American Chemical Society) are given here as

Figure 5 . 1 ,

 51 Figure 5. Projections of the BTBT-CnOH structures for n=5,6,7,8, 9, 10. Hydrogen atoms were omitted in all structures for clarity. The projections are in the same direction as in Figure1, but because of the different space groups this is not always along the same crystallographic axis. The schemes at the right represent the vertical stacking modes of S-S pairs between the top (t) and bottom (b) molecular layers for the even and the odd members, respectively.

Figure 6 .

 6 Figure 6. Classical (odd members) and inverted (even members) herringbone patterns in the structures of BTBT-CnOH. The yellow sulfur atoms are in the foreground, whereas the orange sulfur atoms are in the background. The BTBT moieties of the even members are rotated by 180° with respect to those of the odd members.

Figure 8

 8 compares the hydrogen-bond networks of BTBT-C5OH and BTBT-C6OH, where in the latter case one of the two possible networks have been chosen. In both cases the hydrogen bond network consists of infinite parallel C 2 2 (4) chains. An important difference is that in the case of BTBT-C5OH the chains are composed of pairs of hydrogen bonded OH groups in the top layer (t) connected to pairs in the bottom layer (b), whereas in BTBT-C6OH the hydrogen-bonded chain crosses the gap at each individual OH group. In other words, the chain in BTBT-C5OH can be designated as ⋯OH(t)⋯OH(t)⋯OH(b)⋯OH(b)⋯, whereas the BTBT-C6OH chain is ⋯OH(t)⋯OH(b)⋯OH(t)⋯OH(b)⋯.

Figure 8 .

 8 Figure 8. Hydrogen-bond networks in the structures of BTBT-C5OH and BTBT-C6OH. The projection is in both cases parallel to the stacking direction of the molecular layers. For clarity only the terminal CH2-OH groups of adjacent molecular layers are shown. Depth cueing was used to fade away the CH2-OH groups in the bottom layer (b) in the background from those in the top layer (t) in the foreground. Two examples of OH groups in the top and bottom layer, respectively, have been indicated by small rectangles. ⋯OH(t)⋯OH(t)⋯OH(b)⋯OH(b)⋯ chains are visible in BTBT-C5OH and ⋯OH(t)⋯OH(b)⋯OH(t)⋯OH(b)⋯ chains in BTBT-C6OH.

Figure 9 .

 9 Figure 9. (a) UV-vis absorbance spectra realized on thin films of BTBT-CnOH evaporated on glass substrates. b) evolution of the absorbance maxima as function of the number of CH 2 groups in BTBT-CnOH.

Figure 10 .

 10 Figure 10. OFET mobilities obtained for the BTBT-CnOH series. The height of the boxes extends from the lower to the upper quartile values of the measured values for each n. The orange horizontal lines in the middle of each box give the median values for each n. The whiskers give the minimum and maximum values in each series of measurements, whereas the points outside the whiskers are fliers. Some horizontal jitter has been added to the data points for each n in order to separate them.

1 H and 13 C

 113 Nuclear Magnetic Resonance (NMR) spectra were recorded on a Bruker AC 400 MHz spectrometer (Figs S1-S41).

4. 2 X

 2 -ray data collection, structure solution and refinement.Single-crystal X-ray diffraction data for BTBT-C5OH were collected at the European Synchrotron Radiation Facility ID29 beamline (=0.7290 Å) in Grenoble, France; for BTBT-C6OH and BTBT-C10OH on a Rigaku-Oxford Diffraction Gemini-S diffractometer ( =0.7107 Å); for BTBT-C7OH on a Bruker Venture diffractometer ( =1.5418 Å), for BTBT-C6, BTBT-C7, BTBT-C9, BTBT-C8OH, and BTBT-C9OH at the Elettra synchrotron XRD1 and XRD2 beamlines ( =0.70000 Å), Trieste, Italy. Since the functional devices operate at room temperature, we collected most of the data at that temperature. For some of the structures the data collected at room temperature did not result in acceptable chemical structures and therefore data were collected at lower temperatures. For example, the structure of BTBT-C7OH was refined at room temperature to R F (I > 2(I)) = 0.261 whereas at 173 K it converged to R F (I > 2(I)) = 0.088. The general features of the two structures appeared to be very similar. More details about the experimental conditions and the structural refinements can be found in TableS2. CCDC 2059368-2059375 contains the supplementary crystallographic data in cif-format for the new structures reported in this paper. These data  Syntheses of BTBT-Cn  Syntheses of BTBT-CnOH  Thermal gravimetric analyses  Differential scanning calorimetry  X-ray data collection, structure solution and refinement  Procedure for the fabrication of the organic field effect transistors  Characteristics of the organic field effect transistors

Table 2 .

 2 Cell

	BTBT-	Cell parameters
	CnOH

parameters a, b, c, , , , and cell volume V of all BTBT-CnOH compounds for which a structure determination from single crystal X-ray data was reported.

Table 3 .

 3 FET characteristics of BTBT-CnOH devices fabricated on Si/SiO 2

		 OFET		V th
	BTBT-CnOH	(cm 2 V -1 s -1 )	I on /I off	(V)
	BTBT-C5OH	0.16(2)	10 7	+3
	BTBT-C6OH	0.11(1)	10 8	0
	BTBT-C7OH	0.25(5)	10 7	+2
	BTBT-C8OH	0.12(2)	10 8	0

Author(s), and Corresponding Author(s)* ((write out full first and last names))

Acknowledgements

The authors acknowledge the ESRF (European Synchrotron Radiation Facility, Grenoble, France) for the allocation of beam time on ID29 and are grateful to David Flot for collecting synchrotron X-ray data for BTBT-C5OH on this beamline. GHR gratefully acknowledges financial support of ANR grant Helios N° ANR-13-PRGE-0006 of the PROGELEC program.

Received: ((will be filled in by the editorial staff))

Revised: ((will be filled in by the editorial staff)) Published online: ((will be filled in by the editorial staff))

calculation the structures were expanded to the P1 space group and one hydrogen-bonded network was chosen, after which the analysis was carried out with the same parameters as for BTBT-Cn. Figure 7a shows the same tendency as for BTBT-Cn, i.e. a less compact hydroxy plane between adjacent molecular layers for the odd members than for the even members, and no free volume for the members that do not crystallize in a classical herringbone mode. This is rather surprising, since it could be expected that because of the even number of nonhydrogen atoms in the alcohol chain in BTBT-CnOH the odd members would have a denser Van der Waals region. It is probably the smaller volume of the OH group compared to the terminal CH 3 group which makes that it is only the number of methylene groups that matter.

Organic Field Effect Transistors characterization

OFETs were fabricated on Gen.4 chips from Fraunhofer IPMS (Dresden, Germany) with a bottom-gate and bottom-contact structure. The chips consist of a highly conductive n-doped Si wafer with a 230 nm thick thermally grown oxide. SiO 2 exhibits a capacity of 14.63 nF.cm - 2 . On top of the SiO 2 layer, a 10 nm thick ITO layer and a 30 nm thick Au layer were patterned to create source and drain contact electrodes in an interdigitated finger structure.

Transistors have a channel length of 20 m, a channel width of 10 mm and a common gate contact located on the bottom of the chip. Initially, substrates were cleaned in ultrasonic baths of acetone, isopropanol and DI water for 5 minutes each at room temperature and treated with ozone plasma for an additional 15 min and quickly introduced in a glove box. Finally, a 20 nm thick film of BTBT-CnOH was evaporated at 1 Å/min followed by 30 nm at 12 Å/min, affording the operating device. Electrical characterizations of the fabricated OFETs (Fig. S59) were performed using a Keithley 4200 Semiconductor Characterization System in a glove box environment under nitrogen atmosphere. Field effect mobilities µ OFET were estimated from the saturated regime using the method described by Newman et al. [35] Supporting Information Supporting Information is available from the Wiley Online Library or from the author.

An unprecedented odd-even alternation in the relative orientation of -conjugated cores in the structures of organic semiconductors as a function of the number of methylene spacers in the side alkyl chains changes the dimensionality of carrier transport from one-to two-dimensional.

Structural