# The HCCL-DKU System for fake audio generation task of the 2022 ICASSP ADD
Challenge

###### Abstract

The voice conversion task is to modify the speaker identity of continuous
speech while preserving the linguistic content. Generally, the naturalness and
similarity are two main metrics for evaluating the conversion quality, which
has been improved significantly in recent years. This paper presents the HCCL-
DKU entry for the fake audio generation task of the 2022 ICASSP ADD challenge.
We propose a novel ppg-based voice conversion model that adopts a fully end-
to-end structure. Experimental results show that the proposed method
outperforms other conversion models, including Tacotron-based and Fastspeech-
based models, on conversion quality and spoofing performance against anti-
spoofing systems. In addition, we investigate several post-processing methods
for better spoofing power. Finally, we achieve second place with a deception
success rate of 0.916 in the ADD challenge.

Index Terms—  voice conversion, anti-spoofing, post-processing, ADD challenge

##  1 Introduction

The first Audio Deep Synthesis Detection Challenge spurs researchers worldwide
into building innovative techniques that can further accelerate and foster
research on detecting deep fake audios. This challenge includes three fake
audio detection tasks and a contrasting task that generates fake audio. In
this paper, we present our proposed system for the fake audio generation task
(Track 3.1). Both multi-speaker text-to-speech (TTS) and voice conversion
techniques can be used to generate synthesized audios for Track 3.1.
Nevertheless, since the voice conversion attains better spoofing performance
against detection systems, we choose to use voice conversion in this
challenge.

Voice conversion (VC) is a technique that converts a source speaker’s voice to
a target speaker’s voice without changing the linguistic information [1]. With
the development of deep learning, there are plenty of researches on deep
learning based voice conversion. Generative adversarial network and its
variants, such as StarGAN-VC [2] and CycleGAN-VC [3] use generator or
conditional generator to transform the source speaker’s features to target
speakers’ features directly. Autoencoder based model, such as, AutoVC[4],
VQVC[5] and so on. However, benefiting from acoustic features extracted by ASR
models can keep the linguistic information while removing most speaker
information. So ppg-based and cascading ASR and TTS model show excellent
performance both in conversion quality and stability.

Nevertheless, the traditional cascading pipeline is rather complicated, and
there are cascaded errors and over-smoothing issues across speech modules.
Therefore, we proposed a fully end-to-end ppg-based VC model inspired by VITS
[6]. Specifically, our proposed model incorporates a conformer encoder from a
pre-trained ASR model and a few transformer blocks on mel spectrograms, while
we use a posterior encoder upon linear spectrograms. Outputs from those two
modules are constraint to be from the same distribution. Then
reparameterization process and the HiFiGAN decoder are followed to convert the
hidden features to the target waveform. Moreover, we explore several physical
spoofing strategies to improve the performance of attacks against anti-
spoofing systems.

The rest of the paper is organized as follows: Section 2 describes our
proposed method thoroughly. Experimental results are shown in Section 3, while
the conclusion is drawn in Section 4.

Fig. 1: Proposed method structure: (a) training procedure (b) inference
procedure

##  2 Methods

This section describes the details of our proposed voice conversion
architecture along with the training procedures. Basically, we utilize an
encode from a pre-trained hybrid CTC/Attention transformer-based ASR model to
extract Phonetic PosteriorGrams (PPGs). Then PPGs are converted to raw
waveform by a fully end-to-end model.

###  2.1 Model structure

Fig.1 showes the overall pipeline of the proposed model. The model can be
divided into five components and they are introduced in detail in the
following sections.

####  2.1.1 Conformer Encoder

Conformer [7] is a convolution-augmented transformer for ASR. It is a stack of
two feed-forward modules, a self-attention module and a convolution module.The
conformer encoder takes the mel spectrum $m$ as input to generate the hidden
linguistic embedding $g$.

For convenience, we adopt the implementation of
Wenet111https://github.com/wenet-e2e/wenet[8] and its pretrained model on
WenetSpeech222https://wenet-e2e.github.io/WenetSpeech/[9] as the conformer
encoder of the proposed implementation.

####  2.1.2 Transformer blocks

We adopt Feed-Forward Transformer as the encoder in conversion model. It
includes a feed-forward structure based on Multi-Head Self-Attention and 1D
convolutions and this modules was firstly proposed in FastSpeech[10], which
has been one of the most popular TTS framework. The input to the transformer
blocks, which is a concatenation of hidden linguistic information $g$ and a
speaker embedding $s$, is converted to the mean $q_{mean}$ and log variance
$q_{logvar}$ of a gaussian distribution by this module.

####  2.1.3 Posterior Encoder

For the posterior encoder, the non-causal WaveNet[11] residual blocks used in
WaveGlow[12] were adopted. The WaveNet residual block consists of dilated
convolutions with skip connection and a gated activation. And for multi-
speaker task, we add speaker embedding in residual blocks by global
conditioning. The posterior encoder take linear spectrum $x_{linear}$ and
speaker embedding $s$ as inputs to produce the mean $p_{mean}$ and log
variance $p_{logvar}$ of a gaussian distribution.

####  2.1.4 HiFiGAN decoder

The decoder is almost essentially the HiFi-GAN generator[13]. It is a stack of
convolution blocks, which include transpose convolution and multi-receptive
field fusion model(MRF). MRF is composed of residual blocks with different
receptive field size. To avoid possible checkerboard artifacts caused by
transpose convolution, we use temporal nearest interpolation layer followed by
1-D convolution layer as the upsampling layer[14]. The input of HiFiGAN
decoder includes hidden representation $z$ and speaker embedding $embed$. And
$z$ can be represented in Eq.1 during training.

$z=p_{mean}+e^{0.5*p_{logvar}}*\mathcal{N}(0,1)$ (1)

The HiFiGAN decoder takes hidden representation $z$ and speaker embedding $s$
as input to get generated $w_{g}$.

####  2.1.5 Discriminator

The discriminators includes multi-period discriminator(MPD) and multi-scale
discriminator(MPD). MPD is a mixture of window-based sub-discriminators, each
of which operates on different periodic patterns of waveform. MSD directly
operate on time domain of different scales.

###  2.2 KL divergence

Traditional TTS and VC methods cascade acoustic model and vocoder by using mel
spectrum as the intermediate feature, which may cause cascaded error and over-
smoothing due to mean squared error optimization. Due to the transformer block
and posterior encoder predict the mean and variance of gaussian distributions,
we can use KL divergence to measure the distance of two distributions. KL
divergence of two univariate gaussians can be represented in Eq.2.

$\displaystyle KL(p,q)$ $\displaystyle=L_{kl}$ (2)
$\displaystyle=log(\frac{\sigma_{q}}{\sigma_{p}})+\frac{\sigma_{p}^{2}+(\mu_{p}-\mu_{q})^{2}}{2\sigma_{q}^{2}}-\frac{1}{2}$

where $\sigma_{p}=e^{0.5p_{logvar}}$, $\sigma_{q}=e^{0.5q_{logvar}}$,
$\mu_{p}=p_{mean}$ and $\mu_{q}=q_{mean}$ in our proposed method.

###  2.3 Adversarial Training

As with GAN based vocoders, we also add a discriminator $D$ that distinguishes
audio $w_{g}$ generated by generator $G$ and ground truth audio $w_{r}$. We
use least-squares as the adversarial loss for its stablity and feature-
matching loss for training the generator.

