Combinatorics

Authors and titles for August 2021

[1] arXiv:2108.00001 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Mixing colourings in $2K_2$-free graphs Show Chinese title

Title: 在$2K_2$-free 图中的混合着色

Carl Feghali, Owen Merkel

Comments: 4 pages, 2 figures

Subjects: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM)

[2] arXiv:2108.00035 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Computational complexity and pragmatic solutions for flexible tile based DNA self-assembly Show Chinese title

Title: 基于灵活瓷砖的DNA自组装的计算复杂性和实用解决方案

Leyda Almodóvar, Jo Ellis-Monaghan, Amanda Harsy, Cory Johnson, Jessica Sorrells

Comments: 41 pages, 30 figures

Subjects: Combinatorics (math.CO)

[3] arXiv:2108.00050 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Lazy tournaments and multidegrees of a projective embedding of $\overline{M}_{0,n}$ Show Chinese title

Title: 懒惰锦标赛和射影嵌入的多次数$\overline{M}_{0,n}$

Maria Gillespie, Sean T. Griffin, Jake Levinson

Comments: 22 pages, 7 figures

Subjects: Combinatorics (math.CO) ; Algebraic Geometry (math.AG)

[4] arXiv:2108.00074 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Sharp density bounds on the finite field Kakeya problem Show Chinese title

Title: 有限域Kakeya问题的密集度界限

Boris Bukh, Ting-Wei Chao

Comments: 9 pages, 1 figure

Journal-ref: Discrete Analysis, 2021:26

Subjects: Combinatorics (math.CO)

[5] arXiv:2108.00101 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: The Pyro game: a slow intelligent fire Show Chinese title

Title: 燃烧游戏：一种缓慢的智能火焰

Margaret-Ellen Messinger, Spencer Yarnell

Subjects: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM)

[6] arXiv:2108.00134 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Factorially many maximum matchings close to the Erdős-Gallai bound Show Chinese title

Title: 因子众多的最大匹配接近Erdős-Gallai界限

Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta, Dieter Rautenbach

Subjects: Combinatorics (math.CO)

[7] arXiv:2108.00191 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Proof of the Bessenrodt--Ono inequality by Induction Show Chinese title

Title: Bessenrodt--Ono不等式的归纳法证明

Bernhard Heim, Markus Neuhauseer

Subjects: Combinatorics (math.CO)

[8] arXiv:2108.00198 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: An improved planar graph product structure theorem Show Chinese title

Title: 一种改进的平面图乘积结构定理

Torsten Ueckerdt, David R. Wood, Wendy Yi

Comments: arXiv admin note: text overlap with arXiv:1904.04791

Subjects: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM)

[9] arXiv:2108.00232 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: An asymptotic lower bound on the number of bent functions Show Chinese title

Title: 关于弯函数数量的渐近下界

V. N. Potapov, A. A. Taranenko, Yu. V. Tarannikov

Comments: v.1: 10 pages v.2: 13 pages; all main results remain the same, but we extend the introduction, add many references, change the title, and make a large number of other small improvements

Subjects: Combinatorics (math.CO)

[10] arXiv:2108.00245 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Bipartite Graft III: General Case Show Chinese title

Title: 二部图嫁接 III：一般情况

Nanao Kita

Comments: Sequel of arXiv:2101.06678

Subjects: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM)

[11] arXiv:2108.00420 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Connectivity of Alternating Sign Triangle Show Chinese title

Title: 交替符号三角形的连通性

Son Nguyen

Comments: arXiv admin note: text overlap with arXiv:2105.03969

Subjects: Combinatorics (math.CO)

[12] arXiv:2108.00479 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: On the maximum number of distinct intersections in an intersecting family Show Chinese title

Title: 关于相交族中不同交点的最大数量

Peter Frankl, Sergei Kiselev, Andrey Kupavskii

Subjects: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM)

[13] arXiv:2108.00502 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Choice number of Kneser graphs Show Chinese title

Title: Kneser图的选择数

Vera Bulankina, Andrey Kupavskii

Subjects: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM)

[14] arXiv:2108.00522 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Unified framework for tableau models of Grothendieck polynomials Show Chinese title

Title: 格罗滕迪克多项式的表格模型的统一框架

Graham Hawkes

Journal-ref: Contributions to Discrete Mathematics 19(3) (2024), 86-101

Subjects: Combinatorics (math.CO)

