Return to Question

Some motivation:

A company has a certain number of workers. On each given day from Monday to Friday, a fixed number of people are to work. The company wants to foster teamwork, bonding and camaraderie among its team, so it wants to create a weekly schedule that maximises the number of people that have worked with each other on at least one day. How can this be accomplished?

Formal problem (Graph theoretic version):

For $n > 2$, let $G$ be the edgeless graph on $n$ vertices. Let $k > 1$ be a given fixed positive integer. We are asked to select subsets $A_1, \dots, A_k$ of the vertex set of $G$ of cardinality $m$ each, where $m < n$ and $km > n$.

For each subset $A_i$, we connect all vertices in $A_i$ to each other. To be more precise, we form the graph $G’$ with vertex set that of $G$, and edge set $E(G’) = \{(a, a’) \ | \ a, a’ ∈ A_i \text{ for some }i\}$.

Question (GT): How can we maximise |E(G’)|? What is the maximum cardinality?

There is also a continuum/continuous version of the problem, which may be easier to deal with since it avoids problems with discreteness of individual people.

Formal problem (Measure theoretic version):

Let $X$ be a non atomic measure space of measure $1$. For concreteness, we may take $[0, 1]$ under the Lebesgue measure.

Let $k > 1$ be a given fixed positive integer, and $m$ a real number with $0 < m < 1$ and $km > 1$. We are asked to select $k$ measurable subsets $A_1, \dots , A_k$ of $X$ of measure $m$.

Question (MT): Which choice of subsets maximises the measure of $\cup_{i = 1}^n A_i \times A_i$ in $X \times X$? What is the maximal measure?

Here we equip $X \times X$ with the product measure, and $A_i \times A_i$ denotes the set $\{(a, a’) \ | \ a, a’ ∈ A_i\}$.

Remark: By a compactness argument one can verify that the supremum is indeed achieved, and so we are justified in speaking of the configuration achieving the maximum.

Some motivation:

A company has a certain number of workers. On each given day from Monday to Friday, a fixed number of people are to work. The company wants to foster teamwork, bonding and camaraderie among its team, so it wants to create a weekly schedule that maximises the number of people that have worked with each other on at least one day. How can this be accomplished?

Formal problem (Graph theoretic version):

For $n > 2$, let $G$ be the edgeless graph on $n$ vertices. Let $k > 1$ be a given fixed positive integer. We are asked to select subsets $A_1, \dots, A_k$ of the vertex set of $G$ of cardinality $m$ each, where $m < n$ and $km > n$.

For each subset $A_i$, we connect all vertices in $A_i$ to each other. To be more precise, we form the graph $G’$ with vertex set that of $G$, and edge set $E(G’) = \{(a, a’) \ | \ a, a’ ∈ A_i \text{ for some }i\}$.

Question (GT): How can we maximise |E(G’)|? What is the maximum cardinality?

There is also a continuum/continuous version of the problem, which may be easier to deal with since it avoids problems with indivisibility of individual people.

Formal problem (Measure theoretic version):

Let $X$ be a non atomic measure space of measure $1$. For concreteness, we may take $[0, 1]$ under the Lebesgue measure.

Let $k > 1$ be a given fixed positive integer, and $m$ a real number with $0 < m < 1$ and $km > 1$. We are asked to select $k$ measurable subsets $A_1, \dots , A_k$ of $X$ of measure $m$.

Question (MT): Which choice of subsets maximises the measure of $\cup_{i = 1}^n A_i \times A_i$ in $X \times X$? What is the maximal measure?

Here we equip $X \times X$ with the product measure, and $A_i \times A_i$ denotes the set $\{(a, a’) \ | \ a, a’ ∈ A_i\}$.

Remark: By a compactness argument one can verify that the supremum is indeed achieved, and so we are justified in speaking of the configuration achieving the maximum.

Some motivation:

A company has a certain number of workers. On each given day from Monday to Friday, a fixed number of people are to work. The company wants to foster teamwork, bonding and camaraderie among its team, so it wants to create a weekly schedule that maximises the number of people that have worked with each other on at least one day. How can this be accomplished?

Formal problem (Graph theoretic version):

For $n > 2$, let $G$ be the edgeless graph on $n$ vertices. Let $k > 1$ be a given fixed positive integer. We are asked to select subsets $A_1, \dots, A_k$ of the vertex set of $G$ of cardinality $m$ each, where $m < n$ and $km > n$.

For each subset $A_i$, we connect all vertices in $A_i$ to each other. To be more precise, we form the graph $G’$ with vertex set that of $G$, and edge set $E(G’) = \{(a, a’) \ | \ a, a’ ∈ A_i \text{ for some }i\}$.

Question (GT): How can we maximise |E(G’)|? What is the maximum cardinality?

There is also a continuum/continuous version of the problem, which may be easier to deal with since it avoids problems with discreteness of individual people.

Formal problem (Measure theoretic version):

Let $X$ be a non atomic measure space of measure $1$. For concreteness, we may take $[0, 1]$ under the Lebesgue measure.

Let $k > 1$ be a given fixed positive integer, and $m$ a real number with $0 < m < 1$ and $km > 1$. We are asked to select $k$ measurable subsets $A_1, \dots , A_k$ of $X$ of measure $m$.

Question (MT): Which choice of subsets maximises the measure of $\cup_{i = 1}^n A_i \times A_i$ in $X \times X$ (if the supremum can indeed be achieved)? What is the maximal measure?

Here we equip $X \times X$ with the product measure, and $A_i \times A_i$ denotes the set $\{(a, a’) \ | \ a, a’ ∈ A_i\}$.