$\displaystyle
L_{adv}(D)=E_{(w_{f},w_{r})}\Big{[}(D(w_{r})-1)^{2}+D(G(w_{f}))^{2}\Big{]}$
(3) $\displaystyle L_{adv}(G)=E_{w_{f}}\Big{[}(D(G(w_{f})-1)^{2}\Big{]}$
$\displaystyle
L_{fm}(G)=E_{(w_{f},w_{r})}\Big{[}\sum_{T}^{l=1}\frac{1}{N_{l}}\|D^{l}(y)-D^{l}(G(z))\|_{1}\Big{]}$

where $T$ denotes the number of sub-discriminators and $D^{l}$ denotes the
feature map of the $l$-th layer of sub-discriminator with $N_{l}$ number of
features.

###  2.4 Training and inferencing

Due to GPU memory limit, we randomly select segments from hidden
representations and the corresponding waveform for training the HiFiGAN
decoder. We use $L_{2}$ loss between the ground truth and generated mel-
spectrogram as reconstruction loss.

$L_{recon}=\|mel(w_{g})-mel(w_{f})\|_{2}$ (4)

Combining conditional VAE and GAN training, the total loss for training the
generator can be expressed as follows:

$L_{total}=L_{recon}+L_{kl}+L_{adv}(G)+L_{fm}(G)$ (5)

In inferencing stage, the posterior encoder is not required and also the
speaker embedding is set to the target speaker embedding.

##  3 Experiments

###  3.1 Experimental setup

All our experiments are conducted on open source mandarin datasets, including
the 85h multi-speaker dataset AISHELL3[15], an 12h female dataset from
databaker333https://www.data-baker.com/#/data/index/source, and the 5h male
and 5h female M2VoC dev set444http://challenge.ai.iqiyi.com/M2VoC. We convert
the audio from 48KHz into 24KHz for all generation experiments and 16KHz for
all evaluations.

###  3.2 Comparison of VC methods

We conduct experiments of different vc methods with databaker and M2VoC dev
set. To make it fair, all vc methods share the same conformer encoder. We
modified tacotron2[16] and fastspeech as the acoustic model respectively,
which we call _ppg-taco_ and _ppg-fast_ below. They share the same HiFi-GAN
vocoder, which has the same structure and parameters with HiFiGAN decoder in
the proposed method. The conversion results are shown in Fig.2, from which can
be observed that there are harmonic structures in breath and unvoiced segments
of _ppg-taco_ and _ppg-fast_ , which may be detected by anti-spoofing systems
easily.

Fig. 2: Converted results:(a) ppg-fast (b) ppg-taco (c) proposed method Table 1: EER of VC methods on anti-spoofing systems VC method | AASIST$\uparrow$ | FFT_SENet$\uparrow$ | MSTST_LCNN$\uparrow$ | SILENCE$\uparrow$ | Average$\uparrow$
---|---|---|---|---|---
ppg-fast | 41.2% | 46.8% | 35.5% |  60.25% | 45.9%
ppg-taco | 37.5% |  48.5% | 31.2% | 47.2% | 41.1%
proposed |  62.3% | 39.3% |  51.6% | 46.25% |  49.8%
Table 2: EER of post-processing in VC and TTS methods on anti-spoofing systems Spoof Method | Post-processing | AASIST$\uparrow$ | FFT_SENET$\uparrow$ | MSTFT$\uparrow$ | SILENCE$\uparrow$ | AVERAGE$\uparrow$
---|---|---|---|---|---|---
vits_tts | - | 70.0% | 69.5% | 73.4% | 37.2% | 62.5%
proposed_vc | - |  84.3% | 72.6% | 85.9% | 36.4% | 69.8%
vits_tts | silence replacement | 69.5% | 70.5% | 77.9% | 36.8% | 63.7%
proposed_vc | silence replacement | 84.0% | 82.2% | 88.0% | 53.2% | 76.9%
proposed_vc | global noise(SNR=40) | 83.8% | 78.3% | 87.9% | 56.8% | 76.7%
proposed_vc | global noise(SNR=50) | 84.0% | 81.0% | 88.0% | 53.5% | 76.6%
Table 3: Speech naturalness and Speaker similarity Method | Speech naturalness$\uparrow$ | Speaker similarity$\uparrow$
---|---|---
ground truth | 4.62$\pm$0.14 | 4.75$\pm$0.16
ppg-fast | 3.46$\pm$0.19 | 3.69$\pm$0.20
ppg-taco | 3.87$\pm$0.21 | 3.91$\pm$0.17
proposed | 4.01$\pm$0.20 | 3.98$\pm$0.19

AASIST[17], FFT_SENet[18], MSTST_LCNN[19] and SILENCE were used to test our
pre-hypothesis. 800 fake samples and 400 real samples from databaker were used
as trials for test anti-spoofing EER. The results are shown in Table. 1. The
proposed method is obviously better than other two baseline methods.

Subjective evaluation on speech naturalness and speaker similarity of
converted speech are conducted. There are ten speakers in the survey and are
asked to give a 5-scale opinion score on both speaker similarity and
naturalness. The subjective evaluation results are shown in Table. 3.
Generated audios can be found in the demo
page555https://miracyan.github.io/2022hccldkuadd/.

###  3.3 Post-processing

To further enhance the attacking capability of speech produced by our proposed
method, we consider adopting countermeasures against silence based anti-
spoofing systems. We experimented two methods of appending silence to our
generated speech.

The first one is silence replacement. Using a non-neural-network VAD system
that quickly finds silence segments in fake speech, we randomly selected from
our extracted real silence segments and crop them to the same length as the
fake silence segments. Then we replaced the silence segments in the fake
speech with the cropped real silence segments.

The second one is global noise. We randomly select multiple real silence
segments and then normalize their amplitudes to average level. After that, we
connect them together through the strategy of parabolic cross-fading and
finally directly superimpose them to our fake speech like additive noise.

We compared post-processing on audio generated from proposed method and VITS,
which is trained on AISHELL3. In Table.1, the proposed method performs worse
in FFT_SENet and SILENCE worse, while in Table.2, the proposed method with
post-processing improves a lot in FFT_SENet and SILENCE, which verifies the
validity of the proposed post-processing methods.

###  3.4 Evaluations

Track 3.1 requires participants to generate attack samples with respect to the
given text and speaker identities. For voice conversion, this task lacks
source audio. As our proposed method is an any-to-many voice conversion
system, we apply VITS trained on databaker to get source audios of the given
text, then convert them to given speaker identities. Then post-processing of
silence replacement was conducted on generated samples.

Fig. 3: Deception success rate(DSR) team rank

The deception success rate of all teams is shown in Fig.3. We achieve the
second place, which verifies the effectiveness of our proposed method and
post-processing technique.

##  4 Conclusion

In this paper, we present a novel e2e structure for any-to-many voice
conversion, which performs better than baselines in terms of voice conversion
quality and deception success rate. And we also proposed a simple but
efficient post-processing method.

## References

  * [1] Berrak Sisman, Junichi Yamagishi, Simon King, and Haizhou Li,  “An overview of voice conversion and its challenges: From statistical modeling to deep learning,”  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 2020.

  * [2] Hirokazu Kameoka, Takuhiro Kaneko, Kou Tanaka, and Nobukatsu Hojo,  “Stargan-vc: Non-parallel many-to-many voice conversion using star generative adversarial networks,”  in 2018 IEEE Spoken Language Technology Workshop (SLT). IEEE, 2018, pp. 266–273.
  * [3] Takuhiro Kaneko and Hirokazu Kameoka,  “Cyclegan-vc: Non-parallel voice conversion using cycle-consistent adversarial networks,”  in 2018 26th European Signal Processing Conference (EUSIPCO). IEEE, 2018, pp. 2100–2104.
  * [4] Kaizhi Qian, Yang Zhang, Shiyu Chang, Xuesong Yang, and Mark Hasegawa-Johnson,  “Autovc: Zero-shot voice style transfer with only autoencoder loss,”  in International Conference on Machine Learning. PMLR, 2019, pp. 5210–5219.
  * [5] Da-Yi Wu, Yen-Hao Chen, and Hung yi Lee,  “VQVC+: One-Shot Voice Conversion by Vector Quantization and U-Net Architecture,”  in Proc. Interspeech 2020, 2020, pp. 4691–4695.
  * [6] Jaehyeon Kim, Jungil Kong, and Juhee Son,  “Conditional variational autoencoder with adversarial learning for end-to-end text-to-speech,”  arXiv preprint arXiv:2106.06103, 2021.
  * [7] Anmol Gulati, James Qin, Chung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, and Ruoming Pang,  “Conformer: Convolution-augmented Transformer for Speech Recognition,”  in Proc. Interspeech 2020, 2020, pp. 5036–5040.
  * [8] Zhuoyuan Yao, Di Wu, Xiong Wang, Binbin Zhang, Fan Yu, Chao Yang, Zhendong Peng, Xiaoyu Chen, Lei Xie, and Xin Lei,  “Wenet: Production oriented streaming and non-streaming end-to-end speech recognition toolkit,”  in Proc. Interspeech, 2021.
  * [9] Binbin Zhang, Hang Lv, Pengcheng Guo, Qijie Shao, Chao Yang, Lei Xie, Xin Xu, Hui Bu, Xiaoyu Chen, Chenchen Zeng, et al.,  “Wenetspeech: A 10000+ hours multi-domain mandarin corpus for speech recognition,”  arXiv preprint arXiv:2110.03370, 2021.
  * [10] Yi Ren, Yangjun Ruan, Xu Tan, Tao Qin, Sheng Zhao, Zhou Zhao, and Tie-Yan Liu,  “Fastspeech: fast, robust and controllable text to speech,”  in Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019, pp. 3171–3180.
  * [11] Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu,  “Wavenet: A generative model for raw audio,”  arXiv preprint arXiv:1609.03499, 2016.
  * [12] Ryan Prenger, Rafael Valle, and Bryan Catanzaro,  “Waveglow: A flow-based generative network for speech synthesis,”  in ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2019, pp. 3617–3621.
  * [13] Jungil Kong, Jaehyeon Kim, and Jaekyoung Bae,  “Hifi-gan: Generative adversarial networks for efficient and high fidelity speech synthesis,”  Advances in Neural Information Processing Systems, vol. 33, 2020\.
  * [14] Jordi Pons, Santiago Pascual, Giulio Cengarle, and Joan Serrà,  “Upsampling artifacts in neural audio synthesis,”  in ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2021, pp. 3005–3009.
  * [15] Yao Shi, Hui Bu, Xin Xu, Shaoji Zhang, and Ming Li,  “Aishell-3: A multi-speaker mandarin tts corpus and the baselines,”  arXiv preprint arXiv:2010.11567, 2020.
  * [16] Jonathan Shen, Ruoming Pang, Ron J Weiss, Mike Schuster, Navdeep Jaitly, Zongheng Yang, Zhifeng Chen, Yu Zhang, Yuxuan Wang, Rj Skerrv-Ryan, et al.,  “Natural tts synthesis by conditioning wavenet on mel spectrogram predictions,”  in 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2018, pp. 4779–4783.
  * [17] Jee-weon Jung, Hee-Soo Heo, Hemlata Tak, Hye-jin Shim, Joon Son Chung, Bong-Jin Lee, Ha-Jin Yu, and Nicholas Evans,  “Aasist: Audio anti-spoofing using integrated spectro-temporal graph attention networks,”  arXiv preprint arXiv:2110.01200, 2021.
  * [18] Yuxiang Zhang, Wenchao Wang, and Pengyuan Zhang,  “The Effect of Silence and Dual-Band Fusion in Anti-Spoofing System,”  in Proc. Interspeech 2021, 2021, pp. 4279–4283.
  * [19] Anton Tomilov, Aleksei Svishchev, Marina Volkova, Artem Chirkovskiy, Alexander Kondratev, and Galina Lavrentyeva,  “Stc antispoofing systems for the asvspoof2021 challenge,”  in Proc. ASVspoof 2021 Workshop, 2021.


11institutetext: Indian Institute of Technology, Gandhinagar, Palaj 382355
11email<EMAIL_ADDRESS>
# The Parameterized Complexity of Happy Colorings

Neeldhara Misra  11 I. Vinod Reddy  11

###### Abstract

Consider a graph $G=(V,E)$ and a coloring $c$ of vertices with colors from
$[\ell]$. A vertex $v$ is said to be happy with respect to $c$ if $c(v)=c(u)$
for all neighbors $u$ of $v$. Further, an edge $(u,v)$ is happy if
$c(u)=c(v)$. Given a partial coloring $c$ of $V$, the Maximum Happy Vertex
(Edge) problem asks for a total coloring of $V$ extending $c$ to all vertices
of $V$ that maximises the number of happy vertices (edges). Both problems are
known to be NP-hard in general even when $\ell=3$, and is polynomially
solvable when $\ell=2$. In [IWOCA 2016] it was shown that both problems are
polynomially solvable on trees, and for arbitrary $k$, it was shown that MHE
is NP-hard on planar graphs and is $\sf{FPT}$ parameterized by the number of
precolored vertices and branchwidth.

We continue the study of this problem from a parameterized prespective. Our
focus is on both structural and standard parameterizations. To begin with, we
establish that the problems are $\sf{FPT}$ when parameterized by the treewidth
and the number of colors used in the precoloring, which is a potential
improvement over the total number of precolored vertices. Further, we show
that both the vertex and edge variants of the problem is $\sf{FPT}$ when
parameterized by vertex cover and distance-to-clique parameters. We also show
that the problem of maximizing the number of happy edges is $\sf{FPT}$ when
parameterized by the standard parameter, the number of happy edges. We show
that the maximum happy vertex (edge) problem is NP-hard on split graphs and
bipartite graphs and polynomially solvable on cographs.

##  1 Introduction

Given an undirected vertex colored graph $G$, we say that a vertex $v$ in $G$
is happy if $v$ and all its neighbors have same color. Along similar lines, an
edge is happy if both its endpoints have same color. Given a partially colored
graph $G$ with $\ell$ colors, the Max Happy Vertices ($\ell$-MHV) problem is
to color the remaining vertices of graph such that number of happy vertices is
maximized. The Max Happy Edges ($\ell$-MHE) problem is to color the remaining
vertices of graph such that number of happy edges is maximized.

The $\ell$-MHE problem generalizes the Multiway Uncut problem which is defined
as follows. Given a graph $G$ and a terminal set
$S=\\{s_{1},\cdots,s_{k}\\}\subseteq V(G)$, the goal is to find a partition
$\\{V_{1},\cdots,V_{k}\\}$ of $V(G)$ such that the number of edges with both
ends points present in same $V_{i}$ is maximized. The Multiway Uncut problem
is a special case of $\ell$-MHE problem, where each terminal has a unique
precolor.

Both $\ell$-MHV and $\ell$-MHE are NP-hard [10] on general graphs for
$\ell\geq 3$ and both $2$-MHV and $2$-MHE can be solved in polynomial time.
Aravind et al. [2] showed that both the problems admit linear time algorithms
on trees. Zhang et al. [10] studied both problems from the approximation point
of view and given a $max\\{1/k,\Omega(d^{-3})\\}$-approximation algorithm for
the $k$-MHV problem, where $d$ is the maximum degree of the graph, and a
$1/2$-approximation algorithm for the $\ell$-MHE problem.

We initiate, in this work, the study of these problems from a parameterized
perspective. The problem admits several natural parameters: the number of
colors ($\ell$), the number of precolored vertices (say $t$), the number of
happy vertices or edges (denoted by $k$, note that these parameters reflect
the quality of the solution, and might hence be regarded as standard
parameters), and various structural parameters. In particular, the linear time
algorithms on trees prompt us to consider the question of whether the problem
is $\sf{FPT}$ when parameterized by treewidth of the graph ($w$). The work in
[2] already establishes that the problem is $\sf{FPT}$ when parameterized by
treewidth and the number of precolored vertices. Since $\ell$-MHV and
$\ell$-MHE are both NP-hard even when there are only three colors used by the
precoloring, the problems are para-NP-hard by this parameter. We now proceed
to describe some of the results that we obtain for various combinations of
parameters.

#### Our Contributions.

We continue the study of this problem from a parameterized prespective. Our
focus is on both structural and standard parameterizations. To begin with, we
establish that the problems are FPT when parameterized by the treewidth and
the number of colors used in the precoloring, which is a potential improvement
over the total number of precolored vertices. This follows from a MSO
formulation but we also demonstrate a dynamic programming solution on nice
tree decompositions.

Further, we show that both the vertex and edge variants of the problem is
$\sf{FPT}$ when parameterized by vertex cover and distance-to-clique
parameters. Observe that there is no exponential dependence here on the number
of colors in the precoloring. We achieve this by not guessing all possible
assignments of colors on the modulators, but just a wireframe of equivalence
classes based on which vertices in the modulators recieve the same colors, and
it turns out that this coarser information is sufficient to determine an
optimal coloring. We also show that the problem of maximizing the number of
happy edges is $\sf{FPT}$ when parameterized by the standard parameter, the
number of happy edges. This turns out to be a problem that reduces to the case
of bounded vertex cover number.

In the context of studying the problems on special classes of graphs, we show
that the problem of maximizing the number of happy vertices is polynomially
solvable on cographs. Unfortunately, our polynomial time approach for the
$\ell$-MHV problem does not extend in any straightforward way to the
$\ell$-MHE problem. On the other hand, both variants of the problem turn out
to be NP-hard on split graphs and bipartite graphs. We note that some of the
results shown here, particularly relating to algorithms parameterized by the
treewidth of the graph, were obtained independently in [1, 3].

##  2 Preliminaries

In this section, we introduce the notation and the terminology that we will
need to describe our algorithms. Most of our notation is standard. We use
$[k]$ to denote the set $\\{1,2,\ldots,k\\}$. We introduce here the most
relevant definitions, and use standard notation pertaining to graph theory
based on [5, 6].

All our graphs will be simple and undirected unless mentioned otherwise. For a
graph $G=(V,E)$ and a vertex $v$, we use $N(v)$ and $N[v]$ to refer to the
open and closed neighborhoods of $v$, respectively. The _distance_ between
vertices $u,v$ of $G$ is the length of a shortest path from $u$ to $v$ in $G$;
if no such path exists, the distance is defined to be $\infty$. A graph $G$ is
said to be _connected_ if there is a path in $G$ from every vertex of $G$ to
every other vertex of $G$. If $U\subseteq V$ and $G\left[U\right]$ is
connected, then $U$ itself is said to be connected in $G$. For a subset
$S\subseteq V$, we use the notation $G\setminus S$ to refer to the graph
induced by the vertex set $V\setminus S$.

#### Special Graph Classes.

We now define some of the special graph classes considered in this paper. A
graph is _bipartite_ if its vertex set can be partitioned into two disjoint
sets such that no two vertices in same set are adjacent. A graph is a _split
graph_ if its vertex set can be partitioned into a clique and an independent
set. Split graphs do not contain $C_{4}$, $C_{5}$ or $2K_{2}$ as induced
subgraphs. _Cographs_ are $P_{4}$-free graphs, that is, they do not contain
any induced paths on four vertices..

#### Parameterized Complexity.

A parameterized problem denoted as $(I,k)\subseteq\Sigma^{*}\times\mathbb{N}$,
where $\Sigma$ is fixed alphabet and $k$ is called the parameter. We say that
the problem $(I,k)$ is fixed parameter tractable with respect to parameter $k$
if there exists an algorithm which solves the problem in time
$f(k)|I|^{O(1)}$, where $f$ is a computable function. For a detailed survey of
the methods used in parameterized complexity, we refer the reader to the texts
[7, 5].

We now define the problems that we consider in this paper.

Max Happy Vertices Parameter: $k$ Input: A graph $G=(V,E)$, a partial coloring
$p:S\rightarrow[\ell]$ for some $S\subseteq V$, and a positive integer $k$.
Question: Is there a coloring $c:V\rightarrow[\ell]$ extending $p$ such that
$G$ has at least $k$ happy vertices with respect to $c$?

Max Happy Edges Parameter: $k$ Input: A graph $G=(V,E)$, a partial coloring
$p:S\rightarrow[\ell]$ for some $S\subseteq V$, and a positive integer $k$.
Question: Is there a coloring $c:V\rightarrow[\ell]$ extending $p$ such that
$G$ has at least $k$ happy edges with respect to $c$?

##  3 Structural Parameterizations

In this section, we explore the complexity of Max Happy Vertices and Max Happy
Edges with respect to various structural parameterizations. A key question
here is if these problems are $\sf{FPT}$ when parameterized by treewidth
alone. While we do not resolve this question, we make partial progress in two
ways.

First, we show that Max Happy Vertices and Max Happy Edges are both $\sf{FPT}$
when parameterized by the combined parameter $(\ell+w)$, where $\ell$ is the
number of colors used in the precoloring and $w$ is the treewidth of the input
graph. In particular, our running time is
${\mathcal{O}}^{*}((2\ell)^{(w+1)})$. It was already known that the problem is
$\sf{FPT}$ when parameterized by $(q+w)$, where $q$ is the number of
precolored vertices. It was also known that the problem admits a linear-time
algorithm on trees. In general, since $\ell\leq q$, and the treewidth of a
tree is one, our result unifies these results (although the running time we
obtain on trees is quadratic, rather than linear).

Secondly, we show that Max Happy Vertices and Max Happy Edges are both
$\sf{FPT}$ when parameterized by the size of the vertex cover. The running
time of this algorithm has a polynomial dependance on $\ell$, which is why
this is not subsumed by our $\sf{FPT}$ algorithm when we parameterized by
$(\ell+w)$. Along similar lines, we also show that Max Happy Vertices and Max
Happy Edges are both $\sf{FPT}$ when parameterized by the size of a clique
modulator.

The rest of this section is organized as follows. In the first subsection, we
demonstrate that the problem is $\sf{FPT}$ parameterized by treewidth. Next,
we consider the vertex cover and distance to clique parameterizations. In the
last subsection, we show how Max Happy Edges admits a $\sf{FPT}$ algorithm for
the standard parameter (the number of happy edges) by reducing it to the case
of bounded vertex cover number.

###  3.1 Treewidth

######  Theorem 3.1.

Max Happy Vertices and Max Happy Edges are both $\sf{FPT}$ when parameterized
by $(\ell+w)$, where $\ell$ is the number of colors used in the precoloring
and $w$ is the treewidth of input graph.

###### Proof.

We give two different proofs to show Max Happy Vertices and Max Happy Edges
are both $\sf{FPT}$ when parameterized by $(\ell+w)$. The first proof uses a
standard dynamic programming approach on nice tree decompositions (see [5] for
definition). The second proof follows from an application of Courcelle’s
theorem [4] and the fact that the Max Happy Vertices and Max Happy Edges
problems can be expressed by MSO formulas for fixed $\ell$.

Suppose the input is a graph $G$ precolored using a partial precoloring
function $p$ that uses $k$ colors. We briefly describe the MSO formulation
here. The first expression below shows that $S$ is a set of happy vertices
with respect to some partition of the graph into $k$ parts $V_{1},\ldots
V_{k}$.

$\displaystyle\mbox{Happy}(S,V_{1},\cdots V_{k})$ $\displaystyle:=$
$\displaystyle\forall u\in V(u\in S\land u\in V_{i}\Rightarrow\forall
v(adj(u,v)\Rightarrow v\in V_{i}))$

Next, we use a formulation to express that a given partition $V_{1},\cdots
V_{k}$ respects a precoloring $p:V\rightarrow[k]$. This is shown by
considering all pairs of vertices in the same color class and requiring that
no two vertices in the same color class have the same color.

$\displaystyle\mbox{Good}_{p}(V_{1},\cdots V_{k})$ $\displaystyle:=$
$\displaystyle\bigwedge_{1\leq i\leq k}\forall x,y\in V\left((x\in V_{i}\land
y\in V_{i})\land(\bigvee_{1\leq i\leq k}p(x)=i)\land(\bigvee_{1\leq i\leq
k}p(y)=i)\right)$ $\displaystyle\Rightarrow p(x)=p(y)$

Finally, following expression shows that there exists a total coloring of
graph with $k$ colors that respects $p$ (recall that $k$ is the number of
colors used by the precoloring $p$), such that all vertices of $S$ are happy.
The first part of the expression ensures that the $k$ chosen sets form a
partition and the second part of the expression ensures that the vertices in
$S$ are happy.

$\displaystyle\mbox{Happy}(S,k)$ $\displaystyle:=$ $\displaystyle\exists
V_{1},\cdots,V_{k}\left(\forall u\in V\left(\left(\bigvee_{1\leq i\leq k}u\in
V_{i}\right)\land\left(u\in V_{i}\Rightarrow\neg(u\in\bigvee_{i\neq
j}V_{j})\right)\right)\right)$
$\displaystyle\land~{}\mbox{Happy}(S,V_{1},\cdots V_{k})$
$\displaystyle\land~{}\mbox{Good}_{p}(V_{1},\cdots V_{k})$

The $k$-MHV problem is to find the maximum cardinality set $S$ such that:

$Happy(S):=max_{S}~{}\mbox{Happy}(S,k).$

Now by applying the Courcelle’s theorem [4] to above formula the $k$-MHV
problem can be solved in $f(k,tw)n^{O(1)}$ time.

For the sake of completeness, we briefly describe the more direct and standard
dynamic programming approach on nice tree decompositions. We describe here the
semantics of the table and the update algorithm, and skip the proof of
correctness (which is standard and easily checked)

We explain the DP for the Max Happy Vertices problem, noting that the details
for Max Happy Edges are analogous.

Let $(G,S,\ell,p,k)$ denote an instance of Max Happy Vertices. Let
$\mathcal{T}=(T,\\{B_{t}\\}_{t\in V(T)})$ be a nice tree decomposition of
width $w$. For a vertex $g\in T$, $T_{g}$ denote the subtree rooted at $g$,
let $\mathbb{B}_{g}$ denote the union of all the bags corresponding to
vertices in $T_{g}$, and let $G_{t}$ denote the graph induced by
$\mathbb{B}_{g}$, that is, $G[\mathbb{B}_{g}]$.

The table $\mathbb{T}_{t}$ corresponding to a bag $B_{t}$ is indexed by a pair
$(r,S)$, where $r:B\rightarrow[\ell]$ is a labeling of the vertices in the bag
with colors, and $S\subseteq B$ is a subset of vertices in the bag. We only
consider labelings that are consistent with the precoloring $p$ on the
vertices in $B$.

The table entry corresponding to $(r,S)$ at the bag $B_{t}$ is the maximum
number of happy vertices that can be obtained by a coloring of $G_{t}$ that is
consistent with the labeling $r$ on the vertices in $B$ and makes all the
vertices in $S$ happy. If there is no such coloring, then the table entry is
set to $-\infty$.

We now briefly describe the updates for the different node types. Consider the
bag $B_{t}$, and fix a labeling $r$ and a subset $S$ of $B_{t}$. Let $B_{q}$
denote the child node, and let $B_{x}$ and $B_{y}$ denote the children in the
case of a join node. Note that the base cases are straightforward.

  * •

Introduce Node. Suppose $v$ is introduced at bag $B_{t}$. Consider its color
and check if all neighbors of $v$ in the bag have the same color as $v$. If
this is not the case but $v\in S$ (or vice versa) then the value of the entry
is $-\infty$. Otherwise, let $d$ be the value of $\mathbb{T}_{q}$
corresponding to the restriction of $(r,S)$ on $B_{t}\setminus\\{v\\}$. The
entry in $B_{t}$ is either $d$ or $1+d$ depending on whether $v$ is happy or
not.

  * •

Forget Node. Suppose $v$ is forgotten at bag $B_{t}$. Otherwise, consider all
the entries in $\mathbb{T}_{q}$ corresponding to indices that are compatible
with $(r,S)$, and the entry in the present bag is the maximum among all of
these entries.

  * •

Join Node. Let $d_{1}$ and $d_{2}$ be the value of $\mathbb{T}_{x}$ and
$\mathbb{T}_{y}$ corresponding to $(r,S)$ in $B_{x}$ and $B_{y}$,
respectively. Let $d$ be $|S|$. The value of the table entry is then
$d_{1}+d_{2}-d$.

∎

###  3.2 Vertex Cover and Distance to Clique

######  Theorem 3.2.

Max Happy Vertices and Max Happy Edges are both $\sf{FPT}$ when parameterized
by the size of the vertex cover of the input graph.

###### Proof.

We first consider the Max Happy Vertices problem. Let $(G,S,\ell,p,k)$ denote
an instance of Max Happy Vertices. We will use $Q$ to refer to $V\setminus S$,
the set of vertices that are not precolored by $p$. Further, let $X\subseteq
V$ be a vertex cover of $G$. We use $d$ to denote $|X|$.

The algorithm begins by guessing a partition of $X$ into at most
$\min\\{\ell,d\\}$ parts. Note that the number of such partitions is at most
$d^{d}$. Intuitively, we are guessing the behavior of an optimal coloring $c$
when projected on the vertex cover, where our notion of behavior is given by
which vertices are colored in the same way as $c$. We also guess the subset of
vertices in the vertex cover that are happy with respect to $c$.

Let us formalize the notion of a behavior associated with a partition and the
subset of $X$. To begin with, let $\chi=(X_{1},\ldots,X_{t})$ be a fixed
partition of $X$, where $t\leq d$. For vertex $v\in X$, we abuse notation and
use $\chi(v)$ to denote the index of the part that $v$ belongs to in the
partition $\chi$. In other words, if $\chi(v)=i$, then $v\in X_{i}$. A pair of
vertices $u,v\in X$ such that $\chi(u)=\chi(v)$ are called equivalent — we
sometimes say that $u$ is equivalent to $v$, or that $u$ and $v$ are
equivalent. Finally, let $Y\subseteq X$ be a (possibly empty) subset of the
vertex cover.

We say that a coloring $c$ is valid and respects $(\chi,Y)$ if:

  * •

$c$ agrees with $p$ on $S$,

  * •

every vertex $v\in Y$ is happy with respect to $c$, and

  * •

for all $u,v\in X$, $c(u)=c(v)$ if and only if $u$ and $v$ are equivalent.

Our goal now is to find a valid coloring $c$ that respects $(\chi,Y)$. Let
$\lambda(v)$ denote the set of colors employed by $p$ in $N[v]$, in other
words, $\lambda(v):=\\{j~{}|~{}\exists u\in N[v],p(u)=j\\}.$

It is easy to check that there exists a valid coloring $c$ that respects
$(\chi,Y)$ if and only if the following conditions, which we will refer to as
$(\star)$, hold:

  * •

For any vertex $v\in Y$, $|\lambda(v)|\leq 1$.

  * •

For any pair of vertices $u,v$ that are equivalent and $u,v\in Y$, if
$\lambda(v)\neq\emptyset$ and $\lambda(v)\neq\emptyset$,
$\lambda(v)=\lambda(u)$.

  * •

For any pair of vertices $u,v$ that are not equivalent and $u,v\in Y$, we have
that $N(u)\cap N(v)=\emptyset$.

  * •

For any vertex $v\in Y$, every vertex $u\in N(v)\cap X$ is equivalent to $v$.

In particular, that these conditions are necessary follow from the definition
of what it means for a coloring to be valid and respect $(\chi,Y)$. The fact
that they are sufficient will follow from the coloring obtained by the
algorithm below.

We assume, without loss of generality, that all the conditions above are
satisfied: indeed, if not, we simply reject the choice of $(\chi,Y)$. Our
algorithm now proceeds to construct a coloring $c$ of $V$ that respects
$(\chi,Y)$. In fact, among all such colorings, we will construct one that
maximizes the number of happy vertices. To begin with, we initialize $c$ to
coincide with $p$ on $S$. For convenience, we will use $U$ to refer to the set
of uncolored vertices with respect to $c$. Observe that at this stage, $U=Q$,
and when the algorithm finishes, we will have $U=\emptyset$. We now proceed as
follows.

#### Phase 1. Identifying forced colors.

Let $v\in Y$ be such that $\lambda(v)\neq\emptyset$. Set $c(u)=j$ for all
$u\in N[v]\cap Q$. Further, set $c(u)=j$ for all $u$ equivalent to $v$ in
$\chi$. At the end of this phase, let $v$ be any vertex in $Y$ that either has
a precolored vertex in its closed neighborhood or has a precolored vertex that
is equivalent to it. At the end of this phase, $v$ is a happy vertex. Observe
that $c$ is well-defined because the conditions in $(\star)$ are true. We say
that $X_{i}$ is pending if $X_{i}\subseteq U$ at the end of Phase 1. If no
$X_{i}$ is pending, we skip directly to Phase 3.

#### Phase 2. Coloring the pending $X_{i}$’s.

Let $i$ be such that $X_{i}$ is pending, and let $j\in[\ell]$. Let $w[i,j]$
denote the number of vertices in $(V\setminus X)\cap S$ that will be happy if
all vertices of $X_{i}$ are colored $j$. This is simply the size of the set of
vertices in the independent set precolored $j$, whose neighborhoods lie
entirely in $X_{i}$.

Consider an auxiliary weighted bipartite graph, denoted by $H=((A,B),E)$ with
edge weights given by $w:E\rightarrow[|V|]$. This graph is constructed as
follows. The vertex set $A$ contains one vertex for every $X_{i}$ that is
pending at the end of the first phase. The vertex set $B$ contains a vertex
corresponding to every element in $[\ell]\setminus[\cup_{v\in X}c(v)]$, that
is to say, $B$ has one vertex for every color that is not already used on
vertices in $X$ in Phase 1. The weight of the edge $(a_{i},b_{j})$ is simply
$w[i,j]$. We find a matching $M$ of maximum weight in $H$. It is easy to see
that any such matching saturates $A$, since $|B|\geq|A|$, the weights are
positive, and all edges are present.

For a pending part $X_{i}$, we now color all vertices in $X_{i}$ based on the
matching $M$. In particular, if $M$ matches $a_{i}$ to $b_{j}$, then we color
all vertices in $X_{i}$ with color $j$. At the end of this phase, all vertices
in $X$ have been colored — formally, $X\cap U=\emptyset$.

#### Phase 3. Coloring the independent set.

We say that an uncolored vertex in $V\setminus X$ is definitely unhappy with
respect to $\chi$ if it has at least two neighbors which are not equivalent
with respect to $\chi$. If a vertex $v$ that is definitely unhappy has a
neighbor $u$ in $Y$, then assign $c(u)$ to $v$. Observe that this coloring is
well-defined, since vertices in $Y$ that had different colors, and are hence
not equivalent, have disjoint neighborhoods. Arbitrarily color all the other
remaining “definitely unhappy” vertices, namely those that only have neighbors
in $X\setminus Y$.

Similarly, we say that an uncolored vertex in $V\setminus X$ is always happy
if all of its neighbors are equivalent. For a vertex $v$ that is always happy,
let $j$ be such that all neighbors of $v$ lie in $X_{j}$. We then color $v$
with the same color that we used to color all vertices in $X_{j}$. This
completes the description of the construction of the coloring — note that at
this point, $U=\emptyset$.

To conclude, we count $k^{\prime}[\chi,Y]$, the number of happy vertices with
respect to the constructed coloring $c$. Let $k^{*}$ denote
$\max(k^{\prime}[\chi,Y])$, where the $\max$ is taken over all $\chi,S$ for
which there exists a valid coloring that respects $\chi,Y$. The algorithm
returns Yes if $k^{\star}\geq k$ and No otherwise.

Proof of Correctness. [Sketch.] Let $c^{*}$ be an arbitrary but fixed coloring
of $G$ that maxmizes the number of happy vertices. Let $\chi,S$ be the
behavior of $c^{*}$ with respect to $X$, that is, let $S$ be the set of happy
vertices in $X$ with respect to $c^{*}$, and let $\chi:=(X_{1},\ldots,X_{t})$
be a partition of $X$ based on the colors given by $c^{*}$. Let $c$ be the
coloring output by the algorithm when considering the behavior $(\chi,S)$.
Note that the algorithm does output some coloring based on the characterizing
nature of the conditions in $(\star)$.

It is easy to see that $c^{\star}$ and $c$ agree on the colors given in Phase
1 of the algorithm. Further, note that $c$ and $c^{\star}$ agree on the number
(and even the subset) of happy vertices in $X$. Also, among all uncolored
vertices of $V\setminus X$, all definitely unhappy vertices in $V\setminus X$
are not happy in $c^{\star}$, while all the vertices that are always happy are
happy in $c$. Among the precolored vertices in $V\setminus X$, it can be
verified that the maximum number of vertices that can be happy with respect to
any coloring that respects the behavior $(\chi,S)$ is precisely the weight of
the maximum matching obtained in Phase 2. Indeed, any such coloring is a
matching in this auxiliary graph, and the number of happy vertices corresponds
exactly to the weight of the matching. It follows that the number of happy
vertices in $c$ is at least the number of happy vertices in $c^{*}$.

Running Time Analysis. Trying all possible choices of $(\chi,S)$ requires time
proportional to $O((2d)^{d})$. For a fixed choice of $(\chi,S)$, all the three
phases of the algorithm are straightforward to implement in polynomial time. A
maximum matching can be computed in time $O(n+\sqrt{n}m)$ on bipartite graphs.

We now turn to the Max Happy Edges problem. Here the algorithm is considerably
simpler. Partition $E$ into two sets $E_{0}$ and $E_{1}$, where $E_{0}$ is the
set of all edges who have both their endpoints in $X$, and $E_{1}:=E\setminus
E_{0}$. We again guess the behavior of an optimal coloring in terms of how it
partitions $X$ into equivalence classes. For a fixed partition $\chi$, we
count all the happy edges in $E_{0}$ (note that this number does not depend on
what colors are given to the parts, but merely the fact that all vertices in a
part are equivalent).

Having fixed a partition, we force the colors of the parts that have
precolored vertices. Construct an auxiliary bipartite graph as we did in Phase
2 of the algorithm for Max Happy Vertices, with the only difference that now
the weight of the edge $(a_{i},b_{j})$ is based on the number of edges that
are made happy when all vertices $X_{i}$ are colored with color $j$. This
helps us determine a coloring of the vertices in $X$. Uncolored vertices in
$V\setminus X$ can now be colored greedily: for an uncolored vertex $v\in
V\setminus X$, let $d_{j}$ denote $|N(v)\cap X_{j}|$, for $1\leq j\leq t$.
Note that coloring $v$ with the same color as the one used on $\max(d_{j})$
makes $\max(d_{j})$ edges happy. The correctness of this approach follows from
the fact that this is the best we can hope for from a coloring that is
consistent with the behavior specified by $\chi$. ∎

######  Theorem 3.3.

Max Happy Vertices and Max Happy Edges are both $\sf{FPT}$ when parameterized
by the size of a clique modulator of the input graph.

###### Proof.

Let $(G,S,\ell,p,k)$ denote an instance of Max Happy Vertices. We will use $Q$
to refer to $V\setminus S$, the set of vertices that are not precolored by
$p$. Further, let $X\subseteq V$ such that $C=G\setminus X$ is a clique. We
use $d$ to denote $|X|$.

If $\ell>d+1$ then there exists at least two vertices $u$ and $v$ in $C$ such
that $p(u)\neq p(v)$, which implies no vertex of $C$ is happy. First we guess
the partition $(H,U)$ of $X$ in $O(2^{d})$ time, where $H$ and $U$ denotes the
happy and unhappy vertices of $X$ in optimal coloring $c$.

Let $H=(H_{1},\cdots,H_{t})$ be the partition of $H$ such that all vertices in
set $H_{i}$, $i\in[t]$, are colored with the same color by $c$. We can guess
the correct partition in $O(d^{d})$ time. Note that $N(H_{i})\cap
N(H_{j})=\emptyset$: suppose $v\in N(H_{i})\cap N(H_{j})$ then the color of
vertex $v$ is either different from $col(H_{i})$ or $col(H_{j})$ which is a
contradiction to the fact that all vertices in both $H_{i}$ and $H_{j}$ are
happy.

Since $H_{i}$ is happy there does not exist two vertices $u$ and $v$ in the
set $H_{i}\cup N(H_{i})$ such that $p(u)\neq p(v)$. For each $i\in[t]$, if at
least one vertex is precolored in $H_{i}\cup N(H_{i})$ then assign same color
to all vertices of $H_{i}\cup N(H_{i})$. For the sets $H_{i}\cup N(H_{i})$,
which do not have any precolored vertices, assign a color which is not used so
far to color any $H_{i}$. At the end arbitrarily color remaining vertices. For
each possible partition $H$ and $U$ of $X$ and each possible partition
$H_{1},\cdots,H_{t}$ of $H$, count the number of happy vertices and the
optimal coloring $c$ is the coloring which maximizes the number of happy
vertices.

If $\ell\leq d+1$ then some of the clique vertices can be happy, but this only
happens when all the clique vertices are colored by same color. Since there
are at most $\ell$ colors we can guess the correct coloring of the clique in
$O(\ell)$ time. Now it remained to color the set $X$, which can be done using
the procedure described in case of $l>d+1$.

We now turn to the Max Happy Edges problem. First we give a procedure to color
$X$ when all the vertices in clique $C=G\setminus X$ are precolored and no
vertex in $X$ is precolored. Let $X=(X_{1},\cdots,X_{t})$ be the partition of
$X$ such that all vertices in $X_{i}$ are colored in the same way by $c$.

Let $w[i,j]$ denote the number of edges in $G[X_{i}\cup C]$ that will be happy
if all vertices of $X_{i}$ are colored $j$. Consider an auxiliary weighted
bipartite graph, denoted by $D=((A,B),E)$ with edge weights given by
$w:E\rightarrow[|E|]$. This graph is constructed as follows. The vertex set
$A$ contains one vertex for every set $X_{i}$ and the vertex set $B$ contains
one vertex for every color used in clique. The weight of the edge
$(a_{i},b_{j})$ is simply $w[i,j]$. We find a matching $M$ of maximum weight
in $D$. It is easy to see that any such matching saturates $A$, since
$|B|\geq|A|$, the weights are positive, and all edges are present. We now
color all vertices in $X_{i}$ based on the matching $M$. In particular, if $M$
matches $a_{i}$ to $b_{j}$, then we color all vertices in $X_{i}$ with color
$j$. At the end of this phase, all vertices in $X$ have been colored. Now we
are ready to describe the general case. Let $C_{U}$ be the number of uncolored
vertices in clique. If $|C_{U}|\leq d+1$ then $X^{\prime}=X\cup C_{U}$ is a
vertex deletion distance to clique $C^{\prime}$ of size at most $2d+1$, i.e.,
$G\setminus(X\cup C_{U})$ is a clique. Since all the vertices of the clique
$G\setminus(X\cup C_{U})$ are precolored, The vertices of $X^{\prime}$ can be
colored using the procedure described above. So without loss of generality we
assume that $|C_{U}|>d+1$.

######  Lemma 1.

If $|C_{U}|=n_{1}>d+1$, then in any optimal coloring $c$ all non precolored
vertices in clique has to be colored with single color.

###### Proof.

Since $\ell$ colors are used in precoloring there exists a color class of size
at least $\lfloor\frac{n-n_{1}}{\ell}\rfloor$ in $C$. Assigning this color to
all vertices of $C_{U}$ maximizes the number of happy edges, since if we color
a vertex of $C_{U}$ with different color than others, then we loose at least
$d+1$ happy edges in clique $C_{U}$ and can make at most $d$ edges happy. ∎

The case when $\ell\leq d+1$ is easy, since we can guess optimal coloring of
$X$ in time $O(d^{d})$ and then it can be easily extended to color clique. If
$\ell>d+1$, From Lemma 1 we know that all vertices of $C_{U}$ gets same color,
we guess this color in $O(\ell)$ time. Now we need to color $X$ such that the
number of happy edges is maximized. This can be done by simply applying the
procedure describe in first case, where all vertices of clique are precolored.
The running time of the algorithm is $O(\ell(d^{d})(n+\sqrt{n}m)(n+m))$. ∎

###  3.3 The Standard Parameter

We finally show that Max Happy Edges is, in fact, $\sf{FPT}$ when
parameterized by the number of happy edges. Here we use the fact that if there
are enough edges both of whose endpoints are uncolored, then we have a Yes
instance right away. If not, the number of uncolored vertices can be shown to
be bounded, and since it is safe to delete edges among precolored vertices
(with some bookkeeping), the problem effectively reduces to the bounded vertex
cover number scenario.

######  Lemma 2.

Max Happy Edges is $\sf{FPT}$ when parameterized by $k$.

###### Proof.

Let $(G,S,\ell,p,k)$ be an instance of Max Happy Edges and let $Q$ be the set
of vertices that are not precolored by $p$. Without loss of generality, we
assume that no edge in $G[S]$ is happy, since if there are some happy edges in
$G[S]$ then we remove them from $G$ and reduce the value of $k$.

If the number of edges in graph $G[Q]$ is at least $k$ then the algorithm
returns Yes, since by coloring all vertices in $Q$ with same color we can make
at least $k$ edges happy.

If the number of vertices in $Q$ is at least $2k$ then the algorithm returns
Yes. We can make at least $k$ edges happy as follows. Let $Q_{1}=\\{x\in
Q~{}|~{}N(x)\cap S\neq\emptyset\\}$ and $Q_{2}=Q\setminus Q_{1}$. For all
$v\in Q_{1}$ color $v$ with one of its neighbors color. To color $Q_{2}$, we
repeat the following procedure untill all the vertices of $Q_{2}$ are colored.
For all $v\in Q_{2}$ which have colored neighbors in $Q_{1}$ assign one of its
neighbors color to $v$.

Therefore without loss of generality we assume $|Q|\leq 2k$. Since all the
edges in $G[S]$ are unhappy we can simply remove them from $G$. It is easy to
see that in the resulting graph the set $Q$ is a vertex cover of size at most
$2k$. Therefore the problem reduced to solving Max Happy Edges parameterized
by vertex cover number which can be solved using Theorem 3.2. ∎

######  Lemma 3.

Max Happy Vertices is $\sf{FPT}$ when parameterized by $k$ and $\ell$.

###### Proof.

Let $(G,S,\ell,p,k)$ denote an instance of Max Happy Vertices and let $Q$ be
the set of vertices that are not precolored by $p$. Let $S_{U}\subseteq S$ and
$Q_{U}\subseteq Q$ such that every vertex in $S_{U}\cup Q_{U}$ have at least
two neighbors with different colors. Let $S_{H}=S\setminus S_{U}$ and
$Q_{H}=Q\setminus Q_{U}$.

If the size of any color class in $S_{H}$ is at least $k$ then the algorithm
returns Yes. We can make at least $k$ vertices happy by coloring all neighbors
of vertices in this color class with same color. Therefore we assume that size
of each color class in $S_{H}$ is at most $k$, which implies size of $S_{H}$
is at most $\ell k$.

If the size of set $Q_{H}$ is at least $\ell k$ then the algorithm returns
Yes. There exists a subset $A$ of vertices of $Q_{H}$ of size at least $k$
such that each vertex of $A$ either has neighbors in same color class or has
no colored neighbors. By coloring all vertices of $A$ and its uncolored
neighbors with neighbors color we can make all vertices in $A$ happy.
Therefore we assume that size of $Q_{H}$ is less than $\ell k$.

It is easy to see that all vertices in $S_{U}\cup Q_{U}$ are unhappy,
therefore we can remove the edges between them. Then the set $S_{H}\cup Q_{H}$
forms a vertex cover of size at most $2\ell k$. Therefore the problem reduced
to solving Max Happy Vertices parameterized by vertex cover and number of
colors, which can be solved using Theorem 3.2. ∎

##  4 Special Graph Classes

######  Theorem 4.1.

Max Happy Vertices and Max Happy Edges are both NP-complete on the class of
bipartite and split graphs.

###### Proof.

The reductions for Max Happy Vertices follow by easy modifications of the
reduction in [10]. Here, therefore, we only state the proofs for Max Happy
Edges. We first consider the case of bipartite graphs. We reduce from Max
Happy Edges on general graphs.

We let $(G,\ell,S,p,k)$ be an instance of Max Happy Edges. Construct a
bipartite graph $(H=(A,B),E)$ as follows. For every vertex $v\in V(G)$, we
introduce a vertex $a_{v}\in A$. For every edge $e\in E(G)$, we introduce a
vertex $b_{e}\in B$, and if $e=(u,v)$, then $b_{e}$ is adjacent to $a_{u}$ and
$a_{v}$. The precoloring function $q$ mimics $p$ on $A$, that is, for every
$u\in S$, $q(a_{u})=p(u)$. We use $X$ to denote $\\{a_{u}~{}|~{}u\in
S\\}\subseteq A$. Let $k^{\prime}=m+k$. Thus our reduced instance is
$(H,\ell,X,q,k^{\prime})$.

We now argue the equivalence. First, consider the forward direction. If $c$ is
a total coloring of $V$ that makes $k$ edges happy, then we define a coloring
$c^{\prime}$ for $H$ as follows: color $c^{\prime}(a_{v}):=c(v)$ for all
$a_{v}\in A$. For every edge $e=(u,v)\in E$, color $b_{e}\in B$ according to
$c(u)$. Note that for all edges $e$ in $G$ that are happy with respect $c$,
two edges (namely $(b_{e},a_{v})$ and $(b_{e},a_{u})$) are happy with respect
to $c^{\prime}$. Corresponding to all unhappy edges, $H$ has one happy edge
with respect to $c^{\prime}$. Therefore, the total number of happy edges in
$c^{\prime}$ is $2k+(m-k)=m+k$.

In the reverse direction, let $c^{\prime}$ be a coloring of $H$ that makes at
least $m+k$ edges happy. Now consider the coloring $c$ obtained as follows:
$c(u)=c^{\prime}(a_{u})$. We argue that at least $k$ edges are happy in $G$
with respect to $c$. Indeed, suppose not. Without loss of generality, assume
that only $(k-1)$ edges are happy with respect to $c$. Then in $H$, there are
at most $(k-1)$ vertices in $B$ that can have two happy edges incident on
them, and therefore the total number of happy edges is at most
$2(k-1)+(m-k+1)=m+k-1$, which contradicts our assumption about the total
number of happy edges in $H$ with respect to $c^{\prime}$.

We now turn to the case of split graphs. The construction is similar to the
case of bipartite graphs. Construct a split graph $(H=(A,B),E)$ as follows.
Let $(G,\ell,S,p,k)$ be an instance of Max Happy Edges. Let $T:={m\choose
2}+1$. For every vertex $v\in V(G)$, we introduce $T$ copies of the vertex
$a_{v}\in A$, denoted by $a_{v}[1],\ldots,a_{v}[T]$. For every edge $e\in
E(G)$, we introduce a vertex $b_{e}\in B$, and if $e=(u,v)$, then $b_{e}$ is
adjacent to all copies of $a_{u}$ and $a_{v}$. Finally, we add all edges among
vertices in $B$, thereby making $H[B]$ a clique.

The precoloring function $q$ mimics $p$ on $A$ across all copies, that is, for
every $u\in S$, $q(a_{u})=p(u)$ for all copies of $a_{u}$. We use $X$ to
denote $\\{a_{u}~{}|~{}u\in S\\}\subseteq A$. Let $k^{\prime}=T(m+k)$. Thus
our reduced instance is $(H,\ell,X,q,k^{\prime})$.

We now argue the equivalence of these instances. First, consider the forward
direction. If $c$ is a total coloring of $V$ that makes $k$ edges happy, then
we define a coloring $c^{\prime}$ for $H$ as follows: color
$c^{\prime}(a_{v}):=c(v)$ for all copies of $a_{v}\in A$. For every edge
$e=(u,v)\in E$, color $b_{e}\in B$ according to $c(u)$. Note that for all
edges $e$ in $G$ that are happy with respect $c$, $2T$ edges (namely
$(b_{e},a_{v})$ and $(b_{e},a_{u})$ across all copies) are happy with respect
to $c^{\prime}$. Corresponding to all unhappy edges, $H$ has $T$ happy edges
with respect to $c^{\prime}$. Therefore, the total number of happy edges in
$c^{\prime}$ is at least $2Tk+T\cdot(m-k)=T\cdot(m+k)$.

In the reverse direction, , let $c^{\prime}$ be a coloring of $H$ that makes
at least $T(m+k)$ edges happy. We argue that there must be at least one copy
$A_{i}$ of $\\{a_{v}~{}|~{}v\in V\\}$ for which the number of happy edges with
one endpoint in $B$ and one in $A_{i}$ is at least $(m+k)$. Indeed, suppose
not. Then consider the following partition of the edges in $H$: let $E_{0}$ be
all edges with both endpoints in $B$, and let $E_{i}$ be all edges with one
endpoint in $B$ and the other endpoint in the $i^{th}$ copy of the vertices
$\\{a_{v}~{}|~{}v\in V\\}$. For the sake of contradiction, we have assumed
that the number of happy edges in $E_{i}$ is less than $(m+k)$ for all
$i\in[T]$. Note that the total number of edges in $B$ is ${m\choose 2}$.
Therefore, the the number of edges happy with respect to $c^{\prime}$ is at
most:

${m\choose 2}+T\cdot(m+k-1)=T\cdot(m+k)+{m\choose 2}-T<T(m+k),$

where the last step follows by substituting for $T={m\choose 2}+1$. This leads
to the desired contradiction.

Having identified one set $E_{i}$ that has at least $(m+k)$ happy edges, the
argument for recovering a coloring $c$ for $G$ that makes at least $k$ edges
happy is identical to the case of bipartite graphs. ∎

We now turn to the Max Happy Vertices problem on the class of cographs. We use
the notion of modular decomposition to solve this problem on cographs.

A set $M\subseteq V(G)$ is called module of $G$ if all vertices of $M$ have
the same set of neighbors in $V(G)\setminus M$. The _trivial modules_ are
$V(G)$, and $\\{v\\}$ for all $v$. A prime graph is a graph in which all
modules are trivial. The modular decomposition of a graph is one of the
decomposition techniques which was introduced by Gallai [8]. The modular
decomposition of a graph $G$ is a rooted tree $M_{G}$ that has the following
properties:

  1. 1.

The leaves of $M_{G}$ are the vertices of $G$.

  2. 2.

For an internal node $h$ of $M_{G}$, let $M(h)$ be the set of vertices of $G$
that are leaves of the subtree of $M_{G}$ rooted at $h$. ($M(h)$ forms a
module in $G$).

  3. 3.

For each internal node $h$ of $M_{G}$ there is a graph $G_{h}$
(_representative graph_) with $V(G_{h})=\\{h_{1},h_{2},\cdots,h_{r}\\}$, where
$h_{1},h_{2},\cdots,h_{r}$ are the children of $h$ in $M_{G}$ and for $1\leq
i<j\leq r$, $h_{i}$ and $h_{j}$ are adjacent in $G_{h}$ iff there are vertices
$u\in M(h_{i})$ and $v\in M(h_{j})$ that are adjacent in $G$.

  4. 4.

$G_{h}$ is either a clique, an independent set, or a prime graph and $h$ is
labeled _Series_ if $G_{h}$ is clique, _Parallel_ if $G_{h}$ is an independent
set, and _Prime_ otherwise.

James et al. [9] gave first polynomial time algorithm for modular
decomposition which runs in $O(n^{4})$ time.

######  Theorem 4.2.

Max Happy Vertices is polynomial time solvable on the class of cographs.

###### Proof.

The modular decomposition tree of cographs has only parallel and series nodes.
Let $G$ be a cograph whose modular decomposition tree is $M_{G}$. Without loss
of generality we assume that the root $r$ of tree $M_{G}$ is a series node,
otherwise $G$ is not connected and the number of happy vertices in $G$ is
equals to the sum of the happy vertices in each connected component. Let the
children of $r$ be $x$ and $y$. Further, let the cographs corresponding to the
subtrees at $x$ and $y$ be $G_{x}$ and $G_{y}$.

We assume that $\ell\geq 3$, otherwise we use the polynomial time algorithm of
$2$-MHV problem on general graphs to find the number of maximum happy
vertices. We assume that both $G_{x}$ and $G_{y}$ contains at least two
vertices. Suppose, if $G_{x}$ has only vertex $v$, then $v$ is the universal
(adjacent to all vertices) vertex in $G$. It is easy to see that in any
optimal coloring $c$ of $G$, if a vertex $u$ is happy then $c(u)=c(v)$ i.e, in
any optimal coloring all happy vertices are colored with color of $v$. We can
guess the color of $v$ in $O(\ell)$ time.

We have the following three cases based on the number of colors present in
$G_{x}$ and $G_{y}$ in the partial coloring $c$ of $G$.

Number of colors in $G_{x}$ is zero. Let $\ell\geq 3$ be the number of colors
used in $G_{y}$ by $c$. It is easy to see that no vertex of $G_{x}$ is happy
as each vertex of $G_{x}$ is adjacent to at least two vertices of different
colors. Moreover all the vertices in $G_{x}$ need to be colored with a single
color otherwise the number of happy vertices becomes zero. We try over all
possible $O(\ell)$ many ways of coloring $G_{x}$. In the end color all
uncolored vertices in $G_{y}$ with the color used in $G_{x}$.

Number of colors in $G_{x}$ is one. Since $\ell\geq 3$, the number of colors
(distinct from the color used in $G_{x}$) used in $G_{y}$ by $c$ is at least
two. The optimal coloring is to color all the uncolored vertices of $G$ with
color used in $G_{x}$.

Number of colors in $G_{x}$ is at least two. We assume that the number of
colors in $G_{y}$ is at least two, otherwise we can use one of the above two
cases by interchanging $G_{x}$ and $G_{y}$. In this case no vertex in $G$ is
happy, because every vertex of $G$ is adjacent to at least two precolored
vertices having different colors. ∎

##  5 Conclusion

In this paper, we study the Max Happy Vertices and Max Happy Edges problems
from the parameterized perspective. We showed that

  * •

Both the problems are $\sf{FPT}$ with respect to the strutural parameters (a)
Vertex cover (b) Distance to clique

  * •

Max Happy Edges is $\sf{FPT}$ when parameterized by number of happy edges in
solution (standard parameter) and Max Happy Vertices is $\sf{FPT}$ when
parameterized by number of happy vertices in the solution and the number of
colors.

  * •

Both Max Happy Vertices and Max Happy Edges are $\sf{NP}$-hard on split graphs
and bipartite graphs and Max Happy Vertices is polynomially solvable on
cographs

The following are some interesting open problems.

  * •

Are Max Happy Vertices and Max Happy Edges are $\sf{FPT}$ when parameterized
by the cluster vertex deletion number.

  * •

Does Max Happy Vertices and Max Happy Edges problems admit polynomial kernels
when parameterized by (a) Vertex cover (b) Distance to clique.

## References

  * [1] Agrawal, A.: On the parameterized complexity of happy vertex coloring. In: International Workshop on Combinatorial Algorithms. In Press, Springer (2017)
  * [2] Aravind, N., Kalyanasundaram, S., Kare, A.S.: Linear time algorithms for happy vertex coloring problems for trees. In: International Workshop on Combinatorial Algorithms. pp. 281–292. Springer (2016)
  * [3] Aravind, N., Kalyanasundaram, S., Kare, A.S., Lauri, J.: Algorithms and hardness results for happy coloring problems. arXiv preprint arXiv:1705.08282 (2017)
  * [4] Courcelle, B.: Graph rewriting: An algebraic and logic approach. Handbook of theoretical computer science pp. 194–242 (1990)
  * [5] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)
  * [6] Diestel, R.: Graph Theory. Springer Graduate Text GTM 173, Reinhard Diestel (Jul 2012)
  * [7] Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity, vol. 4. Springer (2013)
  * [8] Gallai, T.: Transitiv orientierbare graphen. Acta Mathematica Hungarica 18(1), 25–66 (1967)
  * [9] James, L.O., Stanton, R.G., Cowan, D.D.: Graph decomposition for undirected graphs. In: Proceedings of $3^{rd}$ Southeastern Conference on Combinatorics, Graph Theory, and Computing. pp. 281–290 (1972)
  * [10] Zhang, P., Li, A.: Algorithmic aspects of homophyly of networks. Theoretical Computer Science 593, 117–131 (2015)


