Subjects -> MATHEMATICS (Total: 1013 journals)     - APPLIED MATHEMATICS (92 journals)    - GEOMETRY AND TOPOLOGY (23 journals)    - MATHEMATICS (714 journals)    - MATHEMATICS (GENERAL) (45 journals)    - NUMERICAL ANALYSIS (26 journals)    - PROBABILITIES AND MATH STATISTICS (113 journals) MATHEMATICS (714 journals)            First | 1 2 3 4
 Showing 601 - 538 of 538 Journals sorted alphabetically Results in Mathematics Results in Nonlinear Analysis Review of Symbolic Logic       (Followers: 2) Reviews in Mathematical Physics       (Followers: 1) Revista Baiana de Educação Matemática Revista Bases de la Ciencia Revista BoEM - Boletim online de Educação Matemática Revista Colombiana de Matemáticas       (Followers: 1) Revista de Ciencias Revista de Educación Matemática Revista de la Escuela de Perfeccionamiento en Investigación Operativa Revista de la Real Academia de Ciencias Exactas, Fisicas y Naturales. Serie A. Matematicas Revista de Matemática : Teoría y Aplicaciones       (Followers: 1) Revista Digital: Matemática, Educación e Internet Revista Electrónica de Conocimientos, Saberes y Prácticas Revista Integración : Temas de Matemáticas Revista Internacional de Sistemas Revista Latinoamericana de Etnomatemática Revista Latinoamericana de Investigación en Matemática Educativa Revista Matemática Complutense Revista REAMEC : Rede Amazônica de Educação em Ciências e Matemática Revista SIGMA Ricerche di Matematica RMS : Research in Mathematics & Statistics Royal Society Open Science       (Followers: 7) Russian Journal of Mathematical Physics Russian Mathematics Sahand Communications in Mathematical Analysis Sampling Theory, Signal Processing, and Data Analysis São Paulo Journal of Mathematical Sciences Science China Mathematics       (Followers: 1) Science Progress       (Followers: 1) Sciences & Technologie A : sciences exactes Selecta Mathematica       (Followers: 1) SeMA Journal Semigroup Forum       (Followers: 1) Set-Valued and Variational Analysis SIAM Journal on Applied Mathematics       (Followers: 11) SIAM Journal on Computing       (Followers: 11) SIAM Journal on Control and Optimization       (Followers: 18) SIAM Journal on Discrete Mathematics       (Followers: 8) SIAM Journal on Financial Mathematics       (Followers: 3) SIAM Journal on Mathematics of Data Science       (Followers: 1) SIAM Journal on Matrix Analysis and Applications       (Followers: 3) SIAM Journal on Optimization       (Followers: 12) Siberian Advances in Mathematics Siberian Mathematical Journal Sigmae SILICON SN Partial Differential Equations and Applications Soft Computing       (Followers: 7) Statistics and Computing       (Followers: 13) Stochastic Analysis and Applications       (Followers: 2) Stochastic Partial Differential Equations : Analysis and Computations       (Followers: 1) Stochastic Processes and their Applications       (Followers: 5) Stochastics and Dynamics Studia Scientiarum Mathematicarum Hungarica       (Followers: 1) Studia Universitatis Babeș-Bolyai Informatica Studies In Applied Mathematics       (Followers: 1) Studies in Mathematical Sciences       (Followers: 1) Superficies y vacio Suska Journal of Mathematics Education       (Followers: 1) Swiss Journal of Geosciences       (Followers: 1) Synthesis Lectures on Algorithms and Software in Engineering       (Followers: 2) Synthesis Lectures on Mathematics and Statistics       (Followers: 1) Tamkang Journal of Mathematics Tatra Mountains Mathematical Publications Teaching Mathematics       (Followers: 10) Teaching Mathematics and its Applications: An International Journal of the IMA       (Followers: 4) Teaching Statistics       (Followers: 8) Technometrics       (Followers: 8) The Journal of Supercomputing       (Followers: 1) The Mathematica journal The Mathematical Gazette       (Followers: 1) The Mathematical Intelligencer The Ramanujan Journal The VLDB Journal       (Followers: 2) Theoretical and Mathematical Physics       (Followers: 7) Theory and Applications of Graphs Topological Methods in Nonlinear Analysis Transactions of the London Mathematical Society       (Followers: 1) Transformation Groups Turkish Journal of Mathematics Ukrainian Mathematical Journal Uniciencia Uniform Distribution Theory Unisda Journal of Mathematics and Computer Science Unnes Journal of Mathematics       (Followers: 2) Unnes Journal of Mathematics Education       (Followers: 2) Unnes Journal of Mathematics Education Research       (Followers: 1) Ural Mathematical Journal Vestnik Samarskogo Gosudarstvennogo Tekhnicheskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki Vestnik St. Petersburg University: Mathematics VFAST Transactions on Mathematics       (Followers: 1) Vietnam Journal of Mathematics Vinculum Visnyk of V. N. Karazin Kharkiv National University. Ser. Mathematics, Applied Mathematics and Mechanics       (Followers: 1) Water SA       (Followers: 2) Water Waves Zamm-Zeitschrift Fuer Angewandte Mathematik Und Mechanik       (Followers: 1) ZDM       (Followers: 2) Zeitschrift für angewandte Mathematik und Physik       (Followers: 2) Zeitschrift fur Energiewirtschaft Zetetike

First | 1 2 3 4

Similar Journals
 SIAM Journal on Discrete MathematicsJournal Prestige (SJR): 0.863 Citation Impact (citeScore): 1Number of Followers: 8      Hybrid journal (It can contain Open Access articles) ISSN (Print) 0895-4801 - ISSN (Online) 1095-7146 Published by Society for Industrial and Applied Mathematics  [17 journals]

Authors: Karl Däubel
Pages: 867 - 887
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 867-887, June 2022.
The ring loading problem emerged in the 1990s to model an important special case of telecommunication networks (synchronous optical network rings) which gained attention from practitioners and theorists alike. Given an undirected cycle on $n$ nodes together with nonnegative demands between any pair of nodes, the ring loading problem asks for an unsplittable routing of the demands such that the maximum cumulated demand on any edge is minimized. Let $L$ be the value of such a solution. In the relaxed version of the problem, each demand can be split into two parts where the first part is routed clockwise while the second part is routed counterclockwise. Denote with $L^*$ the maximum load of a minimum split routing solution. In a landmark paper, Schrijver, Seymour, and Winkler [SIAM J. Discrete Math., 11 (1998), pp. 1--14] showed that $L \leq L^* + \frac{3}{2}D$, where $D$ is the maximum demand value. They also found (implicitly) an instance of the ring loading problem with $L = L^* + \frac{101}{100}D$. Recently, Skutella [SIAM J. Discrete Math., 30 (2016), pp. 327--342] improved these bounds by showing that $L \leq L^* + \frac{19}{14}D$, and there exists an instance with $L = L^* + \frac{11}{10}D$. We contribute to this line of research by showing that $L \leq L^* + \frac{13}{10}D$. We also take a first step toward lower and upper bounds for small instances.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-07T07:00:00Z
DOI: 10.1137/20M1319395
Issue No: Vol. 36, No. 2 (2022)

• The Multivariate Schwartz--Zippel Lemma

Authors: M. Levent Doğan, Alperen A. Ergür, Jake D. Mundo, Elias Tsigaridas
Pages: 888 - 910
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 888-910, June 2022.
Motivated by applications in combinatorial geometry, we consider the following question: Let $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_m)$ be an $m$-partition of a positive integer $n$, $S_i \subseteq \mathbb{C}^{\lambda_i}$ be finite sets, and let $S:=S_1 \times S_2 \times \cdots \times S_m \subset \mathbb{C}^n$ be the multigrid defined by $S_i$. Suppose $p$ is an $n$-variate degree $d$ polynomial. How many zeros does $p$ have on $S$' We first develop a multivariate generalization of the combinatorial nullstellensatz that certifies existence of a point $t \in S$ so that $p(t) \neq 0$. Then we show that a natural multivariate generalization of the DeMillo--Lipton--Schwartz--Zippel lemma holds, except for a special family of polynomials that we call $\lambda$-reducible. This yields a simultaneous generalization of the Szemerédi--Trotter theorem and the Schwartz--Zippel lemma into higher dimensions, and has applications in incidence geometry. Finally, we develop a symbolic algorithm that identifies certain $\lambda$-reducible polynomials. More precisely, our symbolic algorithm detects polynomials that include a Cartesian product of hypersurfaces in their zero set. It is likely that using Chow forms the algorithm can be generalized to handle arbitrary $\lambda$-reducible polynomials, which we leave as an open problem.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-07T07:00:00Z
DOI: 10.1137/20M1333869
Issue No: Vol. 36, No. 2 (2022)

• A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded
Degree Graphs