[15] arXiv:2108.00526 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Planar graphs with the maximum number of induced 4-cycles or 5-cycles Show Chinese title

Title: 平图中具有最多诱导4-环或5-环的情况

Michael Savery

Comments: v2: 30 pages and 6 figures, minor corrections and adjustments

Subjects: Combinatorics (math.CO)

[16] arXiv:2108.00544 (cross-list from math.CO) [cn-pdf, pdf, html, other]

Title: Parametrizing the Ramsey theory of vector spaces I: Discrete spaces Show Chinese title

Title: 向量空间的Ramsey理论参数化I：离散空间

Iian B. Smythe

Comments: 30 pages. Substantial revisions have been made to much of the paper. Major changes made include: The results in Section 2 now have self-contained and elementary proofs. An error in the previous Lemma 5.2 was found and corrected (now as Lemma 6.2). A gap in the proof of the previous Lemma 5.5 was found, circumventing this issue required changing the proofs for the clopen case of the main result

Subjects: Combinatorics (math.CO) ; Logic (math.LO)

[17] arXiv:2108.00550 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Circular planar electrical networks, Split systems, and Phylogenetic networks Show Chinese title

Title: 环状平面电气网络，分裂系统，和系统发生网络

Stefan Forcey

Comments: 23 pages

Subjects: Combinatorics (math.CO)

[18] arXiv:2108.00592 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Smith Normal Form and the Generalized Spectral Characterization of Graphs Show Chinese title

Title: 史密斯标准型和图的广义谱特征化

Lihong Qiu, Wei Wang, Wei Wang, Hao Zhang

Comments: 14 pages

Subjects: Combinatorics (math.CO)

[19] arXiv:2108.00613 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Weakly distance-regular digraphs of one type of arcs Show Chinese title

Title: 弱距离正则有向图的一种弧类型

Yushuang Fan, Zhiqi Wang, Yuefeng Yang

Subjects: Combinatorics (math.CO)

[20] arXiv:2108.00618 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Bier spheres of extremal volume and generalized permutohedra Show Chinese title

Title: 极值体积的Bier球和广义排列多面体

Filip D. Jevtić, Rade T. Živaljević

Subjects: Combinatorics (math.CO) ; Metric Geometry (math.MG)

[21] arXiv:2108.00635 (cross-list from math.CO) [cn-pdf, pdf, html, other]

Title: The number of distinguishing colorings of a Cartesian product graph Show Chinese title

Title: 一个笛卡尔积图的区分着色数

Saeid Alikhani, Mohammad Hadi Shekarriz

Comments: 11 pages, 4 figures

Journal-ref: Quaestiones Mathematicae

Subjects: Combinatorics (math.CO)

[22] arXiv:2108.00875 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Intersection numbers on tropical Hassett spaces Show Chinese title

Title: 热带Hassett空间上的相交数

Marvin Anas Hahn, Shiyue Li

Comments: 27 pages; v2 with improved readability

Journal-ref: Combinatorial Theory 2(3), 2022

Subjects: Combinatorics (math.CO) ; Algebraic Geometry (math.AG)

[23] arXiv:2108.00987 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Threshold Ramsey multiplicity for odd cycles Show Chinese title

Title: 奇圈的阈值 Ramsey 重数

David Conlon, Jacob Fox, Benny Sudakov, Fan Wei

Comments: 17 pages

Subjects: Combinatorics (math.CO)

[24] arXiv:2108.00991 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Threshold Ramsey multiplicity for paths and even cycles Show Chinese title

Title: 路径和偶数圈的阈值 Ramsey 重数

David Conlon, Jacob Fox, Benny Sudakov, Fan Wei

Comments: 28 pages

Subjects: Combinatorics (math.CO)

[25] arXiv:2108.01023 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: The Increasing Families of Sets Generated by Self-dual Clutters Show Chinese title

Title: 由自对偶杂凑生成的集合族的增加 families

Andrey O. Matveev

Comments: 14 pages

Subjects: Combinatorics (math.CO)

[26] arXiv:2108.01024 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: An algorithm for counting arcs in higher-dimensional projective space Show Chinese title

Title: 高维射影空间中计数弧的算法

Kelly Isham

Comments: Revised based on referee suggestions. Accepted to Finite Fields and Their Applications

Subjects: Combinatorics (math.CO)

[27] arXiv:2108.01032 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: The tripartite-circle crossing number of graphs with two small partition classes Show Chinese title