# Colorful Intersections and Tverberg Partitions

Michael Gene Dobbins ∗ ,  Andreas F. Holmsen$\hskip 0.85355pt{}^{\dagger}$ and
Dohyeon Lee$\hskip 0.85355pt{}^{\dagger}$

###### Abstract.

The colorful Helly theorem and Tverberg’s theorem are fundamental results in
discrete geometry. We prove a theorem which interpolates between the two. In
particular, we show the following for any integers $d\geq m\geq 1$ and $k$ a
prime power. Suppose $F_{1},F_{2},\dots,F_{m}$ are families of convex sets in
$\mathbb{R}^{d}$, each of size $n>(\frac{d}{m}+1)(k-1)$, such that for any
choice $C_{i}\in F_{i}$ we have $\bigcap_{i=1}^{m}C_{i}\neq\emptyset$. Then,
one of the families $F_{i}$ admits a Tverberg $k$-partition. That is, one of
the $F_{i}$ can be partitioned into $k$ nonempty parts such that the convex
hulls of the parts have nonempty intersection. As a corollary, we also obtain
a result concerning $r$-dimensional transversals to families of convex sets in
$\mathbb{R}^{d}$ that satisfy the colorful Helly hypothesis, which extends the
work of Karasev and Montejano.

###### Key words and phrases:

Tverberg’s theorem, geometric transversals, topological combinatorics,
configuration space/test map, discrete Morse theory

∗ Department of Mathematics and Statistics, Binghamton University, Binghamton,
New York, USA. Support from KAIST Advanced Institute for Science-X (KAI-X)

† Department of Mathematical Sciences, KAIST, Daejeon, South Korea and
Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South
Korea. Supported by the Institute for Basic Science (IBS-R029-C1)

Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
##  1\. Introduction

###  1.1. Background

A $k$-partition of a finite set $X$ is an ordered partition of $X$ into
$k$-nonempty parts, that is, a $k$-tuple

$(X_{1},X_{2},\dots,X_{k}),$

such that $X=X_{1}\cup X_{2}\cup\cdots\cup X_{k}$ and $X_{i}\neq\emptyset$ for
all $i$. If the elements of $X$ are points (or convex sets) in
$\mathbb{R}^{d}$, a $k$-partition of $X$, $(X_{1},X_{2},\dots,X_{k})$, is
called a Tverberg $k$-partition provided that

$(\operatorname{conv}\>X_{1})\cap(\operatorname{conv}\>X_{2})\cap\cdots\cap(\operatorname{conv}\>X_{k})\neq\emptyset.$

A fundamental result of discrete geometry is the celebrated theorem of
Tverberg [17], which asserts that if $|X|>(d+1)(k-1)$, then $X$ admits a
Tverberg $k$-partition.