Authors: Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
Pages: 911 - 921
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 911-921, June 2022.
In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [Algorithmica, 75 (2016), pp. 363--382] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most $k$ to any minor-closed class of graphs is fixed-parameter tractable parameterized by $k$ [Algorithmica, 79 (2017), pp. 139--158]. They showed that graph isomorphism parameterized by the elimination distance to bounded degree graphs is fixed-parameter tractable and asked whether determining the elimination distance to the class of bounded degree graphs is fixed-parameter tractable. Recently, Lindermayr, Siebertz, and Vigny [MFCS 2020, LIPIcs Leibniz Int. Proc. Inform. 170, Wadern Germany, 2020, 65] obtained a fixed-parameter algorithm for this problem in the special case where the input is restricted to $K_5$-minor free graphs. In this paper, we answer the question of Bulian and Dawar in the affirmative for general graphs. In fact, we give a more general result capturing elimination distance to any graph class characterized by a finite set of graphs as forbidden induced subgraphs.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-07T07:00:00Z
DOI: 10.1137/21M1396824
Issue No: Vol. 36, No. 2 (2022)

• Constant Congestion Brambles in Directed Graphs

Authors: Tomáš Masařík, Marcin Pilipczuk, Paweł Rzaͅżewski, Manuel Sorge
Pages: 922 - 938
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 922-938, June 2022.
The Directed Grid Theorem, stating that there is a function $f$ such that a directed graph of directed treewidth at least $f(k)$ contains a directed grid of size at least $k$ as a butterfly minor, after being a conjecture for nearly 20 years, was proved in 2015 by Kawarabayashi and Kreutzer. However, the function $f$ obtained in the proof is very fast growing. In this work, we show that if one relaxes directed grid to bramble of constant congestion, one can obtain a polynomial bound. More precisely, we show that for every $k \geq 1$ there exists $t = \mathcal{O}(k^{48} \log^{13} k)$ such that every directed graph of directed treewidth at least $t$ contains a bramble of congestion at most 8 and size at least $k$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-07T07:00:00Z
DOI: 10.1137/21M1417661
Issue No: Vol. 36, No. 2 (2022)

• Maximizing Line Subgraphs of Diameter at Most t

Authors: Stijn Cambie, Wouter Cames van Batenburg, Rémi de Joannis de Verclos, Ross J. Kang
Pages: 939 - 950
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 939-950, June 2022.
We wish to bring attention to a natural but slightly hidden problem, posed by Erdös and Nešetřil in the late 1980s, an edge version of the degree--diameter problem. Our main result is that, for any graph of maximum degree $\Delta$ with more than $1.5 \Delta^t$ edges, its line graph must have diameter larger than $t$. In the case where the graph contains no cycle of length $2t+1$, we can improve the bound on the number of edges to one that is exact for $t\in\{1,2,3,4,6\}$. In the case $\Delta=3$ and $t=3$, we obtain an exact bound. Our results also have implications for the related problem of bounding the distance-$t$ chromatic index, $t>2$; in particular, for this, we obtain an upper bound of $1.941\Delta^t$ for graphs of large enough maximum degree $\Delta$, markedly improving on earlier bounds for this parameter.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-11T07:00:00Z
DOI: 10.1137/21M1437354
Issue No: Vol. 36, No. 2 (2022)

• A Quantitative Helly-Type Theorem: Containment in a Homothet

Authors: Grigory Ivanov, Márton Naszódi
Pages: 951 - 957
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 951-957, June 2022.
We introduce a new variant of quantitative Helly-type theorems: the minimal homothetic distance of the intersection of a family of convex sets to the intersection of a subfamily of a fixed size. As an application, we establish the following quantitative Helly-type result for the diameter. If $K$ is the intersection of finitely many convex bodies in $\mathbb{R}^d$, then one can select $2d$ of these bodies whose intersection is of diameter at most $(2d)^3{diam}(K)$. The best previously known estimate, due to Brazitikos [Bull. Hellenic Math. Soc., 62 (2018), pp. 19--25], is $c d^{11/2}$. Moreover, we confirm that the multiplicative factor $c d^{1/2}$ conjectured by Bárány, Katchalski, and Pach [Proc. Amer. Math. Soc., 86 (1982), pp. 109--114] cannot be improved. The bounds above follow from our key result that concerns sparse approximation of a convex polytope by the convex hull of a well-chosen subset of its vertices: Assume that $Q \subset {\mathbb R}^d$ is a polytope whose centroid is the origin. Then there exist at most 2d vertices of $Q$ whose convex hull $Q^{\prime \prime}$ satisfies $Q \subset - 8d^3 Q^{\prime \prime}.$
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-11T07:00:00Z
DOI: 10.1137/21M1403308
Issue No: Vol. 36, No. 2 (2022)

• Counting and Cutting Rich Lenses in Arrangements of Circles

Authors: Esther Ezra, Orit E. Raz, Micha Sharir, Joshua Zahl
Pages: 958 - 974
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 958-974, June 2022.
We show that the maximum number of pairwise nonoverlapping $k$-rich lenses (lenses formed by at least $k$ circles) in an arrangement of $n$ circles in the plane is $O(n^{3/2}\log(n / k^3)/k^{5/2} + n/k)$, and the sum of the degrees of the lenses of such a family (where the degree of a lens is the number of circles that form it) is $O(n^{3/2}\log(n/k^3)/k^{3/2} + n)$. Two independent proofs of these bounds are given, each interesting in its own right (so we believe). The second proof gives a bound that is weaker by a polylogarithmic factor. We then show that these bounds lead to the known bound of Agarwal et al. [J. ACM, 51 (2004), pp. 139--186] and Marcus and Tardos [J. Combin. Theory Ser. A, 113 (2006), pp. 675--691] on the number of point-circle incidences in the plane. Extensions to families of more general algebraic curves and some other related problems are also considered.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-11T07:00:00Z
DOI: 10.1137/21M1409305
Issue No: Vol. 36, No. 2 (2022)

• Invariant Chains in Algebra and Discrete Geometry

Authors: Thomas Kahle, Dinh Van Le, Tim Römer
Pages: 975 - 999
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 975-999, June 2022.
We relate finite generation of cones, monoids, and ideals in increasing chains (the local situation) to equivariant finite generation of the corresponding limit objects (the global situation). For cones and monoids, there is no analog of Noetherianity as in the case of ideals, and we demonstrate this in examples. As a remedy we find local-global correspondences for finite generation. These results are derived from a more general framework that relates finite generation under closure operations to equivariant finite generation under general families of maps. We also give a new proof that nonsaturated Inc-invariant chains of ideals stabilize, closing a gap in the literature.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-14T07:00:00Z
DOI: 10.1137/20M1385652
Issue No: Vol. 36, No. 2 (2022)

• Spectral Radius on Linear $r$-Graphs without Expanded $K_{r+1}$

Authors: Guorong Gao, An Chang, Yuan Hou
Pages: 1000 - 1011
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1000-1011, June 2022.
An $r$-uniform hypergraph is linear if every two edges intersect in at most one vertex. Let $K_{r+1}$ be a complete graph with $r+1$ vertices. The $r$-uniform hypergraph $K_{r+1}^+$ is obtained from $K_{r+1}$ by enlarging each edge of $K_{r+1}$ with $r-2$ new vertices disjoint from $V(K_{r+1})$ such that distinct edges of $K_{r+1}$ are enlarged by distinct vertices. Let $H$ be a $K_{r+1}^+$-free linear $r$-uniform hypergraph with $n$ vertices. In this paper, we prove that when $n$ is sufficiently large, the spectral radius $\rho (H)$ of the adjacency tensor of $H$ is no more than $\frac{n}{r}$, i.e., $\rho (H)\leq \frac{n}{r}$, with equality if and only if $r n$ and $H$ is a transversal design, where the transversal design is the balanced $r$-partite $r$-uniform hypergraph such that each pair of vertices from distinct parts is contained in one hyperedge exactly. An immediate corollary of this result is that $ex_r^{lin}(n,K_{r+1}^+)= \frac{n^2}{r^2}$ for sufficiently large $n$ and $r n$, where $ex_r^{lin}(n,K_{r+1}^+)$ is the maximum number of edges of an $n$-vertex $K_{r+1}^+$-free linear $r$-uniform hypergraph, i.e., the linear Turán number of $K_{r+1}^+$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-14T07:00:00Z
DOI: 10.1137/21M1404740
Issue No: Vol. 36, No. 2 (2022)

• Clean Clutters and Dyadic Fractional Packings

Authors: Ahmad Abdi, Gérard Cornuéjols, Bertrand Guenin, Levent Tunçel
Pages: 1012 - 1037
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1012-1037, June 2022.
A vector is dyadic if each of its entries is a dyadic rational number, i.e., an integer multiple of $\frac{1}{2^k}$ for some nonnegative integer $k$. We prove that every clean clutter with a covering number of at least two has a dyadic fractional packing of value two. This result is best possible, for there exist clean clutters with a covering number of three and no dyadic fractional packing of value three. Examples of clean clutters include ideal clutters, binary clutters, and clutters without an intersecting minor. Our proof is constructive and leads naturally to an (albeit exponential) algorithm. We improve the running time to quasi-polynomial in the rank of the input and to polynomial in the binary case.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-19T07:00:00Z
DOI: 10.1137/21M1397325
Issue No: Vol. 36, No. 2 (2022)

