Combinatorics

Authors and titles for December 2020

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

Title: On minimal subspace Zp-null designs Show Chinese title

Title: 关于最小子空间 Zp-零设计

Denis S. Krotov (Sobolev Institute of Mathematics, Novosibirsk, Russia)

Comments: 5 pages

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

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

Title: Equitable [[2,10],[6,6]]-partitions of the 12-cube Show Chinese title

Title: 等价的 [[2,10],[6,6]]-划分的12维超立方体

Denis S. Krotov (Sobolev Institute of Mathematics, Novosibirsk, Russia)

Comments: v2: Section 4 and related data have been added

Journal-ref: Cryptogr. Commun. 16(5) 2024, 975-996

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

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

Title: The combinatorics of normal subgroups in the unipotent upper triangular group Show Chinese title

Title: 单位上三角群中正规子群的组合学

Lucas Gagnon

Comments: 33 pages, 1 figure, 1 table

Subjects: Combinatorics (math.CO) ; Group Theory (math.GR)

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

Title: Defining phylogenetic networks using ancestral profiles Show Chinese title

Title: 使用祖先特征定义系统发生网络

Allan Bai, Peter Erdos, Charles Semple, Mike Steel

Comments: 18 pages, 4 figures. arXiv admin note: text overlap with arXiv:1901.04064

Subjects: Combinatorics (math.CO)

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

Title: A Bijection Between Weighted Dyck Paths and 1234-avoiding Up-Down Permutations Show Chinese title

Title: 加权Dyck路径与避免1234的上升下降排列之间的双射

Justine Falque

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

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

Title: The role of the Axiom of Choice in proper and distinguishing colourings Show Chinese title

Title: 选择公理在恰当和区分着色中的作用

Marcin Stawiski

Subjects: Combinatorics (math.CO)

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

Title: Tight Bounds on the Probabilistic Zero Forcing on Hypercubes and Grids Show Chinese title

Title: 超立方体和网格上的概率零着色的紧致界

Natalie C. Behague, Trent Marbach, Pawel Pralat

Comments: arXiv admin note: substantial text overlap with arXiv:1909.06568

Subjects: Combinatorics (math.CO)

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

Title: Paths of given length in tournaments Show Chinese title

Title: 给定长度的竞赛图中的路径

Ashwin Sah, Mehtaab Sawhney, Yufei Zhao

Comments: Appendix with alternative entropy proof by Dingding Dong and Tomasz \'Slusarczyk

Subjects: Combinatorics (math.CO)

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

Title: A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem Show Chinese title

Title: 折叠超立方体中最小双消除集问题与硬币称重问题之间的桥梁

Changhong Lu, Qingjie Ye

Journal-ref: Discrete Appl. Math. 309 (2022) 147-159

Subjects: Combinatorics (math.CO)

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

Title: A construction of the abstract induced subgraph poset of a graph from its abstract edge subgraph poset Show Chinese title

Title: 从图的抽象边子图序集构造图的抽象诱导子图序集

Deisiane Lopes Gonçalves, Bhalchandra D. Thatte

Comments: 12 pages, 1 figure

Subjects: Combinatorics (math.CO)

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

Title: A variation on the Rubik's cube Show Chinese title

Title: 魔方的一个变种

Mathieu Dutour Sikirić

Comments: 7 pages, 4 figures

Subjects: Combinatorics (math.CO)

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

Title: Families of finite sets in which no set is covered by the union of the others Show Chinese title

Title: 有限集族，其中没有一个集合被其他集合的并所覆盖

Guillermo Alesandroni

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

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

Title: A bound on the joint spectral radius using the diagonals Show Chinese title

Title: 使用对角线的联合谱半径的界

Vuong Bui

Comments: 17 pages; minor revision before publication

Subjects: Combinatorics (math.CO)

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

Title: Improved Bounds for $(b,k)$-hashing Show Chinese title