Let $F_{1},F_{2},\dots,F_{m}$ be families of sets. We say that
$F_{1},F_{2},\dots,F_{m}$ satisfy the colorful intersection property if

$C_{1}\cap C_{2}\cap\cdots\cap C_{m}\neq\emptyset$

for every choice $C_{1}\in F_{1},C_{2}\in F_{2},\dots,C_{m}\in F_{m}$.

Another fundamental result of discrete geometry is the colorful Helly theorem
[1]. It asserts that if $F_{1},F_{2},\dots,F_{d+1}$ are finite families of
convex sets in $\mathbb{R}^{d}$ that satisfy the colorful intersection
property, then there is a point in common to every member of one of the
families. Observe that it is no loss in generality to assume that $|F_{i}|=n$
for all $i$, in which case the conclusion asserts (in our terminology) that
one of the $F_{i}$ admits a Tverberg $n$-partition.

Tverberg’s theorem and the colorful Helly theorem have both played important
roles in the development of discrete geometry, and there are a number of
generalizations and extensions. For further information on the subject, we
suggest the reader consult [2, 3, 5, 6, 8, 12] and the references therein.

In the last decade, a particular intriguing question related to the colorful
Helly theorem has been under investigation: What conclusions (if any) can be
drawn if we are given fewer than $d+1$ families of convex sets in
$\mathbb{R}^{d}$ which satisfy the colorful intersection property? See [15,
11, 14] for some answers to this question, as well as [11, Conjecture 1] and
[3, Problems 8.1 and 8.2].

