Short rainbow cycles for families of matchings and triangles

被引:0
作者
Guo, He [1 ]
机构
[1] Umea Univ, Dept Math & Math Stat, S-90187 Umea, Sweden
关键词
generalized Caccetta-Haggkvist conjecture; rainbow girth; short rainbow cycles; GIRTH;
D O I
10.1002/jgt.23183
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A generalization of the famous Caccetta-Haggkvist conjecture, suggested by Aharoni, is that any family F = (F-1,..., F-n) of sets of edges in K-n, each of size k, has a rainbow cycle of length at most inverted right perpendicularn/kinverted left perpendicular. In works by the author with Aharoni and by the author with Aharoni, Berger, Chudnovsky, and Zerbib, it was shown that asymptotically this can be improved to O(log n) if all sets are matchings of size 2, or all are triangles. We show that the same is true in the mixed case, that is, if each F-i is either a matching of size 2 or a triangle. We also study the case that each F-i is a matching of size 2 or a single edge, or each F-i is a triangle or a single edge, and in each of these cases we determine the threshold proportion between the types, beyond which the rainbow girth goes from linear to logarithmic.
引用
收藏
页码:325 / 336
页数:12
相关论文
共 39 条
  • [31] Counting Short Cycles in Bipartite Graphs: A Fast Technique/Algorithm and a Hardness Result
    Dehghan, Ali
    Banihashemi, Amir H.
    IEEE TRANSACTIONS ON COMMUNICATIONS, 2020, 68 (03) : 1378 - 1390
  • [32] Acyclic 4-choosability of planar graphs without adjacent short cycles
    Borodin, Oleg V.
    Ivanova, Anna O.
    DISCRETE MATHEMATICS, 2012, 312 (22) : 3335 - 3341
  • [33] Acyclic 6-choosability of planar graphs without adjacent short cycles
    Wang WeiFan
    Zhang Ge
    Chen Min
    SCIENCE CHINA-MATHEMATICS, 2014, 57 (01) : 197 - 209
  • [34] On Computing the Number of Short Cycles in Bipartite Graphs Using the Spectrum of the Directed Edge Matrix
    Dehghan, Ali
    Banihashemi, Amir H.
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (10) : 6037 - 6047
  • [35] Protograph-based LDPC codes with chordless short cycles and large minimum distance
    Amirzade, Farzane
    Sadeghi, Mohammad-Reza
    Panario, Daniel
    2022 17TH CANADIAN WORKSHOP ON INFORMATION THEORY (CWIT), 2022, : 16 - 20
  • [36] Design of Multiple-Edge Protographs for QC LDPC Codes Avoiding Short Inevitable Cycles
    Park, Hosung
    Hong, Seokbeom
    No, Jong-Seon
    Shin, Dong-Joon
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2013, 59 (07) : 4598 - 4614
  • [37] PEG based Construction of Irregular QC-LDPC Codes by jointly Optimizing the Girth and the Number and ACE of Short cycles
    Wang, Dongdong
    Guo, Yantao
    Wang, Zhihui
    Wang, Liqian
    Chen, Xue
    2019 18TH INTERNATIONAL CONFERENCE ON OPTICAL COMMUNICATIONS AND NETWORKS (ICOCN), 2019,
  • [38] Reed-Solomon Based Quasi-Cyclic LDPC Codes: Designs, Girth, Cycle Structure, and Reduction of Short Cycles
    Xiao, Xin
    Vasic, Bane
    Lin, Shu
    Abdel-Ghaffar, Khaled
    Ryan, William E.
    IEEE TRANSACTIONS ON COMMUNICATIONS, 2019, 67 (08) : 5275 - 5286