I was doing research in Analysis and it somehow all devolved into some weird type of combinatorics optimization problem. The problem is that I don't know anything about combinatorics. For the progress I've made on the problem it is impossibly frustrating to express these arguments rigorously. I would like to ask people with more experience in combinatorics to provide references to any problems that are similar to the one in question (even if the problems are technically very different but you feel they have the same "style"). If I see what tools/style combinatorics people use to express their arguments I think it will help me with the problem.
Here is the problem in question:
Firstly I have to introduce the concept of the block number.
Given a permutation of $\sigma$ of $\{1,2,...,2k\}$ (i.e $\sigma\in S_{2k}$) we look at the set $\{\sigma(1),\sigma(2),...,\sigma(n)\}$ ($1\leq n\leq 2k$) and express it as a union of integer intervals as follows:
$ \{\sigma(1),\sigma(2),...,\sigma(n)\}=[a_1,c_1]_{\mathbb{Z}}\cup[a_2,c_2]_{\mathbb{Z}}\cup\cdots\cup[a_m,c_m]_{\mathbb{Z}}. $
where $c_i<a_{i+1}$. Then as the set $\{\sigma(1),\sigma(2),...,\sigma(n)\}$ is expressed as a union of $m$ integer intervals we say that the $n$th block number of $\sigma$, $b_n(\sigma)$, is equal to $m$.
For example, if $\{\sigma(1),\sigma(2),...,\sigma(5)\}=\{2,3,10,11,12\}=[2,3]_{\mathbb{Z}}\cup[10,12]_{\mathbb{Z}}$ we then say that $b_5(\sigma)=2$.
Now given a binary string of length $2k$ with an equal amount of zeroes and ones we restrict our attention only to $\sigma$'s with the "alternating property". That is, they permute the string into alternating ones and zeroes starting with 1. So if the string in question is $11110000$ $\sigma$ has the alternating property iff $\sigma(11110000)=10101010$. If $s$ is a binary string let $A(s)$ be the set of all $\sigma$ that have the alternating property with respect to $s$. Then we want to find
$$\inf\{\sup_{1\leq n\leq 2k} b_n(\sigma) : \sigma\in A(s)\}.$$
Admittedly, I don't know much about combinatorics either, but I'll take a stab at solving the problem. It is a bit unclear what a solution to this problem should look like. I'm assuming you are looking for alternate ways to express the desired quantity, which I'm going to refer to as $\alpha(s)$. Perhaps it is also desirable to give an efficient algorithm for determining $\alpha(s)$ from given $s$ as opposed to just iterating over the $(k!)^2$ permutations $\sigma\in A(s)$. I am going to assume singleton intervals $\ [n,n]_{\mathbb{Z}}\ $ are allowed.
$$\alpha(s):=\inf_{\sigma\in A(s)}\ \sup_{1\leq n\leq2k}\ b_n(\sigma)$$
Let $s$ be a binary string of length $2k$ with an equal number of zeroes and ones. For each $n\in\{1\ ,\ \dots\ ,\ 2k\}$, let $s_n$ be the substring which contains the first $n$ characters of $s$. Let $C_0(s_n)$ and $C_1(s_n)$ count the number of $0$'s and $1$'s in $s_n$ respectively. I claim the following:
$$\alpha(s)=\sup_{1\leq n\leq2k}\big|C_0(s_n)-C_1(s_n)\big|\qquad\qquad1\leq\alpha(s)\leq k$$
Example: Suppose $s=1110100010110001$. Then we are taking a supremum over $1,2,3,2,3,2,1,0,1,0,1,2,1,0,1,0$ and the answer is $\alpha(s)=3$.
My arguments are not going to be rigorous in a strictly formal sense. On a philosophical note, I believe there are circumstances where effectively conveying the proof idea is more important than actually being able to write down a fully formal/rigorous proof. I am not claiming that my arguments effectively convey the idea. I'm also struggling to find appropriate ways to communicate the proof. At least, I hope to be able to pass along some of the intuition. I would be happy to see if anyone has a better proof of my assertion.
Before getting to the proof, let us reframe the problem. Consider the following. Suppose we have $\sigma(11110000)=10101010$ for some $\sigma\in S_8$. Let $\sigma(s_n)$ display the image with everything else replaced with underscores. For example, if $\sigma=(1372)(45)(68)$ in cycle notation, we would have:
$$\sigma(1\ \_\ \_\ \_\ \_\ \_\ \_\ \_)=\_\ \_\ 1\ \_\ \_\ \_\ \_\ \_\qquad\qquad b_1(\sigma)=1$$ $$\sigma(1\ 1\ \_\ \_\ \_\ \_\ \_\ \_)=1\ \_\ 1\ \_\ \_\ \_\ \_\ \_\qquad\qquad b_2(\sigma)=2$$ $$\sigma(1\ 1\ 1\ \_\ \_\ \_\ \_\ \_)=1\ \_\ 1\ \_\ \_\ \_\ 1\ \_\qquad\qquad b_3(\sigma)=3$$ $$\sigma(1\ 1\ 1\ 1\ \_\ \_\ \_\ \_)=1\ \_\ 1\ \_\ 1\ \_\ 1\ \_\qquad\qquad b_4(\sigma)=4$$ $$\sigma(1\ 1\ 1\ 1\ 0\ \_\ \_\ \_)=1\ \_\ 1\ 0\ 1\ \_\ 1\ \_\qquad\qquad b_5(\sigma)=3$$ $$\sigma(1\ 1\ 1\ 1\ 0\ 0\ \_\ \_)=1\ \_\ 1\ 0\ 1\ \_\ 1\ 0\qquad\qquad b_6(\sigma)=3$$ $$\sigma(1\ 1\ 1\ 1\ 0\ 0\ 0\ \_)=1\ 0\ 1\ 0\ 1\ \_\ 1\ 0\qquad\qquad b_7(\sigma)=2$$ $$\sigma(1\ 1\ 1\ 1\ 0\ 0\ 0\ 0)=1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\qquad\qquad b_8(\sigma)=1$$
The block number $b_n(\sigma)$ tells us how many groups are formed by the separating underscores. Taking the supremum over the block numbers, we get 4. Consider what happens for any other $\sigma\in A(11110000)$. Regardless, we must always have $b_4(\sigma)=4$ because $\sigma$ must map the first four $1$'s to their respective positions separated by underscores. Furthermore, 4 is the largest number of groups which can be separated by the underscores in a set of 8 elements. Therefore $\alpha(11110000)=4$.
There are two parts to the proof. First, we construct $\sigma\in A(s)$ such that $b_n(\sigma)=\max\Big(1,\ \big|C_0(s_n)-C_1(s_n)\big|\Big)$ for all $n$. Then we prove $b_n(\sigma)\geq\big|C_0(s_n)-C_1(s_n)\big|$ for all $n$ and all $\sigma\in A(s)$. These facts respectively assert the following inequalities (at which point, the claim immediately follows).
$$\alpha(s)\leq\sup_{1\leq n\leq2k}\big|C_0(s_n)-C_1(s_n)\big|\qquad\qquad\alpha(s)\geq\sup_{1\leq n\leq2k}\big|C_0(s_n)-C_1(s_n)\big|$$
(Part 1) We construct $\sigma\in A(s)$ such that $b_n(\sigma)=\max\Big(1,\ \big|C_0(s_n)-C_1(s_n)\big|\Big)$ for all $n$. This construction is best conveyed by example. Suppose $s=01001101$. We use underscores similarly to the $11110000$ example; however, we omit underscores to the left or right of any group. The padding underscores may change at each step, which is why they are omitted.
$$\sigma(0\ \_\ \_\ \_\ \_\ \_\ \_\ \_)=0\ \ \ \ \ \ \ \ \ $$ $$\sigma(0\ 1\ \_\ \_\ \_\ \_\ \_\ \_)=1\ 0\ \ \ \ \ \ \ \ \ \ \ \ $$ $$\sigma(0\ 1\ 0\ \_\ \_\ \_\ \_\ \_)=0\ 1\ 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ $$ $$\sigma(0\ 1\ 0\ 0\ \_\ \_\ \_\ \_)=0\ 1\ 0\ \_\ 0\ \ \ \ \ \ \ \ $$ $$\sigma(0\ 1\ 0\ 0\ 1\ \_\ \_\ \_)=0\ 1\ 0\ 1\ 0\ \ \ \ \ \ \ \ $$ $$\sigma(0\ 1\ 0\ 0\ 1\ 1\ \_\ \_)=0\ 1\ 0\ 1\ 0\ 1\ \ \ \ \ $$ $$\sigma(0\ 1\ 0\ 0\ 1\ 1\ 0\ \_)=0\ 1\ 0\ 1\ 0\ 1\ 0\ \ $$ $$\ \sigma(0\ 1\ 0\ 0\ 1\ 1\ 0\ 1)=0\ 1\ 0\ 1\ 0\ 1\ 0\ 1$$
Note the end result begins with $0$ instead of $1$. In this example, we could simply have chosen to put the $1$ in the front in the last step, but I want to emphasize it is not a problem if the construction starts with $0$. We can always define another permutation $\sigma'(n):=2k+1-\sigma(n)$, which flips the orientation, fixing the problem. To actually determine what $\sigma$ is from the previous steps, we backtrack and fill in underscores.
$$\sigma(0\ 1\ 0\ 0\ 1\ 1\ 0\ \_)=0\ 1\ 0\ 1\ 0\ 1\ 0\ \_$$ $$\sigma(0\ 1\ 0\ 0\ 1\ 1\ \_\ \_)=0\ 1\ 0\ 1\ 0\ 1\ \_\ \_$$ $$\sigma(0\ 1\ 0\ 0\ 1\ \_\ \_\ \_)=0\ 1\ 0\ 1\ 0\ \_\ \_\ \_$$ $$\sigma(0\ 1\ 0\ 0\ \_\ \_\ \_\ \_)=0\ 1\ 0\ \_\ 0\ \_\ \_\ \_$$ $$\sigma(0\ 1\ 0\ \_\ \_\ \_\ \_\ \_)=0\ 1\ 0\ \_\ \_\ \_\ \_\ \_$$ $$\sigma(0\ 1\ \_\ \_\ \_\ \_\ \_\ \_)=\ \_1\ 0\ \_\ \_\ \_\ \_\ \_$$ $$\sigma(0\ \_\ \_\ \_\ \_\ \_\ \_\ \_)=\ \_\ \_0\ \_\ \_\ \_\ \_\ \_$$
In cycle notation, this $\sigma$ is given by $(13)(45)$. The idea is that we want to lump everything as close together as possible in each step. The only time there is a problem is when the number of $1$'s significantly exceeds the number of $0$'s or vice-versa (this forces a separation into groups). If you want formal rigor, I bet it is possible to do some sort of inductive construction/proof, but I doubt such an endeavor would be illuminating. Honestly, it would probably be easier to write pseudocode depicting the algorithm for the construction, and then argue inductively about the pseudocode.
(Part 2) We prove $b_n(\sigma)\geq\big|C_0(s_n)-C_1(s_n)\big|$ for all $n$ and all $\sigma\in A(s)$. Again, we argue by example. Consider that $C_0(s_8)=5$ and $C_1(s_8)=3$. I claim $$0\ 1\ 0\ 1\ 0\ 1\ 0\ \_\ 0$$ packs $s_8$ into the smallest number of groups. Consider that $C_0(s_{12})=4$ and $C_1(s_{12})=8$. I claim $$1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ \_\ 1\ \_\ 1\ \_\ 1$$ packs $s_{12}$ into the smallest number of groups. In each case, notice the number of groups is equal to $\big|C_0(s_n)-C_1(s_n)\big|$. Previously, we had to take the maximum of this number with $1$ to account for the possibility of $C_0(s_n)=C_1(s_n)$, in which case there is still $1$ group.