###  1.2. Main results

Our main result can be viewed as an interpolation between the colorful Helly
theorem and Tverberg’s theorem.

######  Theorem 1.1.

Given integers $d\geq m\geq 1$ and $k$ a prime power. Suppose
$F_{1},F_{2},\dots,F_{m}$ are families of convex sets in $\mathbb{R}^{d}$,
with $|F_{i}|=n>(\frac{d}{m}+1)(k-1)$, that satisfy the colorful intersection
property. Then one of the $F_{i}$ admits a Tverberg $k$-partition.

######  Remark 1.2.

Note that for $m=d$, our theorem follows immediately from the colorful Helly
theorem. First project the sets into a hyperplane and apply the colorful Helly
theorem. There is a point in common to all the members of one of the projected
families, and the preimage of this point is a line that intersects all the
members of one of the $F_{i}$. Now, just apply Tverberg’s theorem within this
line.

For smaller $m$ this argument becomes generally less effective. Projecting
into an $(m-1)$-flat and applying the colorful Helly theorem would give a
$(d-m+1)$-flat transversal to one of the families $F_{i}$, but to obtain a
Tverberg $k$-partition within this $(d-m+1)$-flat would require
$|F_{i}|>(d-m+2)(k-1)$, which is significantly worse than the size of $F_{i}$
that we require in Theorem 1.1.

######  Remark 1.3.

Whenever $d$ is a multiple of $m$, our theorem is optimal with respect to the
size of the families. Indeed, consider the following construction in
$\mathbb{R}^{d}=\mathbb{R}^{t}\times\mathbb{R}^{t}\times\cdots\times\mathbb{R}^{t}$
with $m$ copies of $\mathbb{R}^{t}$, where $t=\frac{d}{m}$. Let
$X\subset\mathbb{R}^{t}$ be a set of $(t+1)(k-1)$ points which does not admit
a Tverberg $k$-partition, and for $1\leq i\leq m$ define the family

$F_{i}:=\big{\\{}\mathbb{R}^{t}\times\cdots\times\mathbb{R}^{t}\times\underset{i\text{th
factor}}{\\{x\\}}\times\mathbb{R}^{t}\times\cdots\times\mathbb{R}^{t}:x\in
X\big{\\}}.$

Observe that these families satisfy the colorful intersection property, but
none of them has a Tverberg $k$-partition.

######  Remark 1.4.

The prime power assumption in our Theorem 1.1 appears to be just an artifact
of our proof method, and we conjecture that the theorem also holds when $k$ is
any positive integer.

Another interesting instance that our proof method falls short of would be to
generalize Theorem 1.1 to the case where the $F_{i}$ may have distinct sizes
and we ask for one of the $F_{i}$ to admit a Tverberg $k_{i}$-partition. We
leave it to the reader’s imagination to formulate (and prove) such a
conjecture.

###  1.3. An application to geometric transversals

Some of the earliest results dealing with the colorful intersection property
for less than $d+1$ families of convex sets in $\mathbb{R}^{d}$ are the
transversal theorems of Karasev and Montejano [15, 14]. The simplest case
asserts: Given three red convex and three blue convex sets in
$\mathbb{R}^{3}$, where each red set intersects each blue set, then there is a
line that intersects every red set or a line that intersects every blue set.
More generally, we have the following

######  Corollary 1.5.

Let $F_{1},F_{2},\dots,F_{m}$ be families of convex sets in $\mathbb{R}^{d}$,
each of size $k+r$, satisfying the colorful intersection property, where $k$
is a prime power. If $d<\frac{(r+1)m}{k-1}$, then one of the $F_{i}$ have an
$r$-dimensional affine flat transversal.

###### Proof.

Theorem 1.1 implies that one of the $F_{i}$ admits a Tverberg $k$-partition.
That is, for $F_{i}=\\{C_{1},C_{2},\dots,C_{k+r}\\}$, there is a $k$-partition
$(X_{1},X_{2},\dots,X_{k})$ of $[k+r]$ and a point $x\in\mathbb{R}^{d}$ such
that $x\in\operatorname{conv}\big{(}\bigcup_{i\in X_{j}}C_{i}\big{)}$ for
every $1\leq j\leq k$. This means that we can choose a point $x_{i}\in C_{i}$,
for every $1\leq i\leq k+r$, such that
$x\in\operatorname{conv}\\{x_{i}\\}_{i\in X_{j}}$ for every $1\leq j\leq k$.
Let $A_{j}$ denote the affine hull of $\\{x_{i}\\}_{i\in X_{j}}$, and let $A$
be the affine hull of $A_{1}\cup A_{2}\cup\cdots\cup A_{k}$. Then $x\in
A_{1}\cap A_{2}\cap\cdots\cap A_{k}$, and so

$\dim A\leq\sum_{j=1}^{k}\dim A_{j}=\sum_{j=1}^{k}(|X_{j}|-1)=r.$

Since $x_{i}\in A$ for every $1\leq i\leq k+r$, it follows that $A$ is an
affine flat of dimension at most $r$ that intersects every $C_{i}$. ∎

######  Remark 1.6.

We note that the work of Karasev and Montejano deals with the cases $k=2$ [15,
Theorem 8] and $k=m$ [15, Corollary 7], but without any primality condition on
$m$. For $k=2$, their theorem requires $d<r+m+1$, while Corollary 1.5 allows
for $d<(r+1)m$. However, for the case $k=m$, their theorem requires
$d<(\frac{r}{m-1}+1)m$ which is slightly better than our bound
$d<(\frac{r+1}{m-1})m$ given by Corollary 1.5.

######  Remark 1.7.

The work of Karasev and Montejano makes use of Schubert calculus and the
Lusternik–Schnirelmann category of the Grassmannian. In contrast, our proof
uses a combination of the configuration space / test map scheme from
topological combinatorics (see e.g. [13]) and Sarkaria’s tensor method from
discrete geometry (see e.g. [12, section 8.3]). The latter appear more
frequently in discrete and computational geometry literature, so we expect
these methods to attract broader interest from the community.

##  2\. Proof of Theorem 1.1

We will show that a hypothetical counter-example to Theorem 1.1 would
contradict the following

######  Theorem (Volovikov [18]).

Let $G=\mathbb{Z}_{p}\times\mathbb{Z}_{p}\times\cdots\times\mathbb{Z}_{p}$ be
the product of finitely many copies, with $p$ prime. Let $X$ and $Y$ be fixed
point free $G$-spaces, where $X$ is $n$-connected and $Y$ is finite
dimensional and homotopy equivalent to $S^{n}$. Then there is no
$G$-equivariant map $X\to Y$.

To reach a contradiction, we use Sarkaria’s tensor method to get geometric
criteria for the existence of a Tverberg $k$-partition, which we then use to
construct such an equivariant map. We then use discrete Morse theory to show
that the domain of this map is sufficiently connected to violate Volovikov’s
theorem.

###  2.1. The configuration space $K_{n,k}^{*m}$

Given integers $n>k\geq 1$, we let $V_{n,k}$ denote the set of surjective maps

$\varphi:[n]\to[k].$

Note that we can equivalently think of $V_{n,k}$ as the set of $k$-partitions
on $[n]$

$\big{(}\varphi^{-1}(1),\dots,\varphi^{-1}(k)\big{)}.$

For a family of sets $F=\\{C_{1},\dots,C_{n}\\}$ and $\varphi\in V_{n,k}$, we
write $\varphi F$ to denote the $k$-partition

$\big{(}F^{(1)},\dots,F^{(k)}\big{)}$

where $F^{(i)}=\\{C_{j}\;:\;j\in\varphi^{-1}(i)\\}$.

We define $K_{n,k}$ to be the simplicial complex on the vertex set $V_{n,k}$
whose faces consists of subsets
$\sigma=\\{\varphi_{1},\dots,\varphi_{r}\\}\subset V_{n,k}$ such that

(1) $X_{i}=\varphi_{1}^{-1}(i)\cap\cdots\cap\varphi_{r}^{-1}(i)\neq\emptyset$

for every $i\in[k]$. Note that the facets of $K_{n,k}$ correspond to a choice
of representative from each part of a $k$-partition, and the vertices of a
facet correspond to all the ways of extending this choice of representatives
to a $k$-partition.

The symmetric group $S_{k}$ acts (freely) on $V_{n,k}$ by permuting the parts
of the partition. That is, for $g\in S_{k}$ and
$\varphi=\big{(}\varphi^{-1}(1),\dots,\varphi^{-1}(k)\big{)}\in V_{n,k}$ we
have

$g\varphi=\big{(}\varphi^{-1}(g(1)),\dots,\varphi^{-1}(g(k))\big{)},$

which means that $S_{k}$ acts freely on $K_{n,k}$.

In order to apply Volovikov’s theorem, we need a lower bound on the
connectedness of $K_{n,k}$. This is given by

######  Lemma 2.1.

For all $n>k\geq 1$, the simplicial complex $K_{n,k}$ is $(n-k-1)$-connected.

We give the proof of this lemma in section 3. For now we proceed with the
proof of Theorem 1.1 assuming the bound on the connectedness of $K_{n,k}$. We
will construct an equivariant map on the $m$-fold join
$K_{n,k}^{*m}=K_{n,k}*\dots*K_{n,k}$.

###  2.2. Sarkaria’s criterion

Here we demonstrate one of the standard methods for proving Tverberg’s
theorem, Sarkaria’s tensor method. The method is usually applied for
collections of points, but here we apply it to families of convex sets,
similar to the approach taken in [16].

For each $i\in[k]$, define the vector $v_{i}\in\mathbb{R}^{k}$ as

$v_{i}=e_{i}-\textstyle{\frac{1}{k}}\mathbf{1},$

where $e_{i}$ is the $i$th standard unit vector and
$\mathbf{1}=(1,\dots,1)\in\mathbb{R}^{k}$. Observe that the $v_{i}$ satisfy
only one linear dependency up to a scalar multiple, which is

(2) $v_{1}+\cdots+v_{k}=0.$

Next, define the map

$\begin{array}[]{cccc}L_{i}:&\mathbb{R}^{d}&\to&\mathbb{R}^{(d+1)\times k}\\\
&x&\mapsto&\bigl{[}\\!\begin{smallmatrix}x\\\
1\end{smallmatrix}\\!\bigr{]}\otimes v_{i}\end{array}$