• A Degree Sequence Strengthening of the Vertex Degree Threshold for a
Perfect Matching in 3-Uniform Hypergraphs

Authors: Candida Bowtell, Joseph Hyde
Pages: 1038 - 1063
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1038-1063, June 2022.
The study of asymptotic minimum degree thresholds that force matchings and tilings in hypergraphs is a lively area of research in combinatorics. A key breakthrough in this area was a result of Hàn, Person, and Schacht [SIAM J. Disc. Math., 23 (2009), pp. 732--748] who proved that the asymptotic minimum vertex degree threshold for a perfect matching in an $n$-vertex $3$-graph is $\left(\frac{5}{9}+o(1)\right)\binom{n}{2}$. In this paper, we improve on this result, giving a family of degree sequence results, all of which imply the result of Hàn, Person and Schacht and additionally allow one-third of the vertices to have degree $\frac{1}{9}\binom{n}{2}$ below this threshold. Furthermore, we show that this result is, in some sense, tight.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-19T07:00:00Z
DOI: 10.1137/20M1364825
Issue No: Vol. 36, No. 2 (2022)

• Multiplicative Properties of Hilbert Cubes

Authors: Igor E. Shparlinski
Pages: 1064 - 1070
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1064-1070, June 2022.
We obtain upper bounds on the cardinality of Hilbert cubes in finite fields, which avoid large product sets and reciprocals of sum sets. In particular, our results replace recent estimates of N. Hegyvári and P. P. Pach [J. Number Theory, 217 (2020), pp. 292--300], which appear to be void for all admissible parameters. Our approach is different from that of Hegyvári and Pach and is based on some well-known bounds of double character and exponential sums over arbitrary sets, due to A. A. Karatsuba [Dokl. Akad. Nauk SSSR, 319 (1991), pp. 543--545] and N. G. Moshchevitin [Mat. Sb., 198 (2007), pp. 95--116]), respectively.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-19T07:00:00Z
DOI: 10.1137/22M1470396
Issue No: Vol. 36, No. 2 (2022)

• Anticoncentration and the Exact Gap-Hamming Problem

Authors: Anup Rao, Amir Yehudayoff
Pages: 1071 - 1092
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1071-1092, June 2022.
We prove anticoncentration bounds for the inner product of two independent random vectors and use these bounds to prove lower bounds in communication complexity. We show that if $A,B$ are subsets of the cube $\{\pm 1\}^n$ with $A \cdot B \geq 2^{1.01 n}$, and $X \in A$ and $Y \in B$ are sampled independently and uniformly, then the inner product $\langle{X},{Y}\rangle$ takes on any fixed value with probability at most $O(1/\sqrt{n})$. In fact, we prove the following stronger “smoothness" statement: $\max_{k } \big \Pr[\langle{X},{Y}\rangle = k] - \Pr[\langle{X},{Y}\rangle = k+4]\big \leq O(1/n).$ We use these results to prove that the exact gap-hamming problem requires linear communication, resolving an open problem in communication complexity. We also conclude anticoncentration for structured distributions with low entropy. If $x \in \mathbb{Z}^n$ has no zero coordinates, and $B \subseteq \{\pm 1\}^n$ corresponds to a subspace of $\mathbb{F}_2^n$ of dimension $0.51n$, then $\max_k \Pr[\langle{x},{Y}\rangle = k] \leq O(\sqrt{\ln (n)/n})$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-21T07:00:00Z
DOI: 10.1137/21M1435288
Issue No: Vol. 36, No. 2 (2022)

• On the Cardinality of Sets in $R^d$ Obeying a Slightly Obtuse Angle Bound

Authors: Tongseok Lim, Robert J. McCann
Pages: 1093 - 1101
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1093-1101, June 2022.
In this paper, we explicitly estimate the number of points in a subset $A \subset R^{d}$ as a function of the maximum angle $\angle A$ that any three of these points form, provided $\angle A < \theta_d := \arccos(-\frac 1 {d}) \in (\pi/2,\pi)$. We also show $\angle A < \theta_d$ ensures that $A$ coincides with the vertex set of a convex polytope. This study is motivated by a question of Paul Erdös and indirectly by a conjecture of László Fejes Tóth.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-27T07:00:00Z
DOI: 10.1137/21M1403163
Issue No: Vol. 36, No. 2 (2022)

• Shortest Reconfiguration of Perfect Matchings via Alternating Cycles

Authors: Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
Pages: 1102 - 1123
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1102-1123, June 2022.
Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-28T07:00:00Z
DOI: 10.1137/20M1364370
Issue No: Vol. 36, No. 2 (2022)

• The $\chi$-Ramsey Problem for Triangle-Free Graphs

Authors: Ewan Davies, Freddie Illingworth
Pages: 1124 - 1134
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1124-1134, June 2022.
In 1967, Erdös asked for the greatest chromatic number, $f(n)$, amongst all $n$-vertex, triangle-free graphs. An observation of Erdös and Hajnal together with Shearer's classical upper bound for the off-diagonal Ramsey number $R(3, t)$ shows that $f(n)$ is at most $(2 \sqrt{2} + o(1)) \sqrt{n/\log n}$. We improve this bound by a factor $\sqrt{2}$, as well as obtaining an analogous bound on the list chromatic number which is tight up to a constant factor. A bound in terms of the number of edges that is similarly tight follows, and these results confirm a conjecture of Cames van Batenburg et al. [Electron. J. Combin., 27 (2020), P2.34].
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-04-28T07:00:00Z
DOI: 10.1137/21M1437573
Issue No: Vol. 36, No. 2 (2022)

• Sets Avoiding Six-Term Arithmetic Progressions in $\mathbb{Z}_6^{n}$ are
Exponentially Small

Authors: Péter Pál Pach, Richárd Palincza
Pages: 1135 - 1142
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1135-1142, June 2022.
We show that sets avoiding six-term arithmetic progressions in $\mathbb{Z}_6^n$ have size at most $5.709^n$. It is also pointed out that the “product construction” does not work in this setting; in particular we show that for the extremal sizes in small dimensions we have $r_6(\mathbb{Z}_6)=5$, $r_6(\mathbb{Z}_6^2)=25$, and $117\leq r_6(\mathbb{Z}_6^n)\leq 124$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-05-05T07:00:00Z
DOI: 10.1137/21M1413766
Issue No: Vol. 36, No. 2 (2022)

• The Degrees of Regular Polytopes of Type [4, 4, 4]

Authors: Maria Elisa Fernandes, Claudio Alexandre Piedade
Pages: 1143 - 1155
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1143-1155, June 2022.
We give a list of all possible degrees of faithful transitive permutation representations, corresponding to the indexes of core-free subgroups, of the finite universal regular polytopes ${{4,4}_{(t_1,t_2)},{4,4}_{(s_1,s_2)}}$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-05-19T07:00:00Z
DOI: 10.1137/20M1375012
Issue No: Vol. 36, No. 2 (2022)

• The Price of Connectivity in Fair Division

Authors: Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, Warut Suksompong
Pages: 1156 - 1186
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1156-1186, June 2022.
We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest multiplicative gap between the graph-specific and the unconstrained maximin share and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-05-19T07:00:00Z
DOI: 10.1137/20M1388310
Issue No: Vol. 36, No. 2 (2022)

• On the Turán Number of the Blow-Up of the Hexagon

Authors: Oliver Janzer, Abhishek Methuku, Zoltán Lóránt Nagy
Pages: 1187 - 1199
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1187-1199, June 2022.
The $r$-blowup of a graph $F$, denoted by $F[r]$, is the graph obtained by replacing the vertices and edges of $F$ with independent sets of size $r$ and copies of $K_{r,r}$, respectively. For bipartite graphs $F$, very little is known about the order of magnitude of the Turán number of $F[r]$. In this paper we prove that ${ex}(n,C_6[2])=O(n^{5/3})$ and, more generally, for any positive integer $t$, ${ex}(n,\theta_{3,t}[2])=O(n^{5/3})$. This is tight when $t$ is sufficiently large.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-05-19T07:00:00Z
DOI: 10.1137/21M1428510
Issue No: Vol. 36, No. 2 (2022)

• On Covering Segments with Unit Intervals

Authors: Dan Bergren, Eduard Eiben, Robert Ganian, Iyad Kanj
Pages: 1200 - 1230
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1200-1230, June 2022.
We study the problem of covering a set of segments on a line with the minimum number of unit-length intervals, where an interval covers a segment if at least one of the two endpoints of the segment falls in the unit interval. We also study several variants of this problem. We show that the restrictions of the aforementioned problems to the set of instances in which all the segments have the same length are NP-hard. This result implies several NP-hardness results in the literature for variants and generalizations of the problems under consideration. We then study the parameterized complexity of the aforementioned problems. We provide tight results for most of them by showing that they are fixed-parameter tractable for the restrictions in which all the segments have the same length, and are W[1]-complete otherwise.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-05-23T07:00:00Z
DOI: 10.1137/20M1336412
Issue No: Vol. 36, No. 2 (2022)