Some motivation:

A company has a certain number of workers. On each given day from Monday to Friday, a fixed number of people are to work. The company wants to foster teamwork, bonding and camaraderie among its team, so it wants to create a weekly schedule that maximises the number of people that have worked with each other on at least one day. How can this be accomplished?

Formal problem (Graph theoretic version):

For $n > 2$, let $G$ be the edgeless graph on $n$ vertices. Let $k > 1$ be a given fixed positive integer. We are asked to select subsets $A_1, \dots, A_k$ of the vertex set of $G$ of cardinality $m$ each, where $m < n$ and $km > n$.

For each subset $A_i$, we connect all vertices in $A_i$ to each other. To be more precise, we form the graph $G’$ with vertex set that of $G$, and edge set $E(G’) = \{(a, a’) \ | \ a, a’ ∈ A_i \text{ for some }i\}$.

Question (GT): How can we maximise |E(G’)|? What is the maximum cardinality?

There is also a continuum/continuous version of the problem, which may be easier to deal with since it avoids problems with discreteness of individual people.

Formal problem (Measure theoretic version):

Let $X$ be a non atomic measure space of measure $1$. For concreteness, we may take $[0, 1]$ under the Lebesgue measure.

Let $k > 1$ be a given fixed positive integer, and $m$ a real number with $0 < m < 1$ and $km > 1$. We are asked to select $k$ measurable subsets $A_1, \dots , A_k$ of $X$ of measure $m$.

Question (MT): Which choice of subsets maximises the measure of $\cup_{i = 1}^n A_i \times A_i$ in $X \times X$? What is the maximal measure?

Here we equip $X \times X$ with the product measure, and $A_i \times A_i$ denotes the set $\{(a, a’) \ | \ a, a’ ∈ A_i\}$.

Remark: By a compactness argument one can verify that the supremum is indeed achieved, and so we are justified in speaking of the configuration achieving the maximum.

Some motivation:

A company has a certain number of workers. On each given day from Monday to Friday, a fixed number of people are to work. The company wants to foster teamwork, bonding and camaraderie among its team, so it wants to create a weekly schedule that maximises the number of people that have worked with each other on at least one day. How can this be accomplished?

Formal problem (Graph theoretic version):

For $n > 2$, let $G$ be the edgeless graph on $n$ vertices. Let $k > 1$ be a given fixed positive integer. We are asked to select subsets $A_1, \dots, A_k$ of the vertex set of $G$ of cardinality $m$ each, where $m < n$ and $km > n$.

For each subset $A_i$, we connect all vertices in $A_i$ to each other. To be more precise, we form the graph $G’$ with vertex set that of $G$, and edge set $E(G’) = \{(a, a’) \ | \ a, a’ ∈ A_i \text{ for some }i\}$

Question (GT): How can we maximise |E(G’)|? What is the maximum cardinality?

There is also a continuum/continuous version of the problem, which may be easier to deal with since it avoids problems with discreteness of individual people.

Formal problem (Measure theoretic version):

Let $X$ be a non atomic measure space of measure $1$. For concreteness, we may take $[0, 1]$ under the Lebesgue measure.

Let $k > 1$ be a fixed positive integer, and $m$ a real number with $0 < m < 1$ and $km > 1$. We are asked to select k measurable subsets $A_1, \dots , A_k$ of $X$ of measure $m$.

Question (MT): Which choice of subsets maximises the measure of $\cup_{i = 1}^n A_i \times A_i$ in $X \times X$ (if the supremum can indeed be achieved)? What is the maximal measure?

Here we equip $X \times X$ with the product measure, and $A_i \times A_i$ denotes the set $\{(a, a’) \ | \ a, a’ ∈ A_i\}$.

Some motivation:

A company has a certain number of workers. On each given day from Monday to Friday, a fixed number of people are to work. The company wants to foster teamwork, bonding and camaraderie among its team, so it wants to create a weekly schedule that maximises the number of people that have worked with each other on at least one day. How can this be accomplished?

Formal problem (Graph theoretic version):

For $n > 2$, let $G$ be the edgeless graph on $n$ vertices. Let $k > 1$ be a given fixed positive integer. We are asked to select subsets $A_1, \dots, A_k$ of the vertex set of $G$ of cardinality $m$ each, where $m < n$ and $km > n$.

For each subset $A_i$, we connect all vertices in $A_i$ to each other. To be more precise, we form the graph $G’$ with vertex set that of $G$, and edge set $E(G’) = \{(a, a’) \ | \ a, a’ ∈ A_i \text{ for some }i\}$.

Question (GT): How can we maximise |E(G’)|? What is the maximum cardinality?

There is also a continuum/continuous version of the problem, which may be easier to deal with since it avoids problems with discreteness of individual people.

Formal problem (Measure theoretic version):

Let $X$ be a non atomic measure space of measure $1$. For concreteness, we may take $[0, 1]$ under the Lebesgue measure.

Let $k > 1$ be a given fixed positive integer, and $m$ a real number with $0 < m < 1$ and $km > 1$. We are asked to select $k$ measurable subsets $A_1, \dots , A_k$ of $X$ of measure $m$.

Question (MT): Which choice of subsets maximises the measure of $\cup_{i = 1}^n A_i \times A_i$ in $X \times X$ (if the supremum can indeed be achieved)? What is the maximal measure?

Here we equip $X \times X$ with the product measure, and $A_i \times A_i$ denotes the set $\{(a, a’) \ | \ a, a’ ∈ A_i\}$.