where $\bigl{[}\\!\begin{smallmatrix}x\\\ 1\end{smallmatrix}\\!\bigr{]}$
denotes the vector in $\mathbb{R}^{d+1}$ obtained from $x$ by appending an
additional coordinate and setting this equal to 1. For a given
$x\in\mathbb{R}^{d}$, we will regard the image $L_{i}(x)$ as a $(d+1)\times k$
matrix. Observe that since each $v_{i}$ is orthogonal to
$\mathbf{1}\in\mathbb{R}^{k}$, it follows that $L_{i}(x)$ belongs to the
subspace

$Y=\\{\>[w_{1}\;\cdots\;w_{k}]\>:\>w_{1}+\dots+w_{k}=\mathbf{0}\\}\subset\mathbb{R}^{(d+1)\times
k}.$

We note that the symmetric group $S_{k}$ acts on the subspace $Y$ by permuting
the columns, and for $g\in S_{k}$ and $L_{i}(x)\in Y$, we have

$gL_{i}(x)=g(\textstyle\bigl{[}\\!\begin{smallmatrix}x\\\
1\end{smallmatrix}\\!\bigr{]}\otimes
v_{i})=\textstyle\bigl{[}\\!\begin{smallmatrix}x\\\
1\end{smallmatrix}\\!\bigr{]}\otimes v_{g(i)}=L_{g(i)}(x).$

Observe that the action is not free, but it is fixed-point free on
$Y\setminus\\{0\\}$.

For a convex set $C\subset\mathbb{R}^{d}$, we write $L_{i}C$ to denote the set

$L_{i}C=\\{L_{i}(x)\;:\;x\in C\\},$

which is a convex subset of $Y$. The crucial step of the Sarkaria method is
the following

######  Observation 2.2.

Let $F=\\{C_{1},\dots,C_{n}\\}$ be a family of convex sets in $\mathbb{R}^{d}$
and $\varphi\in V_{n,k}$. If

$0\in\text{\em conv}\left(L_{\varphi(1)}C_{1}\cup\cdots\cup
L_{\varphi(n)}C_{n}\right),$

then $\varphi F$ is a Tverberg $k$-partition.

Indeed, suppose $0=\alpha_{1}L_{1}(x_{1})+\cdots+\alpha_{k}L_{k}(x_{k})$ is a
convex combination, where

$L_{i}(x_{i})=\textstyle{\bigl{[}\\!\begin{smallmatrix}x_{i}\\\
1\end{smallmatrix}\\!\bigr{]}}\otimes
v_{i}\in\operatorname{conv}\left(\bigcup_{j\in\varphi^{-1}(i)}L_{i}C_{j}\right).$

Then in each coordinate, the $\alpha_{i}\bigl{[}\\!\begin{smallmatrix}x_{i}\\\
1\end{smallmatrix}\\!\bigr{]}$ are the coefficients of a linear dependency of
the $v_{i}$, and since (2) is the unique linear dependency up to scalar
multiple, we have

$\alpha_{1}=\cdots=\alpha_{k}\;\;\;\text{ and }\;\;\;x_{1}=\cdots=x_{k}.$

We also have
$x_{i}\in\operatorname{conv}\left(\bigcup_{j\in\varphi^{-1}(i)}C_{j}\right)$,
so $\varphi F$ is a Tverberg $k$-partition.

###  2.3. The test map $f$

Consider a single family $F_{1}=\\{C_{1},\dots,C_{n}\\}$ of compact convex
sets in $\mathbb{R}^{d}$ which does not have a Tverberg $k$-partition. We show
how this gives us an equivariant map

$f_{1}:K_{n,k}\to Y.$

For $\varphi\in V_{n,k}$, consider the $k$-partition $\varphi F_{1}$. By
hypothesis, this is not a Tverberg $k$-partition, so by Observation 2.2, there
is a vector $a_{\varphi}\in Y$ which defines an open halfspace

$H_{\varphi}=\\{y\in Y:a_{\varphi}\cdot y>0\\}$

such that

(3) $L_{\varphi(1)}C_{1}\cup\cdots\cup L_{\varphi(n)}C_{n}\subset
H_{\varphi}.$

It is important that the vectors $a_{\varphi}$ are chosen such that

$ga_{\varphi}=a_{g\varphi}$

for every $g\in S_{k}$. This can be done by first choosing one vector
$a_{\varphi}$ in each $S_{k}$ orbit, and then allowing the rest of the vectors
in that orbit to be defined accordingly.

To verify that such a choice is valid, suppose that $a_{\varphi}$ has been
chosen such that the containment (3) holds and consider $g\in S_{k}$. Since
$gL_{i}(x)=L_{g(i)}(x)$, we get

$\begin{array}[]{rclcl}L_{g\varphi(i)}C_{i}&=&g(L_{\varphi(i)}C_{i})&\subset&g(H_{\varphi})\\\
&&&=&\\{g(y):a_{\varphi}\cdot y>0\\}\\\ &&&=&\\{z:a_{\varphi}\cdot
g^{-1}(z)>0\\}\\\ &&&=&\\{z:ga_{\varphi}\cdot z>0\\}\\\
&&&=&\\{z:a_{g\varphi}\cdot z>0\\}=H_{g\varphi}.\end{array}$

The equivariant map $f_{1}:K_{n,k}\to Y$ is defined by affine extension of
$a_{\bullet}$ by setting

$f_{1}(\sigma)=\operatorname{conv}\\{a_{\varphi}:\varphi\in\sigma\\},$

for every face $\sigma\in K_{n,k}$.

Now consider the setting of Theorem 1.1 where we have families
$F_{1},\dots,F_{m}$ of compact convex sets in $\mathbb{R}^{d}$, each of size
$n$, and suppose none of them have a Tverberg $k$-partition. For every $1\leq
i\leq m$, the family $F_{i}$ gives us an equivariant map $f_{i}:K_{n,k}\to Y$
as defined above. By taking joins, we get an equivariant map

$f=f_{1}*f_{2}*\cdots*f_{m}:K_{n,k}^{*m}\to Y.$

(Note that the symmetric group $S_{k}$ acts freely on $K^{*m}_{n,k}$ by
applying the group action to each component of the join.)

###  2.4. Using colorful intersections to avoid a subspace

We now want to determine the range of $f$, and for this we use the assumption
that the families $F_{i}$ satisfy the colorful intersection property.

First we note that the facets of $K_{n,k}$ are in one-to-one correspondence
with injective functions

$\rho:[k]\to[n].$

In particular, each facet $\sigma\in K_{n,k}$ corresponds to the unique
injection $\rho:[k]\to[n]$ that has $\sigma$ as its set of left inverses. That
is,

$\varphi\in\sigma\iff\varphi\circ\rho=\text{id}_{[k]}.$

Consider a facet $\sigma=\sigma_{1}*\sigma_{2}*\cdots*\sigma_{m}\in
K^{*m}_{n,k}$ with the corresponding injections $\rho_{i}$ satisfying
$\varphi\circ\rho_{i}=\text{id}_{[k]}$ for all $\varphi\in\sigma_{i}$. For
each $1\leq i\leq m$, we apply $\rho_{i}$ to select a $k$-tuple of distinct
convex sets

$C^{(i)}_{\rho_{i}(1)},C^{(i)}_{\rho_{i}(2)},\dots,C^{(i)}_{\rho_{i}(k)}\in
F_{i}.$

The colorful intersection property now guarantees that, for every $1\leq j\leq
k$, we can select a point $x_{j}\in\mathbb{R}^{d}$ which satisfies

$x_{j}\in C^{(1)}_{\rho_{1}(j)}\cap C^{(2)}_{\rho_{2}(j)}\cap\cdots\cap
C^{(m)}_{\rho_{m}(j)}.$

Now consider a vertex $\varphi\in\sigma_{i}$ and the halfspace
$H_{\varphi}=\\{y\in Y:a_{\varphi}\cdot y>0\\}$ from the definition of the
test map $f$. Since $\varphi\circ\rho_{i}=\text{id}_{[k]}$, we get

$L_{1}C^{(i)}_{\rho_{i}(1)}\cup L_{2}C^{(i)}_{\rho_{i}(2)}\cup\cdots\cup
L_{k}C^{(i)}_{\rho_{i}(k)}\subset H_{\varphi},$

by the containment (3), which in turn implies

$\big{\\{}L_{1}(x_{1}),L_{2}(x_{2}),\dots,L_{k}(x_{k})\big{\\}}\subset
H_{\varphi}.$

Thus, for every vertex $\varphi\in\sigma$ and every $1\leq j\leq k$, we have
$a_{\varphi}\cdot L_{j}(x_{j})>0$, which gives us

(4)
$f(\sigma)=\operatorname{conv}\\{a_{\varphi}:\varphi\in\sigma\\}\subset\\{y\in
Y:L_{j}(x_{j})\cdot y>0\\}.$

We claim that $f(\sigma)$ does not intersect the subspace

$B:=e_{d+1}\otimes\mathbb{R}^{k}.$

For the sake of contradiction, suppose there were a vector
$c=(c_{1},c_{2},\dots,c_{k})\in\mathbb{R}^{k}$ such that

$b=e_{d+1}\otimes c\in f(\sigma)\cap B.$

Let $j\in[k]$ be a coordinate such that $c_{j}$ is minimized. Then

$v_{j}\cdot c=\textstyle\frac{k-1}{k}c_{j}-\frac{1}{k}\sum_{i\neq j}c_{i}\leq
0,$

and so

$\textstyle L_{j}(x_{j})\cdot b=\left(\bigl{[}\\!\begin{smallmatrix}x_{j}\\\
1\end{smallmatrix}\\!\bigr{]}\otimes v_{j}\right)\cdot\left(e_{d+1}\otimes
c\right)=\left(\bigl{[}\\!\begin{smallmatrix}x_{j}\\\
1\end{smallmatrix}\\!\bigr{]}\cdot e_{d+1}\right)\left(v_{j}\cdot c\right)\leq
0,$

but $L_{j}(x_{j})\cdot b>0$ by (4) since $b\in f(\sigma)$, so $f(\sigma)$
cannot intersect $B$.

We conclude that the range of $f$ is contained in $Y\setminus B$, so we have
an equivariant map

$f:K^{*m}_{n,k}\to Y\setminus B.$

###  2.5. Finishing the proof

By Lemma 2.1, it follows that the complex $K^{*m}_{n,k}$ is
$(m(n-k+1)-2)$-connected (see e.g. [13, Proposition 4.4.3]), and since
$n>(\frac{d}{m}+1)(k-1)$, we get

$m(n-k+1)-2>d(k-1)-2.$

Therefore $K^{*m}_{n,k}$ is at least $(d(k-1)-1)$-connected.

The symmetric group $S_{k}$ acts on $Y\setminus B$ by permuting columns, which
makes it a fixed-point free action. If $k=p^{r}$, then the action is also
fixed-point free with respect to the subgroup
$G=\mathbb{Z}_{p}\times\mathbb{Z}_{p}\times\cdots\times\mathbb{Z}_{p}$. The
subspace $Y\cap B^{\perp}$ has dimension $d(k-1)$ as it consists of the
matrices in $Y$ whose $(d+1)$st row is equal to the 0-vector, and therefore
$Y\setminus B$ is homotopy equivalent to $S^{d(k-1)-1}$. Consequently, the
existence of the map $f$ contradicts Volovikov’s theorem. ∎

##  3\. Proof of Lemma 2.1

Here we show that the simplicial complex $K_{n,k}$ is $(n-k-1)$-connected. The
proof is in two steps. First we define a polyhedral complex $C_{n,k}$ whose
cells correspond to partial surjective functions $\pi:[n]\to[k]$, and use
Quillen’s fiber lemma to show that $C_{n,k}$ is homotopy equivalent to
$K_{n,k}$. We then bound the connectedness of $C_{n,k}$ using discrete Morse
theory.

###  3.1. The complex of partial surjections

Given integers $n>k\geq 1$, we let $C_{n,k}$ denote the set of partial
surjective functions

$\eta:[n]\to[k].$

Equivalently, we can think of $C_{n,k}$ as the set of $k$-partitions

$\big{(}\eta^{-1}(1),\eta^{-1}(2),\dots,\eta^{-1}(k)\big{)}$

of subsets of $[n]$. Furthermore, we may identify an element $\eta\in C_{n,k}$
with the product of simplices

$\Delta_{\eta}:=2^{\eta^{-1}(1)}\times 2^{\eta^{-1}(2)}\times\cdots\times
2^{\eta^{-1}(k)},$

whose geometric realization is a convex polytope of dimension
$|\eta^{-1}([k])|-k$.

Observe that for $\eta,\gamma\in C_{n,k}$, if
$\eta^{-1}([k])\subset\gamma^{-1}([k])$ and $\eta(x)=\gamma(x)$ for all
$x\in\eta^{-1}([k])$, then $\Delta_{\eta}$ is a face of $\Delta_{\gamma}$.
Consequently, $C_{n,k}$ has the structure of a polyhedral complex (see Figure
1). Note that $C_{n,k}$ may also be viewed as a poset where the faces are
ordered by inclusion.

$2\>|\>3\>|\>4$$1\>|\>3\>|\>4$$5\>|\>3\>|\>4$$2\>|\>3\>|\>6$$5\>|\>3\>|\>6$$1\>|\>3\>|\>6$$4\>|\>123$$24\>|\>13$$234\>|\>1$$34\>|\>12$$134\>|\>2$$14\>|\>23$$124\>|\>3$$2\>|\>134$$23\>|\>14$$3\>|\>124$$13\>|\>24$$1\>|\>234$$12\>|\>34$$123\>|\>4$$4\,|\,1$$2\,|\,1$$3\,|\,1$$2\,|\,4$$4\,|\,2$$3\,|\,2$$1\,|\,2$$3\,|\,4$$4\,|\,3$$1\,|\,3$$2\,|\,3$$1\,|\,4$
Figure 1. Above: The polyhedral cell of $C_{6,3}$ corresponding to the ordered
partition $\big{(}\\{1,2,5\\},\\{3\\},\\{4,6\\}\big{)}$, which we express more
succinctly by $(125\>|\>3\>|\>46)$. Below: The cell complex $C_{4,2}$.