Title: 图的三元圆交叉数，其中两个划分类较小

Charles Camacho, Silvia Fernández-Merchant, Marija Jelić Milutinović, Rachel Kirsch, Linda Kleist, Elizabeth Bailey Matson, Jennifer White

Comments: 22 pages, 11 figures. Added new results and revised throughout. Originally appeared in arXiv:1910.06963v1, now removed from arXiv:1910.06963v2

Journal-ref: Computing in Geometry and Topology, Vol. 3 No. 1 (2024), 9:1-9:21

Subjects: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM)

[28] arXiv:2108.01058 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Self-dual polyhedra of given degree sequence Show Chinese title

Title: 给定度序列的自对偶多面体

Riccardo W. Maffucci

Subjects: Combinatorics (math.CO)

[29] arXiv:2108.01061 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: A 1-Separation Formula for the Graph Kemeny Constant and Braess Edges Show Chinese title

Title: 一个图Kemeny常数的1-分离公式和Braess边

Nolan Faught, Mark Kempton, Adam Knudson

Subjects: Combinatorics (math.CO)

[30] arXiv:2108.01108 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: A note on extremal intersecting linear Ryser systems Show Chinese title

Title: 关于极值相交线性 Ryser 系统的一篇笔记

Adrián Vázquez Ávila

Subjects: Combinatorics (math.CO)

[31] arXiv:2108.01119 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Hamiltonicity of the Complete Double Vertex Graph of some Join Graphs Show Chinese title

Title: 完全双顶点图的一些连接图的哈密顿性

Luis Manuel Rivera, Ana Laura Trujillo-Negrete

Comments: 8 pages, 1 figure. The results presented in this article were presented in preprint arXiv:2007.00115 which was splitted into two papers

Subjects: Combinatorics (math.CO)

[32] arXiv:2108.01162 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree Show Chinese title

Title: 诱导子图和树分解 II. 关于有界度图中的墙及其线图

Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Sepehr Hajebi, Paweł Rzążewski, Sophie Spirkl, Kristina Vušković

Comments: Accepted manuscript; see DOI for journal version

Journal-ref: Journal of Combinatorial Theory, Series B, Volume 164, January 2024, Pages 371-403

Subjects: Combinatorics (math.CO)

[33] arXiv:2108.01168 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: $(k,H)$-kernels in nearly tournaments Show Chinese title

Title: $(k,H)$-核在几乎竞赛图中

Hortensia Galeana-Sánchez, Miguel Tecpa-Galván

Comments: arXiv admin note: text overlap with arXiv:2105.00044

Subjects: Combinatorics (math.CO)

[34] arXiv:2108.01209 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: On ($1,C_4$) one-factorization and two orthogonal ($2,C_4$) one-factorization of complete graphs Show Chinese title

Title: 关于完全图的（$1,C_4$）一因子分解和两个正交的（$2,C_4$）一因子分解

Adrián Vázquez-Ávila

Comments: arXiv admin note: text overlap with arXiv:1906.09291

Subjects: Combinatorics (math.CO)

[35] arXiv:2108.01263 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Twist polynomials of delta-matroids Show Chinese title

Title: 扭多项式 of delta-矩阵

Qi Yan, Xian'an Jin

Comments: 13 pages, 1 figure

Subjects: Combinatorics (math.CO)

[36] arXiv:2108.01325 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: The signless Laplacian state transfer in Q-graph Show Chinese title

Title: 无符号拉普拉斯状态传输在Q图中

Xiao-Qin Zhang, Shu-Yu Cui, Gui-Xian Tian

Comments: 17 pages

Subjects: Combinatorics (math.CO)

[37] arXiv:2108.01347 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Three families of toric rings arising from posets or graphs with small class groups Show Chinese title

Title: 由偏序集或图产生的具有小类群的环族

Akihiro Higashitani, Koji Matsushita

Comments: 25 pages, 20 figures. Comments are welcome

Subjects: Combinatorics (math.CO) ; Commutative Algebra (math.AC)

[38] arXiv:2108.01443 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Inertia indices of a complex unit gain graph in terms of matching number Show Chinese title

Title: 惯性指数与匹配数的关系

Yong Lu, Qi Wu

Comments: 17 pages. arXiv admin note: text overlap with arXiv:1909.07555 by other authors

Subjects: Combinatorics (math.CO)

[39] arXiv:2108.01580 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Biased multilinear maps of abelian groups Show Chinese title

