Consider a graph $G=(V,E)$ with $V=\{\{a,b\}: a,b \in [n], a \not= b\}$, or equivalently $\ V:=\binom {[n]}2\ $ for short.
Assume also that $G$ is a cluster graph (a disjoint union of complete graphs) with at most $n$ clusters.
For every distinct elements $a,b$ of $[n]$ consider a bipartite subgraph $G_{\{a,b\}}$ of $G$, with parts $V_a=\{\{a,c\}:c\in [n]\setminus\{a,b\}\}$ and $V_b=\{\{b,c\}:c\in [n]\setminus\{a,b\}\}$. It is required that $G_{\{a,b\}}$ has no perfect matching of size $m$.
QUESTION: I would like to get an upper bound for the number of edges in $G$. In particular, can we prove or disprove that the upper bound is $< \binom{n}{3}$ when $m = \lfloor (n-1)/2 \rfloor$?
This problem is the dual of this one, because the graph $G$ there is the complement of $G$ here. Also, here we have added the "cluster graph" requirement above.
The problem can be rephrased as follows: among all commutative magmas $S$ of order $n$, where there does not exist $a, b \in S = \{s_1, \ldots, s_n\}$ with $a \ne b$, and two $m$-element subsets $X = \{x_1, \ldots, x_m\}$ and $Y = \{y_1, ... ,y_m\}$ of $S \setminus \{a,b\}$ such that $ax_i = by_i$ for each $i=1, \ldots m$, and defined $q_1, \ldots, q_n$ the number of occurrences of $s_1, \ldots, s_n$ respectively in the "half" Cayley table for different operands only, we want to find an upper bound for $\sum_{i=1}^n \binom{q_i}{2}$. The problem is related to this conjecture, and in particular to the case of the union-closed sets conjecture. Proving that the upper bound is $< \binom{n}{3}$ when $m = \lfloor (n-1)/2 \rfloor$ would prove it, due to this other proof. Maybe instead of finding an upper bound for $\sum_{i=1}^n \binom{q_i}{2}$ we could try to seek a sequence $q_1^{\star}\ge\ldots\ge q_n^{\star}$ that majorizes all feasible $q_1\ge\ldots\ge q_n$.
Without the "cluster graph" requirement we know from the linked question answer that:
$$|E| \le \binom{\binom{n}{2}}{2} - \frac{(n-m-1)(n-1)n(n+1)}8$$
and using an Integer Linear Program for the case $m = \lfloor (n-1)/2 \rfloor$ we know that the maximum possible values for $|E|$ are $0,0,13,22,72$ respectively for $n=3,4,5,6,7$.
Adding the new "cluster graph" requirement, the maximum possible values for $|E|$, obtained with an updated ILP, are $0,8,12$ respectively for $n=3,5,6$ and the problem is infeasible for $n=4$. We have $8 \lt \binom{5}{3}$ and $12 \lt \binom{6}{3}$.
Now I describe my attempt, following the answer to the linked question. Let $C_1, \ldots, C_n$ be the (possibly empty) clusters of $G$. Let $G_{\{a,b\}}^{(i)}$, subgraphs of $C_i$, $1 \le i \le n$, be defined as in the second paragraph. Their parts are $V_a^{(i)}$ and $V_b^{(i)}$ of size $x_a^{(i)}$ and $x_b^{(i)}$ respectively. Let $y_i = \min(x_a^{(i)},x_b^{(i)})$, $1 \le i \le n$. We want to find:
$$\max \sum_{i=1}^n \binom{x_a^{(i)}+x_b^{(i)}}{2}$$
subject to:
$$\sum_{i=1}^n y_i \le m-1 \\ \sum_{i=1}^n x_a^{(i)} = n-2 \\ \sum_{i=1}^n x_b^{(i)} = n-2 $$
@RobPratt answer regarding this IQP shows how to solve it, however the maximum values are worse than the maximum number of edges of $G_{a,b}$ in the answer to the linked question, i.e. $(m−1)(n−2)$, therefore my attempt does not work.
Is it possible to get an analytical bound to the question above?