We need the following.

######  Lemma 3.1.

For all integers $n>k\geq 1$, we have a homotopy equivalence $K_{n,k}\simeq
C_{n,k}$.

###### Proof.

Let $K=K_{n,k}$ and $C=C_{n,k}$. Our goal is to construct an order-reversing
map

$g:K\to C$

such that $g^{-1}(C_{\succeq\eta})$ is contractible for every $\eta\in C$,
where $C_{\succeq\eta}=\\{\gamma\in C:\Delta_{\gamma}\supset\Delta_{\eta}\\}$.
This will establish the desired homotopy equivalence by Quillen’s fiber lemma
[4, Theorem 10.5].

To this end, consider a face
$\sigma=\\{\varphi_{1},\varphi_{2},\dots,\varphi_{|\sigma|}\\}\in K_{n,k}$ and
define the $k$-tuple

$X=(X_{1},X_{2},\dots,X_{k}),$

where
$X_{j}=\varphi^{-1}_{1}(j)\cap\varphi^{-1}_{2}(j)\cap\cdots\cap\varphi^{-1}_{|\sigma|}(j)$
as in (1). By definition, each $X_{j}$ is nonempty, and so $X$ is a
$k$-partition of a subset of $[n]$. We may therefore identify $X$ with a
partial surjective function $\eta_{\sigma}:[n]\to[k]$ given by
$\eta_{\sigma}(i)=j$ when $\varphi(i)=j$ for each $\varphi\in\sigma$, and
$\eta_{\sigma}(i)$ is undefined otherwise, or equivalently
$\eta_{\sigma}^{-1}(j)=X_{j}$. By setting

$g(\sigma):=\eta_{\sigma},$

we have

$\displaystyle\tau\subset\sigma$
$\displaystyle\implies\eta_{\sigma}^{-1}(j)\subset\eta_{\tau}^{-1}(j)\text{
for each $j\in[k]$}$
$\displaystyle\implies\Delta_{g(\sigma)}\subset\Delta_{g(\tau)},$

so we obtain a surjective map $g:K\to C$, which is order-reversing. The upper
set $C_{\succeq\eta}$ is the set of partial functions $\gamma$ such that
$\gamma^{-1}(j)\supset\eta^{-1}(j)$ for each $j$, that is, $C_{\succeq\eta}$
is the set of extensions of $\eta$, so

$g^{-1}(C_{\succeq\eta})=2^{\sigma_{\eta}}$

where

$\sigma_{\eta}:=\big{\\{}\varphi\in K_{n,k}:\varphi(i)=\eta(i)\text{ if
}\eta(i)\text{ is defined}\big{\\}}.$

Thus the fibers are simplices, and the associated complexes $K_{n,k}$ and
$C_{n,k}$ are homotopy equivalent by Quillen’s fiber lemma. ∎

###  3.2. Acyclic matchings

We now apply discete Morse theory [7] to determine the connectedness of
$C_{n,k}$. This means that we now view $C_{n,k}$ as a poset, and it contains
the empty face as a unique minimal element.

Recall that a matching in a poset $P$ is a matching in the underlying graph of
the Hasse diagram of $P$. In other words, a matching $M$ in $P$ is a
collection of pairs

$M=\big{\\{}\\{a_{1},b_{1}\\},\\{a_{2},b_{2}\\},\dots,\\{a_{t},b_{t}\\}\big{\\}},$

where the $a_{i}$ and $b_{j}$ are all distinct, and $a_{i}$ is an immediate
predecessor of $b_{i}$ for every $i$. The matching $M$ is called cyclic if
there is a subsequence of indices $i_{1},i_{2},\dots,i_{s}\in[t]$ such that

$\begin{array}[]{lcl}a_{i_{2}}&\prec&b_{i_{1}}\\\ a_{i_{3}}&\prec&b_{i_{2}}\\\
&\vdots&\\\ a_{i_{s}}&\prec&b_{i_{s-1}}\\\
a_{i_{1}}&\prec&b_{i_{s}}\end{array}$

If no such subsequence exists, then the matching $M$ is called acyclic.

In the case when $P$ is the face lattice of a polyhedral complex and $M$ is an
acyclic matching, then the unmatched elements of $P$ are called the critical
cells of the matching. One of the fundamental theorems of discrete Morse
theory [9, Theorem 4.7] (see also [10, Theorem 11.13]) asserts that if all the
critical cells of $M$ have dimension at least $d$, then the polyhedral complex
is $(d-1)$-connected. Our goal is therefore to show the following

######  Lemma 3.2.

For all $n>k\geq 1$, there is an acyclic matching $M$ on $C_{n,k}$ whose
critical cells (if there are any) have dimension $n-k$.

In order to find such an acyclic matching we need two basic tools from the
toolbox of discrete Morse theory. The first one (referred to as an element
matching [9, Lemma 4.1]) describes a particular acyclic matching which we use
repeatedly. Let $(\sigma-x,\sigma+x)$ denote
$(\sigma\setminus\\{x\\},\sigma\cup\\{x\\})$.

######  Lemma (Element matching).

Let $X$ be a finite set, $P\subseteq 2^{X}$ is ordered by inclusion, and for a
fixed element $x\in X$, let

(5) $\displaystyle P_{x}$ $\displaystyle=\\{\sigma:\sigma-x,\sigma+x\in P\\}$
(6) $\displaystyle M_{x}$ $\displaystyle=\\{\\{\sigma-x,\sigma+x\\}:\sigma\in
P_{x}\\}.$

Then $M_{x}$ is an acyclic matching on $P$.

The second tool allows us to combine a collection of acyclic matchings into a
single one (see [9, Lemma 4.2] or [10, Theorem 11.10]).

######  Lemma (Patchwork lemma).

Let $P$ and $Q$ be finite posets, and let $h:P\to Q$ be an order-preserving
map. Assume we have acyclic matchings $M_{q}$ on each of the subposets
$h^{-1}(q)$. Then, $M=\bigcup_{q\in Q}M_{q}$ is an acyclic matching on $P$.

###### Proof of Lemma 3.2.

We proceed by induction on $k$. For $k=1$, observe that $C_{n,1}$ is
isomorphic to $2^{[n]}$, and so the element matching

$\big{\\{}\\{\sigma-n,\sigma+n\\}:\sigma\in 2^{[n]}\big{\\}}$

is a complete acyclic matching (i.e. there are no critical cells).

Now, assume $k>1$ and that the lemma holds for $C_{n^{\prime},k-1}$ for all
$n^{\prime}>k-1$. We denote the cells of $C_{n,k}$ as $k$-tuples

$X=(X_{1},X_{2},\dots,X_{k}),$

where the $X_{i}$ are either nonempty, pairwise disjoint subsets of $[n]$
(corresponding to a nonempty cell of $C_{n,k}$), or they satisfy
$X_{1}=X_{2}=\cdots=X_{k}=\emptyset$ (corresponding to the unique empty cell).
Note that the dimension of a nonempty cell equals $\sum_{i=1}^{k}(|X_{i}|-1)$,
and so our goal is to find an acyclic matching in $C_{n,k}$ whose critical
cells (if there are any) satisfy $X_{1}\cup X_{2}\cup\cdots\cup X_{k}=[n]$.

Let $\\{a_{1},a_{2},\dots,a_{k-1}\\}$ be an antichain and let $a_{k}\prec
a_{i}$ for all $1\leq i<k$. Then a map
$h_{1}:C_{n,k}\to\\{a_{1},a_{2},\dots,a_{k}\\}$, defined by

$h_{1}(X_{1},X_{2},\dots,X_{k})=\begin{cases}a_{i}&\text{ if }n\in X_{i}\text{
and }i<k\\\ a_{k}&\text{ otherwise }\end{cases}$

is order-preserving. Our goal is therefore to apply the patchwork lemma by
finding appropriate acyclic matchings on each of the subposets
$A_{i}:=h_{1}^{-1}(a_{i})$.

Fix $1\leq i<k$ and consider the projection map
$p_{i}:A_{i}\to(2^{[n-1]})^{\times(k-1)}$ which forgets the $i$th component

$p_{i}(X_{1},X_{2},\dots,X_{k})=(X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{k}).$

This is an order preserving map when the range of $p_{i}$ is ordered by
(componentwise) inclusion. For a given
$(X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{k})$ in the range of $p_{i}$, we
observe that $p_{i}^{-1}(X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{k})$ is
isomorphic to $2^{Y_{i}}$, where

$Y_{i}:=[n-1]\setminus(X_{1}\cup\cdots\cup X_{i-1}\cup X_{i+1}\cup\cdots\cup
X_{k}).$

Therefore, if $Y_{i}\neq\emptyset$, then
$p_{i}^{-1}(X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{k})$ has a complete element
matching. Otherwise, we have

$p_{i}^{-1}(X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{k})=(X_{1},\dots,X_{i-1},\\{n\\},X_{i+1},\dots,X_{k}),$

which will be one of our critical cells of dimension $n-k$.

It remains to find an appropriate acyclic matching on $A_{k}$. Define an
order-preserving map $h_{2}:A_{k}\to\\{a\prec b\\}$ where

$h_{2}(X_{1},X_{2},\dots,X_{k})=\begin{cases}a&\text{ if }X_{k}=\\{n\\}\text{
or }X_{k}=\emptyset,\\\ b&\text{ otherwise. }\end{cases}$

Set $A:=h_{2}^{-1}(a)$ and $B:=h_{2}^{-1}(b)$. Note that the empty cell
belongs to $A$, and $A$ is isomorphic to $C_{n-1,k-1}$. By induction, there is
an acyclic matching on $A$ such that all critical cells (if there are any)
have dimension $n-k$.

Consider the projection map $p_{k}:B\to(2^{[n-1]})^{\times(k-1)}$ which
forgets the $k$th component

$p_{i}(X_{1},X_{2},\dots,X_{k})=(X_{1},X_{2},\dots,X_{k-1}).$

This is an order preserving map when the range of $p_{k}$ is ordered by
(componentwise) inclusion. For a given $(X_{1},X_{2},\dots,X_{k-1})$ in the
range of $p_{k}$, we observe that $p_{i}^{-1}(X_{1},X_{2},\dots,X_{k-1})$ is
isomorphic to $2^{Y_{k}}\setminus\big{\\{}\emptyset,\\{n\\}\big{\\}}$, where

$Y_{k}:=[n]\setminus(X_{1}\cup X_{2}\cup\cdots\cup X_{k-1}).$

By definition, $Y_{k}\neq\emptyset$, and so
$p_{i}^{-1}(X_{1},X_{2},\dots,X_{k-1})$ has a complete element matching of the
form $\\{\sigma-n,\sigma+n\\}$. ∎

## References

  * [1] Imre Bárány.  A generalization of Carathéodory’s theorem.  Discrete Mathematics, 40(2-3):141–152, 1982.
  * [2] Imre Bárány.  Combinatorial convexity, volume 77.  American Mathematical Soc., 2021.
  * [3] Imre Bárány and Gil Kalai.  Helly-type problems.  Bulletin of the American Mathematical Society, 59(4):471–502, 2022\.
  * [4] Anders Björner.  Topological methods.  Handbook of combinatorics, 2:1819–1872, 1995.
  * [5] Jesús De Loera, Xavier Goaoc, Frédéric Meunier, and Nabil Mustafa.  The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg.  Bulletin of the American Mathematical Society, 56(3):415–511, 2019\.
  * [6] Jürgen Eckhoff.  Helly, Radon, and Carathéodory type theorems.  In Handbook of convex geometry, pages 389–448. Elsevier, 1993.
  * [7] Robin Forman.  A discrete Morse theory for cell complexes.  In Geometry, topology, and physics, Conf. Proc. Lecture Notes Geom. Topology, IV, pages 112–125, 1995.
  * [8] Andreas Holmsen and Rephael Wenger.  Helly-type theorems and geometric transversals.  In Handbook of discrete and computational geometry, pages 91–123. Chapman and Hall/CRC, 2017.
  * [9] Jakob Jonsson.  Simplicial complexes of graphs, volume 1928.  Springer, 2008.
  * [10] Dimitry Kozlov.  Combinatorial algebraic topology, volume 21.  Springer Science & Business Media, 2008.
  * [11] Leonardo Martínez-Sandoval, Edgardo Roldán-Pensado, and Natan Rubin.  Further consequences of the colorful Helly hypothesis.  Discrete & Computational Geometry, 63(4):848–866, 2020.
  * [12] Jiri Matousek.  Lectures on discrete geometry, volume 212.  Springer Science & Business Media, 2013.
  * [13] Jiří Matoušek, Anders Björner, Günter M Ziegler, et al.  Using the Borsuk-Ulam theorem: lectures on topological methods in combinatorics and geometry, volume 2003.  Springer, 2003.
  * [14] L Montejano.  Transversals, topology and colorful geometric results.  Geometry—Intuitive, Discrete, and Convex: A Tribute to László Fejes Tóth, pages 205–218, 2013.
  * [15] Luis Montejano and Roman N Karasev.  Topological transversals to a family of convex sets.  Discrete & Computational Geometry, 46(2):283–300, 2011.
  * [16] Sherry Sarkar and Pablo Soberón.  Tolerance for colorful Tverberg partitions.  European Journal of Combinatorics, 103:103527, 2022.
  * [17] Helge Tverberg.  A generalization of Radon’s theorem.  Journal of the London Mathematical Society, 1(1):123–128, 1966\.
  * [18] A Yu Volovikov.  On a topological generalization of the Tverberg theorem.  Mathematical Notes, 59(3):324–326, 1996.