2017/04/28 by Kai Jin, Jin, Kai
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.1 #G.2.2 #I.2.11 #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1704.08852
We design the first explicit 1-factorization of H(2,q), where q is a odd prime power
arxiv created 2019/04/03 · arxiv updated 2019/04/04
It is a challenging open problem to construct an explicit 1-factorization of the bipartite Kneser graph H(v,t), which contains as vertices all t-element and (v-t)-element subsets of [v]:=\1,…,v\ and an edge between any two vertices when one is a subset of the other. In this paper, we propose a new framework for designing such 1-factorizations, by which we solve a nontrivial case where t=2 and v is an odd prime power. We also revisit two classic constructions for the case v=2t+1 --- the lexical factorization and modular factorization. We provide their simplified definitions and study their inner structures. As a result, an optimal algorithm is designed for computing the lexical factorizations. (An analogous algorithm for the modular factorization is trivial.)