Title: 改进的$(b,k)$-哈希界限

Stefano Della Fiore, Simone Costa, Marco Dalai

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

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

Title: Some applications of Wagner's weighted subgraph counting polynomial Show Chinese title

Title: Wagner加权子图计数多项式的某些应用

Ferenc Bencs, Péter Csikvári, Guus Regts

Subjects: Combinatorics (math.CO)

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

Title: On the Laplacian spectra of token graphs Show Chinese title

Title: 关于令牌图的拉普拉斯谱

C. Dalfó, F. Duque, R. Fabila-Monroy, M. A. Fiol, C. Huemer, A. L. Trujillo-Negrete, F. J. Zaragoza Martínez

Subjects: Combinatorics (math.CO)

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

Title: The generating function of Kreweras walks with interacting boundaries is not algebraic Show Chinese title

Title: Kreweras行走与相互作用边界生成函数不是代数的

Alin Bostan, Manuel Kauers, Thibaut Verron

Comments: 13 pages, accepted at FPSAC'21;

Subjects: Combinatorics (math.CO)

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

Title: Image sets of perfectly nonlinear maps Show Chinese title

Title: 完美非线性映射的像集

Lukas Kölsch, Björn Kriepke, Gohar M. Kyureghyan

Comments: Major revision

Subjects: Combinatorics (math.CO) ; Cryptography and Security (cs.CR) ; Information Theory (cs.IT)

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

Title: Chromatic symmetric functions of Dyck paths and q-rook theory (extended abstract) Show Chinese title

Title: 染色对称函数与Dyck路径及q-棋子理论（扩展摘要）

Laura Colmenarejo, Alejandro H. Morales, Greta Panova

Comments: To appear in FPSAC 2021 Proceedings. Extended abstract of ArXiv: 2104.07599

Subjects: Combinatorics (math.CO)

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

Title: Packings of partial difference sets Show Chinese title

Title: 部分差集的覆盖

Jonathan Jedwab, Shuxing Li

Comments: 41 pages, 2 tables, 1 figure. Minor revisions

Subjects: Combinatorics (math.CO)

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

Title: Hamilton decompositions of line graphs Show Chinese title

Title: 线图的哈密顿分解

Darryn Bryant, Sara Herke, Barbara Maenhaut, Benjamin R. Smith

Comments: 106 pages

Subjects: Combinatorics (math.CO)

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

Title: Classification of Finite Highly Regular Vertex-Coloured Graphs Show Chinese title

Title: 有限高度正则顶点着色图的分类

Irene Heinrich, Thomas Schneider, Pascal Schweitzer

Comments: 34 pages, 2 figures

Subjects: Combinatorics (math.CO)

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

Title: Total eccentricity index of graphs with fixed number of pendant or cut vertices Show Chinese title

Title: 图的总偏心指数与固定数量的悬挂顶点或割顶点

Dinesh Pandey, Kamal Lochan Patra

Comments: 17 pages, 5 figures

Subjects: Combinatorics (math.CO)

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

Title: Tree-width dichotomy Show Chinese title

Title: 树宽二分法

Vadim Lozin, Igor Razgon

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

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

Title: An elementary approach to solve recursions relative to the enumeration of S-Motzkin paths Show Chinese title

Title: 一种求解与S-Motzkin路径计数相关的递归关系的初等方法

Helmut Prodinger

Subjects: Combinatorics (math.CO)

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

Title: An extension of the Wilf conjecture to semimodules over a numerical semigroup Show Chinese title

Title: 数值半群上半模的Wilf猜想的扩展

Patricio Almirón, Julio José Moyano-Fernández

Comments: v3: New title, section 4 of v2 has been suppressed, some others minor changes, 20 pages; v2: Minor changes from v1, 25 pages. Comments are welcome!

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

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

Title: Triangles and subgraph probabilities in random regular graphs Show Chinese title

Title: 三角形和随机正则图中的子图概率

