2025/08/10 by Pitchayut Saengrungkongka, Saengrungkongka, Pitchayut
Mathematics · #Advanced Combinatorial Mathematics #Analytic Number Theory Research #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.2508.07331
openalex publication_date 2025/08/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let n, s, and k be positive integers. We say that a sequence f1,…,fs of nonnegative integers is satisfying if for any collection of s families \mathcal F1,…,\mathcal Fs⊆ [n]k such that |\mathcal Fi|=fi for all i, there exists a rainbow matching, i.e., a list of pairwise disjoint tuples F1∈\mathcal F1, …, Fs∈\mathcal Fs. We investigate the question, posed by Kupavskii and Popova, of determining the smallest c=c(n,s,k) such that the arithmetic progression c, nk-1+c, 2nk-1+c, …, (s-1)nk-1+c is satisfying. We prove that the sequence is satisfying for c=Ωk(max(s2nk-2, snk-3/2√(log s))), improving the previous result by Kupavskii and Popova. We also study satisfying sequences for k=2 using the polynomial method, extending the previous result by Kupavskii and Popova to when n is not prime.