• 2-Modular Matrices

Authors: James Oxley, Zach Walsh
Pages: 1231 - 1248
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1231-1248, June 2022.
An integer matrix $A$ is $\Delta$-modular if the determinant of each $rank(A) \times rank(A)$ submatrix has absolute value at most $\Delta$. The class of 1-modular, or unimodular, matrices is of fundamental significance in both integer programming theory and matroid theory. A 1957 result of Heller shows that the maximum number of nonzero, pairwise non-parallel columns of a rank-$r$ unimodular matrix is ($r + 1 \atop 2$). We prove that, for each sufficiently large integer $r$, the maximum number of nonzero, pairwise non-parallel columns of a rank-$r$ 2-modular matrix is ($r + 2 \atop 2$)$- 2$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-05-23T07:00:00Z
DOI: 10.1137/21M1419131
Issue No: Vol. 36, No. 2 (2022)

• Percolation on Random Graphs with a Fixed Degree Sequence

Authors: Nikolaos Fountoulakis, Felix Joos, Guillem Perarnau
Pages: 1 - 46
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 1-46, January 2022.
We consider bond percolation on random graphs with given degrees and bounded average degree. In particular, we consider the order of the largest component after the random deletion of the edges of such a random graph. We give a rough characterization of those degree distributions for which bond percolation with high probability leaves a component of linear order, known usually as a giant component. We show that essentially the critical condition has to do with the tail of the degree distribution. Our proof makes use of recent technique which is based on the switching method and avoids the use of the classic configuration model on degree sequences that have a limiting distribution. Thus our results hold for sparse degree sequences without the usual restrictions that accompany the configuration model.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-01-04T08:00:00Z
DOI: 10.1137/20M1347607
Issue No: Vol. 36, No. 1 (2022)

• An Evans-Style Result for Block Designs

Authors: Ajani De Vas Gunasekara, Daniel Horsley
Pages: 47 - 63
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 47-63, January 2022.
For positive integers $n$ and $k$ with $n \geq k$, an $(n,k,1)$-design is a pair $(V, \mathcal{B})$, where $V$ is a set of $n$ points and $\mathcal{B}$ is a collection of $k$-subsets of $V$ called blocks such that each pair of points occur together in exactly one block. If we weaken this condition to demand only that each pair of points occur together in at most one block, then the resulting object is a partial $(n,k,1)$-design. A completion of a partial $(n,k,1)$-design $(V,\mathcal{A})$ is a (complete) $(n,k,1)$-design $(V,\mathcal{B})$ such that $\mathcal{A} \subseteq \mathcal{B}$. Here, for all sufficiently large $n$, we determine exactly the minimum number of blocks in an uncompletable partial $(n,k,1)$-design. This result is reminiscent of Evans' now-proved conjecture on completions of partial Latin squares. We also prove some related results concerning edge decompositions of almost complete graphs into copies of $K_k$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-01-04T08:00:00Z
DOI: 10.1137/20M1373219
Issue No: Vol. 36, No. 1 (2022)

• Computing the Tandem Duplication Distance is NP-Hard

Authors: Manuel Lafond, Binhai Zhu, Peng Zou
Pages: 64 - 91
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 64-91, January 2022.
In computational biology, tandem duplication is an important biological phenomenon which can occur either at the genome or at the DNA level. A tandem duplication takes a copy of a genome segment and inserts it right after the segment---this can be represented as the string operation $AXB \Rightarrow AXXB$. Tandem exon duplications have been found in many species such as human, fly, and worm and have been largely studied in computational biology. The tandem duplication (TD) distance problem we investigate in this paper is defined as follows: given two strings $S$ and $T$ over the same alphabet $\Sigma$, compute the smallest sequence of TDs required to convert $S$ to $T$. The natural question of whether the TD distance can be computed in polynomial time was posed in 2004 by Leupold et al. and had remained open, despite the fact that TDs have received much attention ever since. In this paper, we focus on the special case when all characters of $S$ are distinct. This is known as the exemplar TD distance, which is of special relevance in bioinformatics. We first prove that this problem is NP-hard when the alphabet size is unbounded, settling the 16-year-old open problem. We then show how to adapt the proof to $\Sigma =4$, hence proving the NP-hardness of the TD problem for any $\Sigma \geq 4$. One of the tools we develop for the reduction is a new problem called Cost-Effective Subgraph, for which we obtain W[1]-hardness results that might be of independent interest. We finally show that computing the exemplar TD distance between $S$ and $T$ is fixed-parameter tractable. Our results open the door to many other questions, and we conclude with several open problems.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-01-04T08:00:00Z
DOI: 10.1137/20M1356257
Issue No: Vol. 36, No. 1 (2022)

• Lattice Size of Plane Convex Bodies

Authors: Anthony Harrison, Jenya Soprunova, Patrick Tierney
Pages: 92 - 102
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 92-102, January 2022.
The lattice size $\operatorname{ls_\Delta}(P)$ of a lattice polygon $P$ with respect to the standard simplex $\Delta$ was introduced and studied by Castryck and Cools in the context of simplification of the defining equation of an algebraic curve. Earlier, Schicho provided an “onion skins” algorithm for mapping a lattice polygon $P$ into a small integer multiple of the standard simplex, based on passing successively to the convex hull of the interior lattice points of $P$. Castryck and Cools showed that this algorithm computes the lattice size of $P$. In this paper we show that for a plane convex body $P$ a reduced basis of $\mathbb Z^2$ computes the lattice size. This provides a lattice reduction algorithm for computing the lattice size, which works for any convex body $P\subset\mathbb R^2$ and outperforms the “onion skins” algorithm in the case when $P$ is a lattice polygon.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-01-04T08:00:00Z
DOI: 10.1137/20M137536X
Issue No: Vol. 36, No. 1 (2022)

• Ramsey Numbers for Nontrivial Berge Cycles

Authors: Jiaxi Nie, Jacques Verstraëte
Pages: 103 - 113
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 103-113, January 2022.
In this paper, we consider an extension of cycle-complete graph Ramsey numbers to Berge cycles in hypergraphs: for $k \geq 2$, a nontrivial Berge $k$-cycle is a family of sets $e_1,e_2,\dots,e_k$ such that $e_1 \cap e_2, e_2 \cap e_3,\dots,e_k \cap e_1$ has a system of distinct representatives and $e_1 \cap e_2 \cap \dots \cap e_k = \emptyset$. In the case that all the sets $e_i$ have size three, let $\mathcal{B}_k$ denote the family of all nontrivial Berge $k$-cycles. The Ramsey numbers $R(t,\mathcal{B}_k)$ denote the minimum $n$ such that every $n$-vertex 3-uniform hypergraph contains either a nontrivial Berge $k$-cycle or an independent set of size $t$. We prove $R(t, \mathcal{B}_{2k}) \leq t^{1 + \frac{1}{2k-1} + \frac{2}{\sqrt{\log t}}}$, and moreover, we show that if a conjecture of Erdös and Simonovits [Combinatorica, 2 (1982), pp. 275--288] on girth in graphs is true, then this is tight up to a factor $t^{o(1)}$ as $t \rightarrow \infty$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-01-04T08:00:00Z
DOI: 10.1137/21M1396770
Issue No: Vol. 36, No. 1 (2022)

• A Note on Seminormality of Cut Polytopes

Authors: Michał Lasoń, Mateusz Michałek
Pages: 114 - 117
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 114-117, January 2022.
We prove that seminormality of cut polytopes is equivalent to normality.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-01-04T08:00:00Z
DOI: 10.1137/20M138586X
Issue No: Vol. 36, No. 1 (2022)

• Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices

Authors: Georgios Amanatidis, Pieter Kleer
Pages: 118 - 146
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 118-146, January 2022.
The switch Markov chain has been extensively studied as the most natural Markov chain Monte Carlo approach for sampling graphs with prescribed degree sequences. In this work we study the problem of uniformly sampling graphs for which, in addition to the degree sequence, joint degree constraints are given. These constraints specify how many edges there should be between two given degree classes (i.e., subsets of nodes that all have the same degree). Although the problem was formalized over a decade ago, and despite its practical significance in generating synthetic network topologies, small progress has been made on the random sampling of such graphs. In the case of one degree class, the problem reduces to the sampling of regular graphs (i.e., graphs in which all nodes have the same degree), but beyond this very little is known. We fully resolve the case of two degree classes, by showing that the switch Markov chain is always rapidly mixing. We do this by combining a recent embedding argument developed by the authors in combination with ideas of Bhatnagar et al. [Algorithmica, 50 (2008), pp. 418--445] introduced in the context of sampling bichromatic matchings.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-01-06T08:00:00Z
DOI: 10.1137/20M1352697
Issue No: Vol. 36, No. 1 (2022)