Pu Gao

Subjects: Combinatorics (math.CO)

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

Title: A density bound for triangle-free $4$-critical graphs Show Chinese title

Title: 三角形-free 的$4$-临界图的密度界

Benjamin Moore, Evelyne Smith-Roberge

Comments: 40 pages. Final version, the authors are thankful for the comments of the referees

Subjects: Combinatorics (math.CO)

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

Title: A combinatorial formula for the nabla operator Show Chinese title

Title: nabla 算子的组合公式

Erik Carlsson, Anton Mellit

Comments: 35 Pages

Subjects: Combinatorics (math.CO) ; Representation Theory (math.RT)

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

Title: Multivariate Difference Gončarov Polynomials Show Chinese title

Title: 多元差分Gončarov多项式

Ayomikun Adeniran, Lauren Snider, Catherine Yan

Comments: 17 pages

Subjects: Combinatorics (math.CO)

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

Title: The graph minor theorem in topological combinatorics Show Chinese title

Title: 拓扑组合学中的图子式定理

Dane Miyata, Eric Ramos

Comments: Major Revision: Due to the gap found in the proof of the categorical graph minor theorem, this paper has been rewritten to prove a weaker version of that theorem. arXiv admin note: text overlap with arXiv:2004.05544

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

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

Title: Rainbow triangles in edge-colored complete graphs Show Chinese title

Title: 边着色完全图中的彩虹三角形

Xiaozheng Chen, Xueliang Li

Comments: 10 pages, 4 figures

Subjects: Combinatorics (math.CO)

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

Title: Optimal labelling schemes for adjacency, comparability, and reachability Show Chinese title

Title: 最优邻接、可比较性和可达性标记方案

Marthe Bonamy, Louis Esperet, Carla Groenland, Alex Scott

Comments: 17 pages - to appear in the proceedings of STOC 2021

Subjects: Combinatorics (math.CO) ; Data Structures and Algorithms (cs.DS)

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

Title: Moments of q-Jacobi Polynomials and q-Zeta Values Show Chinese title

Title: q-Jacobi多项式和q-ζ值的矩

Frédéric Chapoton (IRMA), Christian Krattenthaler, Jiang Zeng (ICJ)

Comments: 8 pages

Subjects: Combinatorics (math.CO)

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

Title: A domino tableau-based view on type B Schur-positivity Show Chinese title

Title: 基于多米诺表格的类型B舒尔正性观点

Alina R. Mayorova, Ekaterina A. Vassilieva

Subjects: Combinatorics (math.CO)

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

Title: Spectral properties of the $n$-Queens' Graphs Show Chinese title

Title: $n$皇后图的谱性质

Domingos M. Cardoso, Inês Serôdio Costa, Rui Duarte

Comments: 25 pages

Subjects: Combinatorics (math.CO)

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

Title: Multicritical random partitions Show Chinese title

Title: 多临界随机分划

Dan Betea, Jérémie Bouttier, Harriet Walsh

Comments: 12 pages, 3 figures (v2: minor modifications and clarifications). Extended abstract for FPSAC 2021

Journal-ref: S\'eminaire Lotharingien de Combinatoire, 85B.33 (2021), Proceedings of the 33rd Conference on Formal Power Series and Algebraic Combinatorics (Ramat Gan)

Subjects: Combinatorics (math.CO) ; Mathematical Physics (math-ph) ; Probability (math.PR)

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

Title: On tripartite common graphs Show Chinese title

Title: 关于三部图的共同图

Andrzej Grzesik, Joonkyung Lee, Bernard Lidický, Jan Volec

Subjects: Combinatorics (math.CO)

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

Title: Extremal density for sparse minors and subdivisions Show Chinese title

Title: 稀疏子图和细分图的极值密度

John Haslegrave, Jaehoon Kim, Hong Liu

Comments: 33 pages, 6 figures

