Kolmogorov complexity as a combinatorial tool
<|reference_start|>Kolmogorov complexity as a combinatorial tool: Kolmogorov complexity is often used as a convenient language for counting and/or probabilistic existence proofs. However, there are some applications where Kolmogorov complexity is used in a more subtle way. We provide one (somehow) surprising example where an existence of a winning strategy in a natural combinatorial game is proven (and no direct proof is known).<|reference_end|>
@article{shen2024kolmogorov,
    title={Kolmogorov complexity as a combinatorial tool},
    author={Alexander Shen},
    journal={arXiv preprint arXiv:2405.09304},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.09304},
    primaryClass={cs.DM cs.IT math.CO math.IT}
}