• Localized Codegree Conditions for Tight Hamilton Cycles in 3-Uniform
Hypergraphs

Authors: Pedro Araújo, Simón Piga, Mathias Schacht
Pages: 147 - 169
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 147-169, January 2022.
We study sufficient conditions for the existence of Hamilton cycles in uniformly dense 3-uniform hypergraphs. Problems of this type were first considered by Lenz, Mubayi, and Mycroft for loose Hamilton cycles, and Aigner-Horev and Levy considered them for tight Hamilton cycles for a fairly strong notion of uniformly dense hypergraphs. We focus on tight cycles and obtain optimal results for a weaker notion of uniformly dense hypergraphs. We show that if an $n$-vertex 3-uniform hypergraph $H=(V,E)$ has the property that for any set of vertices $X$ and for any collection $P$ of pairs of vertices, the number of hyperedges composed by a pair belonging to $P$ and one vertex from $X$ is at least $(1/4+o(1)) X P - o( V ^3)$ and $H$ has minimum vertex degree at least $\Omega( V ^2)$, then $H$ contains a tight Hamilton cycle. A probabilistic construction shows that the constant 1/4 is optimal in this context.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-01-06T08:00:00Z
DOI: 10.1137/21M1408531
Issue No: Vol. 36, No. 1 (2022)

• Pure Pairs VI: Excluding an Ordered Tree

Authors: Alex Scott, Paul Seymour, Sophie Spirkl
Pages: 170 - 187
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 170-187, January 2022.
A pure pair in a graph $G$ is a pair $(Z_1,Z_2)$ of disjoint sets of vertices such that either every vertex in $Z_1$ is adjacent to every vertex in $Z_2$, or there are no edges between $Z_1$ and $Z_2$. With Maria Chudnovsky, we recently proved that, for every forest $F$, every graph $G$ with at least two vertices that does not contain $F$ or its complement as an induced subgraph has a pure pair $(Z_1,Z_2)$ with $Z_1 , Z_2$ linear in $G$. Here we investigate what we can say about pure pairs in an ordered graph $G$, when we exclude an ordered forest $F$ and its complement as induced subgraphs. Fox showed that there need not be a linear pure pair; but Pach and Tomon showed that if $F$ is a monotone path, then there is a pure pair of size $c G /\log G$. We generalize this to all ordered forests, at the cost of a slightly worse bound: we prove that, for every ordered forest $F$, every ordered graph $G$ with at least two vertices that does not contain $F$ or its complement as an induced subgraph has a pure pair of size $G ^{1-o(1)}$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-01-06T08:00:00Z
DOI: 10.1137/20M1368331
Issue No: Vol. 36, No. 1 (2022)

• Understanding Popular Matchings via Stable Matchings

Authors: Ágnes Cseh, Yuri Faenza, Telikepalli Kavitha, Vladlena Powers
Pages: 188 - 213
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 188-213, January 2022.
An instance of the marriage problem is given by a graph $G = (A \cup B,E)$, together with, for each vertex of $G$, a strict preference order over its neighbors. A matching $M$ of $G$ is popular in the marriage instance if $M$ does not lose a head-to-head election against any matching where vertices are voters. Every stable matching is a min-size popular matching; another subclass of popular matchings that always exists and can be easily computed is the set of dominant matchings. A popular matching $M$ is dominant if $M$ wins the head-to-head election against any larger matching. Thus, every dominant matching is a max-size popular matching, and it is known that the set of dominant matchings is the linear image of the set of stable matchings in an auxiliary graph. Results from the literature seem to suggest that stable and dominant matchings behave, from a complexity theory point of view, in a very similar manner within the class of popular matchings. The goal of this paper is to show that there are instead differences in the tractability of stable and dominant matchings and to investigate further their importance for popular matchings. First, we show that it is easy to check if all popular matchings are also stable; however, it is co-NP hard to check if all popular matchings are also dominant. Second, we show how some new and recent hardness results on popular matching problems can be deduced from the NP-hardness of certain problems on stable matchings, also studied in this paper, thus showing that stable matchings can be employed to show not only positive results on popular matchings (as is known) but also most negative ones. Problems for which we show new hardness results include finding a min-size (resp., max-size) popular matching that is not stable (resp., dominant). A known result for which we give a new and simple proof is the NP-hardness of finding a popular matching when $G$ is nonbipartite.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-01-10T08:00:00Z
DOI: 10.1137/19M124770X
Issue No: Vol. 36, No. 1 (2022)

• On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs

Authors: Martin Balko, Máté Vizer
Pages: 214 - 228
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 214-228, January 2022.
For an integer $k \geq 2$, an ordered $k$-uniform hypergraph $\mathcal{H}=(H, Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-01-10T08:00:00Z DOI: 10.1137/21M1404958 Issue No: Vol. 36, No. 1 (2022) • On the Stability of the Graph Independence Number • Free pre-print version: Loading... Authors: Zichao Dong, Zhuo Wu Pages: 229 - 240 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 229-240, January 2022. Let$G$be a graph on$n$vertices of independence number$\alpha(G)$such that every induced subgraph of$G$on$n-k$vertices has an independent set of size at least$\alpha(G) - \ell$. What is the largest possible$\alpha(G)$in terms of$n$for fixed$k$and$\ell$' We show that$\alpha(G) \le n/2 + C_{k, \ell}$, which is sharp for$k-\ell \le 2$. We also use this result to determine new values of the Erdös--Rogers function. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-01-10T08:00:00Z DOI: 10.1137/21M1405071 Issue No: Vol. 36, No. 1 (2022) • Perfect Matching and Hamilton Tight Cycle Decomposition of Complete$n$-Balanced$r$-Partite$k$-Uniform Hypergraphs • Free pre-print version: Loading... Authors: Zequn Lv, Mei Lu, Yi Zhang Pages: 241 - 251 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 241-251, January 2022. Let$r\ge k\ge 2$and$K_{r,n}^{(k)}$denote the complete$n$-balanced$r$-partite$k$-uniform hypergraph, whose vertex set consists of$r$parts, each has$n$vertices, and whose edge set contains all the$k$-element subsets with no two vertices from one part. A decomposition of$K_{r,n}^{(k)}$is a partition of$E(K_{r,n}^{(k)})$. A perfect matching (resp., Hamilton tight cycle) decomposition of$K_{r,n}^{(k)}$is a decomposition of$K_{r,n}^{(k)}$into perfect matchings (resp., Hamilton tight cycles). In this paper, we prove that if$k\mid n$(resp.,$2\nmid k$and$k\mid n$), then$K_{k+1,n}^{(k)}$(resp.,$K_{k+2,n}^{(k)}$) has a perfect matching decomposition. We also prove that for any integer$k\geq 2$,$K_{k+1,n}^{(k)}$has a Hamilton tight cycle decomposition. In all cases, we use constructive methods involving number theory. In fact, we confirm two conjectures proposed by Zhang, Lu, and Liu [Appl. Math. Comput., 386 (2020), 125492]. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-01-13T08:00:00Z DOI: 10.1137/20M1365557 Issue No: Vol. 36, No. 1 (2022) • The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs • Free pre-print version: Loading... Authors: Sandra Kiefer, Daniel Neuen Pages: 252 - 298 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 252-298, January 2022. The Weisfeiler--Leman procedure is a widely used technique for graph isomorphism testing that works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, a fundamental tool in structural graph theory, which is often exploited in approaches to tackle the graph isomorphism problem, is the decomposition into 2- and 3-connected components. We prove that the two-dimensional Weisfeiler--Leman algorithm implicitly computes the decomposition of a graph into its 3-connected components. This implies that the dimension of the algorithm needed to distinguish two given nonisomorphic graphs is at most the dimension required to distinguish nonisomorphic 3-connected components of the graphs (assuming dimension at least 2). To obtain our decomposition result, we show that, for$k \geq 2$, the$k$-dimensional algorithm distinguishes$k$-separators, i.e.,$k$-tuples of vertices that separate the graph, from other vertex$k$-tuples. As a byproduct, we also obtain insights about the connectivity of constituent graphs of association schemes. In an application of the results, we show the new upper bound of$k$on the Weisfeiler--Leman dimension of the class of graphs of treewidth at most$k$. Using a construction by Cai, Fürer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-01-24T08:00:00Z DOI: 10.1137/20M1314987 Issue No: Vol. 36, No. 1 (2022) • On the Largest Common Subtree of Random Leaf-Labeled Binary Trees • Free pre-print version: Loading... Authors: David J. Aldous Pages: 299 - 314 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 299-314, January 2022. The size of the largest common subtree (maximum agreement subtree) of two independent uniform random binary trees on$n$leaves is known to be between orders$n^{1/8}$and$n^{1/2}$. By a construction based on recursive splitting and analyzable by standard “stochastic fragmentation" methods, we improve the lower bound to order$n^\beta$for$\beta = \frac{\sqrt{3} - 1}{2} = 0.366$. Improving the upper bound remains a challenging problem. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-01-27T08:00:00Z DOI: 10.1137/20M1347504 Issue No: Vol. 36, No. 1 (2022) • Small Doubling in Groups with Moderate Torsion • Free pre-print version: Loading... Authors: Vsevolod F. Lev Pages: 315 - 335 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 315-335, January 2022. We determine the structure of a finite subset$A$of an abelian group given that$ 2A 0$; namely, we show that$A$is contained either in a one-dimensional coset progression of size comparable with$ A $, or in a union of fewer than$\varepsilon^{-1}$cosets of a finite subgroup. The bounds$3(1-\varepsilon) A $and$\varepsilon^{-1}$are best possible in the sense that none of them can be relaxed without tightening another one, and the estimate obtained for the size of the coset progression containing$A$is sharp. In the case where the underlying group is infinite cyclic, our result reduces to the well-known Freiman's$(3n-3)$-theorem; the former thus can be considered as an extension of the latter onto arbitrary abelian groups, provided that there is “not too much torsion involved.” Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-01-31T08:00:00Z DOI: 10.1137/21M1397799 Issue No: Vol. 36, No. 1 (2022) • On the Maximum Agreement Subtree Conjecture for Balanced Trees • Free pre-print version: Loading... Authors: Magnus Bordewich, Simone Linz, Megan Owen, Katherine St. John, Charles Semple, Kristina Wicke Pages: 336 - 354 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 336-354, January 2022. We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labeled trees on$n$leaves have a maximum agreement subtree (MAST) of size at least$n^{\frac{1}{2}}$. In particular, we show that for any$c>0$, there exist two balanced rooted binary leaf-labeled trees on$n$leaves such that any MAST for these two trees has size less than$c n^{\frac{1}{2}}$. We also improve the lower bound of the size of such a MAST to$n^{\frac{1}{6}}$. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-01-31T08:00:00Z DOI: 10.1137/20M1379678 Issue No: Vol. 36, No. 1 (2022) • Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model • Free pre-print version: Loading... Authors: Chien-Chung Huang, Naonori Kakimura, Simon Mauras, Yuichi Yoshida Pages: 355 - 382 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 355-382, March 2022. Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is large gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat$1-\frac{1}{e}$in the single-pass streaming model. Let$n$be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio$2-\sqrt{2}+\varepsilon$requires$\Omega(\frac{n}{K^2})$space for any$\varepsilon>0$, where$K$is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio$\frac{K}{2K-1}+\varepsilon$requires$\Omega(\frac{n}{K^2})$space for any$\varepsilon>0$, where$K$is the rank of the given matroid. In addition, we give streaming algorithms that assume access to the objective function via a weak oracle that can only be used to evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios$\frac{K}{2K-1}$and$\frac{1}{2}$, respectively, whose space complexity is exponential in$K$but is independent of$n$. The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of$\frac{K}{2K-1}$for a matroid constraint, which almost settles the approximation ratio for a matroid constraint that can be obtained by a streaming algorithm whose space complexity is independent of$n$. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-02-08T08:00:00Z DOI: 10.1137/20M1357317 Issue No: Vol. 36, No. 1 (2022) • Tropical Lines on Cubic Surfaces • Free pre-print version: Loading... Authors: Marta Panizzut, Magnus Dehli Vigeland Pages: 383 - 410 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 383-410, March 2022. Given a tropical line$L$and a smooth tropical surface$X$, we look at the position of$L$on$X$. We introduce its primal and dual motifs which are respectively a decorated graph and a subcomplex of the dual triangulation of$X$. They encode the combinatorial position of$L$on$X$. We classify all possible motifs of tropical lines on general smooth tropical surfaces. This classification allows us to give an upper bound for the number of tropical lines on a general smooth tropical surface with a given subdivision. We focus in particular on surfaces of degree three. As a concrete example, we look at tropical cubic surfaces dual to a fixed honeycomb triangulation, showing that a general surface contains exactly$27$tropical lines. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-02-08T08:00:00Z DOI: 10.1137/20M136520X Issue No: Vol. 36, No. 1 (2022) • A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth • Free pre-print version: Loading... Authors: Mamadou M. Kanté, Christophe Paul, Dimitrios M. Thilikos Pages: 411 - 435 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 411-435, March 2022. The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search, where we are given a system of tunnels (represented by a graph) that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy are to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called connected pathwidth. We prove that connected pathwidth is fixed parameter tractable; in particular we design a$2^{O(k^2)}\cdot n$time algorithm that checks whether the connected pathwidth of$G$is at most$k.$This resolves an open question by Dereniowski, Osula, and Rzaͅżewski [Theoret. Comput. Sci., 794 (2019), pp. 85--100]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced by Bodlaender and Kloks [J. Algorithms, 21 (1996), pp. 358--402] for the design of linear parameterized algorithms for treewidth and pathwidth. While this technique has been later applied to other parameters, none of its advancements was able to deal with the connectivity demand, as it is a “global” demand that concerns an unbounded number of parts of the graph of unbounded size. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted to deliver linear parameterized algorithms for the connected variants of other width parameters as well. An immediate consequence of our result is a$2^{O(k^2)}\cdot n$time algorithm for the monotone and connected version of the edge search number. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-02-10T08:00:00Z DOI: 10.1137/20M1369361 Issue No: Vol. 36, No. 1 (2022) • The Generalized Rainbow Turán Problem for Cycles • Free pre-print version: Loading... Authors: Barnabás Janzer Pages: 436 - 448 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 436-448, March 2022. Given an edge-colored graph, we say that a subgraph is rainbow if all of its edges have different colors. Let${\operatorname{ex}}(n,H, {rainbow-}F)$denote the maximal number of copies of$H$that a properly edge-colored graph on$n$vertices can contain if it has no rainbow subgraph isomorphic to$F$. We determine the order of magnitude of${\operatorname{ex}}(n,C_s,{ rainbow-}C_t)$for all$s,t$with$s\not =3$. In particular, we answer a question of Gerbner, Mészáros, Methuku, and Palmer by showing that${\operatorname{ex}}(n,C_{2k}, {rainbow-}C_{2k})$is$\Theta(n^{k-1})$if$k\geq 3$and$\Theta(n^2)$if$k=2$. We also determine the order of magnitude of${\operatorname{ex}}(n,P_\ell,{rainbow-}C_{2k})$for all$k,\ell\geq 2$, where$P_\ell$denotes the path with$\ell$edges. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-02-14T08:00:00Z DOI: 10.1137/20M1351473 Issue No: Vol. 36, No. 1 (2022) • Enumerating Integer Points in Polytopes with Bounded Subdeterminants • Free pre-print version: Loading... Authors: Hongyi Jiang, Amitabh Basu Pages: 449 - 460 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 449-460, March 2022. We show that one can enumerate the vertices of the convex hull of integer points in polytopes whose constraint matrices have bounded and nonzero subdeterminants, in time polynomial in the dimension and encoding size of the polytope. This improves upon a previous result by Artmann et al. who showed that integer linear optimization in such polytopes can be done in polynomial time. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-02-14T08:00:00Z DOI: 10.1137/21M139935X Issue No: Vol. 36, No. 1 (2022) • Three Combinatorial Perspectives on Minimal Codes • Free pre-print version: Loading... Authors: Gianira N. Alfarano, Martino Borello, Alessandro Neri, Alberto Ravagnani Pages: 461 - 489 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 461-489, March 2022. We develop three approaches of combinatorial flavor to study the structure of minimal codes and cutting blocking sets in finite geometry, each of which has a particular application. The first approach uses techniques from algebraic combinatorics, describing the supports in a linear code via the Alon--Füredi theorem and the combinatorial Nullstellensatz. The second approach combines methods from coding theory and statistics to compare the mean and variance of the nonzero weights in a minimal code. Finally, the third approach regards minimal codes as cutting blocking sets and studies these using the theory of spreads in finite geometry. By applying and combining these approaches with each other, we derive several new bounds and constraints on the parameters of minimal codes. Moreover, we obtain two new constructions of cutting blocking sets of small cardinality in finite projective spaces. In turn, these allow us to give explicit constructions of minimal codes having short length for the given field and dimension. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-02-15T08:00:00Z DOI: 10.1137/21M1391493 Issue No: Vol. 36, No. 1 (2022) • Reconstructibility of Matroid Polytopes • Free pre-print version: Loading... Authors: Guillermo Pineda-Villavicencio, Benjamin Schröter Pages: 490 - 508 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 490-508, March 2022. We specify what is meant for a polytope to be reconstructible from its graph or dual graph, and we introduce the problem of class reconstructibility; i.e., the face lattice of the polytope can be determined from the (dual) graph within a given class. We provide examples of cubical polytopes that are not reconstructible from their dual graphs. Furthermore, we show that matroid (base) polytopes are not reconstructible from their graphs and not class reconstructible from their dual graphs; our counterexamples include hypersimplices. Additionally, we prove that matroid polytopes are class reconstructible from their graphs, and we present an$O(n^3)$algorithm that computes the vertices of a matroid polytope from its$n$-vertex graph. Moreover, our proof includes a characterization of all matroids with isomorphic basis exchange graphs. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-02-17T08:00:00Z DOI: 10.1137/21M1401176 Issue No: Vol. 36, No. 1 (2022) • Ample Completions of Oriented Matroids and Complexes of Uniform Oriented Matroids • Free pre-print version: Loading... Authors: Victor Chepoi, Kolja Knauer, Manon Philibert Pages: 509 - 535 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 509-535, March 2022. This paper considers completions of tope graphs of complexes of oriented matroids (COMs) to ample partial cubes of the same Vapnik--Chervonenkis dimension (VC-dimension). We show that these exist for oriented matroids (OMs) and complexes of uniform oriented matroids (CUOMs). This implies that tope graphs of OMs and CUOMs satisfy the sample compression conjecture---one of the central open questions of learning theory. We conjecture that the tope graph of every COM can be completed to an ample partial cube without increasing the VC-dimension. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-02-24T08:00:00Z DOI: 10.1137/20M1355434 Issue No: Vol. 36, No. 1 (2022) • Target Set Selection in Dense Graph Classes • Free pre-print version: Loading... Authors: Pavel Dvořák, Dušan Knop, Tomáš Toufar Pages: 536 - 572 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 536-572, March 2022. In this paper, we study the Target Set Selection problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex, the task is to find a set of vertices (called a target set) that activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold. We give two parameterized algorithms for a special case where each vertex has the threshold set to half of its neighbors (the so-called Majority Target Set Selection problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph. We complement these results from the negative side. We give a hardness proof for the Majority Target Set Selection problem when parameterized by (a restriction of) the modular-width---a natural generalization of both previous structural parameters. We also show the Target Set Selection problem parameterized by the neighborhood diversity or by the twin cover number is \sf W[1]-hard when there is no restriction on the thresholds. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-02-24T08:00:00Z DOI: 10.1137/20M1337624 Issue No: Vol. 36, No. 1 (2022) • A Note on Infinite Antichain Density • Free pre-print version: Loading... Authors: Paul Balister, Emil Powierski, Alex Scott, Jane Tan Pages: 573 - 577 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 573-577, March 2022. Let$\mathcal F$be an antichain of finite subsets of$\mathbb N$. How quickly can the quantities$ \mathcal{F}\cap 2^{[n]} $grow as$n\to\infty$' We show that for any sequence$(f_n)_{n\ge n_0}$of positive integers satisfying$\sum_{n=n_0}^\infty f_n/2^n \le 1/4$and$f_n\le f_{n+1}\le 2f_n$, there exists an infinite antichain$\mathcal{F}$of finite subsets of$\mathbb{N}$such that$ \F\cap 2^{[n]} \geq f_n$for all$n\ge n_0$. It follows that for any$\varepsilon>0$there exists an antichain$\mathcal{F}\subseteq 2^{\mathbb{N}}$such that$\liminf_{n \to \infty} \mathcal{F}\cap 2^{[n]} \cdot \big(\frac{2^n}{n\log^{1+\varepsilon} n}\big)^{-1}> 0.$This resolves a problem of Sudakov, Tomon, and Wagner in a strong form and is essentially tight. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-03-01T08:00:00Z DOI: 10.1137/21M143025X Issue No: Vol. 36, No. 1 (2022) • Digraphs and Variable Degeneracy • Free pre-print version: Loading... Authors: Jørgen Bang-Jensen, Thomas Schweser, Michael Stiebitz Pages: 578 - 595 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 578-595, March 2022. Let$D$be a digraph, let$p \geq 1$be an integer, and let$f: V(D) \to \mathbb{N}_0^p$be a vector function with$f=(f_1,f_2,\ldots,f_p)$. We say that$D$has an$f$-partition if there is a partition$(V_1,V_2,\ldots,V_p)$of the vertex set of$D$such that, for all$i \in [1,p]$, the digraph$D_i=D[V_i]$is weakly$f_i$-degenerate, that is, in every nonempty subdigraph$D'$of$D_i$there is a vertex$v$such that$\min\{d_{D'}^+(v), d_{D'}^-(v)\} < f_i(v)$. In this paper, we prove that the condition$f_1(v) + f_2(v) + \cdots + f_p(v) \geq \max \{d_D^+(v),d_D^-(v)\}$for all$v \in V(D)$is almost sufficient for the existence of an$f$-partition and give a full characterization of the bad pairs$(D,f)$. Among other applications, this leads to a generalization of Brooks' theorem as well as the list-version of Brooks' theorem for digraphs, where a coloring of a digraph is a partition of the digraph into acyclic induced subdigraphs. We furthermore obtain a result bounding the$s$-degenerate chromatic number of a digraph in terms of the maximum of maximum in-degree and maximum out-degree. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-03-03T08:00:00Z DOI: 10.1137/20M1386827 Issue No: Vol. 36, No. 1 (2022) • On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) • Free pre-print version: Loading... Authors: Sushmita Gupta, Saket Saurabh, Meirav Zehavi Pages: 596 - 681 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 596-681, March 2022. Stable Marriage is a fundamental problem to both computer science and economics. Four well-known NP-hard optimization versions of this problem are the Sex-Equal Stable Marriage (SESMI), Balanced Stable Marriage (BSMI), max-Stable Marriage with Ties (max-SMTI), and min-Stable Marriage with Ties (min-SMTI) problems. In this paper, we analyze these problems from the viewpoint of parameterized complexity. We conduct the first study of these problems in particular, and of problems related to Stable Marriage in general, with respect to the parameter treewidth. The motivation behind the choice of treewidth is threefold. First, several problems in social choice theory have already been studied with respect to treewidth. The networks relevant to these problems (say, social networks) are clearly also relevant to Stable Marriage. Thus, the motivation underlying these studies directly extends to our study. Second, empirical studies of the treewidth of several types of networks relevant to Stable Marriage have also already been undertaken, identifying that some of these networks indeed have a treelike structure. Third, treewidth is the most well studied structural parameter in parameterized complexity. We design optimal parameterized algorithms for all four problems under the treewidth of both their primal graphs and rotation digraphs. First, we study the treewidth${\mathtt{tw}}$of the primal graph. We establish that all four problems are W[1]-hard. In particular, while it is easy to show that all four problems admit algorithms that run in time$n^{{\mathcal{O}}({\mathtt{tw}})}$, we prove that unless the exponential-time hypothesis is false, all of these algorithms are optimal. Next, we study the treewidth${\mathtt{tw}}$of the rotation digraph. In this context, max-SMTI and min-SMTI are not defined. For both SESMI and BSMI, we design (highly nontrivial) algorithms that run in time$2^{{\mathtt{tw}}}n^{{\mathcal{O}}(1)}$. Then, for both SESMI and BSMI, we prove that unless the strong exponential-time hypothesis is false, algorithms that run in time$(2-\epsilon)^{{\mathtt{tw}}}n^{{\mathcal{O}}(1)}$do not exist for any fixed$\epsilon>0$. We thus present a comprehensive, complete picture of the behavior of Stable Marriage with respect to treewidth. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-03-09T08:00:00Z DOI: 10.1137/19M130491X Issue No: Vol. 36, No. 1 (2022) • Characteristic Dependence of Syzygies of Random Monomial Ideals • Free pre-print version: Loading... Authors: Caitlyn Booms-Peot, Daniel Erman, Jay Yang Pages: 682 - 701 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 682-701, March 2022. When do syzygies depend on the characteristic of the field' Even for well-studied families of examples, very little is known. For a family of random monomial ideals, namely, the Stanley--Reisner ideals of random flag complexes, we prove that the Betti numbers asymptotically almost always depend on the characteristic. Using this result, we also develop a heuristic for characteristic dependence of asymptotic syzygies of algebraic varieties. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-03-09T08:00:00Z DOI: 10.1137/21M1392474 Issue No: Vol. 36, No. 1 (2022) • Excluded$t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids • Free pre-print version: Loading... Authors: Kenjiro Takazawa Pages: 702 - 727 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 702-727, March 2022. We propose a framework for optimal$t$-matchings excluding prescribed$t$-factors in bipartite graphs. The proposed framework is a generalization of the nonbipartite matching problem and includes several problems, such as the triangle-free 2-matching, square-free 2-matching, even factor, and arborescence problems. In this paper, we demonstrate a unified understanding of these problems by commonly extending previous important results. We solve our problem under a reasonable assumption, which is sufficiently broad to include the specific problems listed above. We first present a min-max theorem and a combinatorial algorithm for the unweighted version. We then provide a linear programming formulation with dual integrality and a primal-dual algorithm for the weighted version. A key ingredient of the proposed algorithm is a technique to shrink forbidden structures, which corresponds to the techniques of shrinking odd cycles, triangles, squares, and directed cycles in Edmonds' blossom algorithm, a triangle-free 2-matching algorithm, a square-free 2-matching algorithm, and an arborescence algorithm, respectively. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-03-14T07:00:00Z DOI: 10.1137/18M1176737 Issue No: Vol. 36, No. 1 (2022) • Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs • Free pre-print version: Loading... Authors: Yahav Alon, Michael Krivelevich Pages: 728 - 754 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 728-754, March 2022. Consider the random subgraph process on a base graph$G$on$n$vertices: a sequence$\lbrace G_t \rbrace _{t=0} ^{ E(G) }$of random subgraphs of$G$obtained by choosing an ordering of the edges of$G$uniformly at random, and by sequentially adding edges to$G_0$, the empty graph on the vertex set of$G$, according to the chosen ordering. We show that if$G$has one of the following properties: 1. there is a positive constant$\varepsilon> 0$such that$\delta (G) \geq \left( \frac{1}{2} + \varepsilon \right) n$; 2. there are some constants$\alpha, \beta>0$such that every two disjoint subsets$U,W$of size at least$\alpha n$have at least$\beta U W $edges between them, and the minimum degree of$G$is at least$(2\alpha + \beta )\cdot n$; or 3.$G$is an$(n,d,\lambda )$-graph, with$d\geq \frac{C\cdot n\cdot \log \log n}{\log n}$and$\lambda \leq \frac{c\cdot d^2}{n}$for some absolute constants$c,C>0;$then for a positive integer constant$k$with high probability the hitting time of the property of containing$k$edge disjoint Hamilton cycles is equal to the hitting time of having minimum degree at least$2k$. These results extend prior results by Johansson and by Frieze and Krivelevich and answer a question posed by Frieze. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-03-14T07:00:00Z DOI: 10.1137/20M1375838 Issue No: Vol. 36, No. 1 (2022) • Regular Graphs with Few Longest Cycles • Free pre-print version: Loading... Authors: Carol T. Zamfirescu Pages: 755 - 776 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 755-776, March 2022. Motivated by work of Haythorpe, Thomassen and the author showed that there exists a positive constant$c$such that there is an infinite family of 4-regular 4-connected graphs, each containing exactly$c$Hamiltonian cycles. We complement this by proving that the same conclusion holds for planar 4-regular 3-connected graphs, although it does not hold for planar 4-regular 4-connected graphs by a result of Brinkmann and Van Cleemput [European J. Combin., 97 (2021), 103395], and that it holds for 4-regular graphs of connectivity 2 with the constant$144 < c$, which we believe to be minimal among all Hamiltonian 4-regular graphs of sufficiently large order. We then disprove a conjecture of Haythorpe by showing that for every nonnegative integer$k$there is a 5-regular graph on$26 + 6k$vertices with$2^{k+10} \cdot 3^{k+3}$Hamiltonian cycles. We prove that for every$d \ge 3$there is an infinite family of Hamiltonian 3-connected graphs with minimum degree$d$, with a bounded number of Hamiltonian cycles. It is shown that if a 3-regular graph$G$has a unique longest cycle$C$, at least two components of$G - E(C)$have an odd number of vertices on$C$, and that there exist 3-regular graphs with exactly two such components. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-03-21T07:00:00Z DOI: 10.1137/21M1414048 Issue No: Vol. 36, No. 1 (2022) • Bounding the Number of Edges of Matchstick Graphs • Free pre-print version: Loading... Authors: Jérémy Lavollée, Konrad J. Swanepoel Pages: 777 - 785 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 777-785, March 2022. A matchstick graph is a crossing-free unit-distance graph in the plane. Harborth conjectured in 1981 that the maximum number of edges of a matchstick graph with$n$vertices is$\lfloor 3n-\sqrt{12n-3}\rfloor$. Using the Euler formula and the isoperimetric inequality, it can be shown that a matchstick graph with$n$vertices has no more than$3n-\sqrt{2\pi\sqrt{3}\cdot n}+O(1)$edges. We improve this upper bound to$3n-c\sqrt{n-1/4}$edges, where$c=\frac12(\sqrt{12} + \sqrt{2\pi\sqrt{3}})$. The main tool in the proof is a new upper bound for the number of edges that takes into account the number of nontriangular faces. We also find a sharp upper bound for the number of triangular faces in a matchstick graph. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-03-24T07:00:00Z DOI: 10.1137/21M1441134 Issue No: Vol. 36, No. 1 (2022) • An Irrational Lagrangian Density of a Single Hypergraph • Free pre-print version: Loading... Authors: Zilong Yan, Yuejian Peng Pages: 786 - 822 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 786-822, March 2022. The Turán number of an$r$-uniform graph$F$, denoted by$ex(n,F)$, is the maximum number of edges in an$F$-free$r$-uniform graph on$n$vertices. The Turán density of$F$is defined as$\pi(F)=\underset{{n\rightarrow\infty}}{\lim}{ex(n,F) \over {n \choose r }}.$Denote$\Pi_{\infty}^{(r)}={ \pi(\cal F): \cal F is a family of r{-uniform graphs}},\Pi_{fin}^{(r)}=\{ \pi(\cal F): \cal F {is a \ finite \ family of} r{{-}uniform graphs}\}$, and$\Pi_{t}^{(r)}=\{\pi(\cal F): \cal F is a family of r{-uniform graphs, and} \cal F \le t}.$For graphs, Erdös and Simonovits [Studia Sci. Mat. Hungar. 1 (1966), pp. 51--57] and Erdös and Stone [Bull. Amer. Math. Soc., 52 (1946), pp. 1087--1091] showed that$\Pi_{\infty}^{(2)}=\Pi_{fin}^{(2)}=\Pi_{1}^{(2)}={0, {1 \over 2}, {2 \over 3}, ...,{l-1 \over l}, ...}.$We know quite little about the Turán density of an$r$-uniform graph for$r\ge 3$. Baber and Talbot [Electron. J. Combin., 19 (2011)] and Pikhurko [Israel J. Math., 20 (2014), pp. 415--454] showed that there is an irrational number in$\Pi_{3}^{(3)}$and$\Pi_{fin}^{(3)}$, respectively, disproving a conjecture of Chung and Graham [Erdös on Graphs: His Legacy of Unsolved Problems, A. K. Peters, Natick, MA, 1999]. Baber and Talbot [Electron. J. Combin., 19 (2011)] asked whether$\Pi_{1}^{(r)}$contains an irrational number. The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. The Lagrangian density of an$r$-uniform graph$F$is$\pi_{\lambda}(F)=\sup \{r! \lambda(G):G\;is;F-free\}$, where$\lambda(G)$is the Lagrangian of an$r$-uniform graph$G$. Sidorenko [Combinatorica, 9 (1989), pp. 207--215] showed that the Lagrangian density of an$r$-uniform hypergraph$F$is the same as the Turán density of the extension of$F$. In this paper, we show that the Lagrangian density of$F={123, 124, 134, 234, 567}$(the disjoint union of$K_4^3$and an edge) is${\sqrt 3\over 3}$, and consequently, the Turán density of the extension of$F$is an irrational number, answering the question of Baber and Talbot. Citation: SIAM Journal on Discrete Mathematics PubDate: 2022-03-29T07:00:00Z DOI: 10.1137/21M1410798 Issue No: Vol. 36, No. 1 (2022) • Computational Complexity of Biased Diffusion-Limited Aggregation • Free pre-print version: Loading... Authors: Nicolas Bitar, Eric Goles, Pedro Montealegre Pages: 823 - 866 Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 823-866, March 2022. Diffusion-limited aggregation (DLA) is a cluster-growth model that consists of a set of particles that are sequentially aggregated over a two-dimensional grid. In this paper, we introduce a biased version of the DLA model, in which particles are limited to moving in a subset of possible directions. We denote by$k$-DLA the model where the particles move only in$k$possible directions. We study the biased DLA model from the perspective of computational complexity, defining two decision problems. The first problem is Prediction, whose input is a site of the grid$c$and a sequence$S$of walks, representing the trajectories of a set of particles. The question is whether a particle stops at site$c$when sequence$S$is realized. The second problem is Realization, where the input is a set of positions of the grid,$P$. The question is whether there exists a sequence$S$that realizes$P$, i.e., all particles of$S$exactly occupy the positions in$P\$. Our aim is to classify the Prediction and Realization problems for the different versions of DLA. We first show that Prediction is P-Complete for 2-DLA (thus for 3-DLA). Later, we show that Prediction can be solved much more efficiently for 1-DLA. In fact, we show that in that case, the problem is NL-Complete. With respect to Realization, we show that when restricted to 2-DLA the problem is in P, while in the 1-DLA case, the problem is in L.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 2022-03-31T07:00:00Z
DOI: 10.1137/18M1215815
Issue No: Vol. 36, No. 1 (2022)

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762