Journal-ref: International Mathematics Research Notices, Volume 2022, Issue 20

Subjects: Combinatorics (math.CO)

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

Title: On extended 1-perfect bitrades Show Chinese title

Title: 关于扩展的1-完美位贸易

Evgeny A. Bespalov, Denis S. Krotov

Journal-ref: Discrete Math. 348(1) 2025, 114222(1-12)

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

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

Title: Trinets encode orchard phylogenetic networks Show Chinese title

Title: 三元网络编码果园系统发育网络

Charles Semple, Gerry Toft

Comments: 23 pages, 4 figures

Subjects: Combinatorics (math.CO)

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

Title: Power Graphs of Finite Group Show Chinese title

Title: 有限群的幂图

Amrita Acharyya, Allen Williams

Subjects: Combinatorics (math.CO)

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

Title: When do two networks have the same steady-state ideal? Show Chinese title

Title: 什么时候两个网络具有相同的稳态理想？

Mark Curiel, Elizabeth Gross, Carlos Munoz

Comments: 20 pages, 13 figures

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

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

Title: A vertex model for LLT polynomials Show Chinese title

Title: 一个顶点模型用于LLT多项式

Sylvie Corteel, Andrew Gitlin, David Keating, Jeremy Meza

Subjects: Combinatorics (math.CO) ; Mathematical Physics (math-ph) ; Probability (math.PR)

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

Title: Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces Show Chinese title

Title: Minor-闭合族的渐近维数和曲面的Assouad-Nagata维数

Marthe Bonamy, Nicolas Bousquet, Louis Esperet, Carla Groenland, Chun-Hung Liu, François Pirot, Alex Scott

Comments: This paper is essentially a combination of arXiv:2007.03582 and the non-algorithmic part of arXiv:2007.08771, where some results in arXiv:2007.03582 are strengthened. v2: fix the authors names. v3: update based on referees' comments, improve the bound for layered treewidth in Theorem 1.12 from 12 to 1, and simplify the proof without the use of fat bananas

Journal-ref: J. Eur. Math. Soc. (JEMS) 26 (2024), 3739-3791

Subjects: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM) ; Group Theory (math.GR) ; Geometric Topology (math.GT) ; Metric Geometry (math.MG)

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

Title: Ramsey monoids Show Chinese title

Title: 拉姆齐独异点

Claudio Agostini, Eugenio Colla

Comments: The structure of the paper has been strongly reworked, and some sections have been removed, accordingly to the referee's suggestions. Added new results on Solecki's generalization of Furstenberg and Katznelson's theorem. Added references for aperiodic monoids

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

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

Title: Complexity of fixed point counting problems in Boolean Networks Show Chinese title

Title: 布尔网络中固定点计数问题的复杂性

Florian Bridoux, Amélia Durbec, Kévin Perrot, Adrien Richard

Comments: 47 pages

Subjects: Combinatorics (math.CO) ; Computational Complexity (cs.CC) ; Discrete Mathematics (cs.DM) ; Molecular Networks (q-bio.MN)

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

Title: Routing for unmanned aerial vehicles: touring dimensional sets Show Chinese title

Title: 无人飞行器的路由：遍历维数集

Justo Puerto, Carlos Valverde

Subjects: Combinatorics (math.CO) ; Optimization and Control (math.OC)

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

Title: A Strehl Version of Fourth Franel Sequence Show Chinese title

Title: 第四弗兰尔序列的斯特雷尔版本

Hacene Belbachir, Yassine Otmani

Comments: 8 pages

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

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

Title: Connecting $k$-Naples parking functions and obstructed parking functions via involutions Show Chinese title

Title: 通过对合映射连接$k$-那不勒斯停车函数和阻碍停车函数

Roger Tian

Comments: 17 pages

Journal-ref: Electronic Journal of Combinatorics, Volume 29, Issue 3 (2022), #P3.8

Subjects: Combinatorics (math.CO)