Title: 阿贝尔群的有偏多重线性映射

Sean Eberhard

Comments: 12 pages

Subjects: Combinatorics (math.CO)

[40] arXiv:2108.01633 (cross-list from math.CO) [cn-pdf, pdf, html, other]

Title: Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs Show Chinese title

Title: 将线性哈迪格猜想减少到着色小图

Michelle Delcourt, Luke Postle

Comments: 25 pages. In this version, some minor typos fixed. Previously updated in response to referee comments. This and the three previous versions add the necessary results from arXiv:2006.11798 in order to create a self-contained standalone paper. arXiv admin note: text overlap with arXiv:2006.11798, arXiv:2010.05999

Subjects: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM)

[41] arXiv:2108.01794 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Explicit RIP matrices: an update Show Chinese title

Title: 显式RIP矩阵：更新

Kevin Ford, Denka Kutzarova, George Shakan

Comments: Minor corrections

Journal-ref: Acta Math. Hungarica 168 (2022), 509-515

Subjects: Combinatorics (math.CO) ; Information Theory (cs.IT)

[42] arXiv:2108.01888 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Graphs with at most one generalized cospectral mate Show Chinese title

Title: 最多有一个广义同谱伙伴的图

Wei Wang, Wei Wang, Tao Yu

Comments: 18 pages; typos corrected and a small change on the definition of primitive matrix

Subjects: Combinatorics (math.CO)

[43] arXiv:2108.01990 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Combinatorial Algorithms for Multidimensional Necklaces Show Chinese title

Title: 组合算法用于多维项链

Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov

Subjects: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM)

[44] arXiv:2108.01992 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk Show Chinese title

Title: 连续时间量子漫步在约翰逊图上的空间搜索

Hajime Tanaka, Mohamed Sabri, Renato Portugal

Comments: 12 pages

Journal-ref: Quantum Inf Process 21, 74 (2022)

Subjects: Combinatorics (math.CO) ; Computational Complexity (cs.CC) ; Quantum Physics (quant-ph)

[45] arXiv:2108.02022 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: The Jacobian of Cyclic Voltage Covers of $K_n$ Show Chinese title

Title: Cyclic Voltage Covers 的雅可比矩阵$K_n$

Sophia Gonet

Comments: 27 pages

Subjects: Combinatorics (math.CO) ; Number Theory (math.NT)

[46] arXiv:2108.02185 (cross-list from math.CO) [cn-pdf, pdf, html, other]

Title: Maximum likelihood thresholds via graph rigidity Show Chinese title

Title: 最大似然阈值通过图的刚性

Daniel Irving Bernstein, Sean Dewar, Steven J. Gortler, Anthony Nixon, Meera Sitharam, Louis Theran

Comments: In press at Annals of Applied Probability

Subjects: Combinatorics (math.CO) ; Statistics Theory (math.ST)

[47] arXiv:2108.02288 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: The Gotsman-Linial Conjecture is False Show Chinese title

Title: 戈茨曼-林纳尔猜想是错误的

Brynmor Chapman

Comments: Appeared in SODA 2018

Journal-ref: Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 692-699, 2018

Subjects: Combinatorics (math.CO) ; Computational Complexity (cs.CC)

[48] arXiv:2108.02295 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: The combinatorics of weight systems and characteristic polynomials of isolated quasihomogeneous singularities Show Chinese title

Title: 权系的组合学和孤立准齐次奇点的特征多项式

Claus Hertling, Makiko Mase

Comments: 25 pages

Subjects: Combinatorics (math.CO) ; Algebraic Geometry (math.AG) ; Complex Variables (math.CV)

[49] arXiv:2108.02363 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: On the Existence of Word-representable Line Graphs of Non-word-representable Graphs Show Chinese title

Title: 关于非字可表示图的字可表示线图的存在性

M M Akbar, P D Akrobotu, C P Brewer

Comments: 11 pages, 7 figures

Subjects: Combinatorics (math.CO)

[50] arXiv:2108.02364 (cross-list from math.CO) [cn-pdf, pdf, other]

Title: Spectral extrema of $K_{s,t}$-minor free graphs--On a conjecture of M. Tait Show Chinese title

Title: 谱极值的$K_{s,t}$-自由图——关于 M. Tait 的一个猜想

Mingqing Zhai, Huiqiu Lin

Comments: 27

Subjects: Combinatorics (math.CO)