SIAM Journal on Discrete Mathematics
Journal Prestige (SJR): 0.863 Citation Impact (citeScore): 1 Number of Followers: 8 Hybrid journal (It can contain Open Access articles) ISSN (Print) 08954801  ISSN (Online) 10957146 Published by Society for Industrial and Applied Mathematics [17 journals] 
 An Improved Upper Bound for the Ring Loading Problem

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Karl Däubel
Pages: 867  887
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 867887, 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. 114] 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. 327342] 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: 20220407T07:00:00Z
DOI: 10.1137/20M1319395
Issue No: Vol. 36, No. 2 (2022)

 The Multivariate SchwartzZippel Lemma

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 888910, 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 DeMilloLiptonSchwartzZippel lemma holds, except for a special family of polynomials that we call $\lambda$reducible. This yields a simultaneous generalization of the SzemerédiTrotter theorem and the SchwartzZippel 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: 20220407T07:00:00Z
DOI: 10.1137/20M1333869
Issue No: Vol. 36, No. 2 (2022)

 A FixedParameter Tractable Algorithm for Elimination Distance to Bounded
Degree Graphs
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 911921, 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 editdistance 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. 363382] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most $k$ to any minorclosed class of graphs is fixedparameter tractable parameterized by $k$ [Algorithmica, 79 (2017), pp. 139158]. They showed that graph isomorphism parameterized by the elimination distance to bounded degree graphs is fixedparameter tractable and asked whether determining the elimination distance to the class of bounded degree graphs is fixedparameter tractable. Recently, Lindermayr, Siebertz, and Vigny [MFCS 2020, LIPIcs Leibniz Int. Proc. Inform. 170, Wadern Germany, 2020, 65] obtained a fixedparameter 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: 20220407T07:00:00Z
DOI: 10.1137/21M1396824
Issue No: Vol. 36, No. 2 (2022)

 Constant Congestion Brambles in Directed Graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 922938, 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: 20220407T07:00:00Z
DOI: 10.1137/21M1417661
Issue No: Vol. 36, No. 2 (2022)

 Maximizing Line Subgraphs of Diameter at Most t

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 939950, 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 degreediameter 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: 20220411T07:00:00Z
DOI: 10.1137/21M1437354
Issue No: Vol. 36, No. 2 (2022)

 A Quantitative HellyType Theorem: Containment in a Homothet

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Grigory Ivanov, Márton Naszódi
Pages: 951  957
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 951957, June 2022.
We introduce a new variant of quantitative Hellytype 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 Hellytype 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. 1925], 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. 109114] 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 wellchosen 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: 20220411T07:00:00Z
DOI: 10.1137/21M1403308
Issue No: Vol. 36, No. 2 (2022)

 Counting and Cutting Rich Lenses in Arrangements of Circles

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Esther Ezra, Orit E. Raz, Micha Sharir, Joshua Zahl
Pages: 958  974
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 958974, 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. 139186] and Marcus and Tardos [J. Combin. Theory Ser. A, 113 (2006), pp. 675691] on the number of pointcircle 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: 20220411T07:00:00Z
DOI: 10.1137/21M1409305
Issue No: Vol. 36, No. 2 (2022)

 Invariant Chains in Algebra and Discrete Geometry

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Thomas Kahle, Dinh Van Le, Tim Römer
Pages: 975  999
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 975999, 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 localglobal 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 Incinvariant chains of ideals stabilize, closing a gap in the literature.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220414T07:00:00Z
DOI: 10.1137/20M1385652
Issue No: Vol. 36, No. 2 (2022)

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

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Guorong Gao, An Chang, Yuan Hou
Pages: 1000  1011
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 10001011, 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 $r2$ 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: 20220414T07:00:00Z
DOI: 10.1137/21M1404740
Issue No: Vol. 36, No. 2 (2022)

 Clean Clutters and Dyadic Fractional Packings

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 10121037, 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 quasipolynomial in the rank of the input and to polynomial in the binary case.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220419T07: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 3Uniform Hypergraphs
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Candida Bowtell, Joseph Hyde
Pages: 1038  1063
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 10381063, 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. 732748] 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 onethird 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: 20220419T07:00:00Z
DOI: 10.1137/20M1364825
Issue No: Vol. 36, No. 2 (2022)

 Multiplicative Properties of Hilbert Cubes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Igor E. Shparlinski
Pages: 1064  1070
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 10641070, 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. 292300], 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 wellknown bounds of double character and exponential sums over arbitrary sets, due to A. A. Karatsuba [Dokl. Akad. Nauk SSSR, 319 (1991), pp. 543545] and N. G. Moshchevitin [Mat. Sb., 198 (2007), pp. 95116]), respectively.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220419T07:00:00Z
DOI: 10.1137/22M1470396
Issue No: Vol. 36, No. 2 (2022)

 Anticoncentration and the Exact GapHamming Problem

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Anup Rao, Amir Yehudayoff
Pages: 1071  1092
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 10711092, 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 gaphamming 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: 20220421T07: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

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Tongseok Lim, Robert J. McCann
Pages: 1093  1101
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 10931101, 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: 20220427T07:00:00Z
DOI: 10.1137/21M1403163
Issue No: Vol. 36, No. 2 (2022)

 Shortest Reconfiguration of Perfect Matchings via Alternating Cycles

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 11021123, 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 NPhard 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: 20220428T07:00:00Z
DOI: 10.1137/20M1364370
Issue No: Vol. 36, No. 2 (2022)

 The $\chi$Ramsey Problem for TriangleFree Graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Ewan Davies, Freddie Illingworth
Pages: 1124  1134
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 11241134, June 2022.
In 1967, Erdös asked for the greatest chromatic number, $f(n)$, amongst all $n$vertex, trianglefree graphs. An observation of Erdös and Hajnal together with Shearer's classical upper bound for the offdiagonal 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: 20220428T07:00:00Z
DOI: 10.1137/21M1437573
Issue No: Vol. 36, No. 2 (2022)

 Sets Avoiding SixTerm Arithmetic Progressions in $\mathbb{Z}_6^{n}$ are
Exponentially Small
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Péter Pál Pach, Richárd Palincza
Pages: 1135  1142
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 11351142, June 2022.
We show that sets avoiding sixterm 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: 20220505T07:00:00Z
DOI: 10.1137/21M1413766
Issue No: Vol. 36, No. 2 (2022)

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

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Maria Elisa Fernandes, Claudio Alexandre Piedade
Pages: 1143  1155
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 11431155, June 2022.
We give a list of all possible degrees of faithful transitive permutation representations, corresponding to the indexes of corefree 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: 20220519T07:00:00Z
DOI: 10.1137/20M1375012
Issue No: Vol. 36, No. 2 (2022)

 The Price of Connectivity in Fair Division

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, Warut Suksompong
Pages: 1156  1186
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 11561186, 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 wellstudied fairness notions including envyfreeness and maximin share fairness. We introduce the price of connectivity to capture the largest multiplicative gap between the graphspecific 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 envyfreeness 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 envyfreeness up to one good (EF1) for three agents. Our work demonstrates several applications of graphtheoretic tools and concepts to fair division problems.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220519T07:00:00Z
DOI: 10.1137/20M1388310
Issue No: Vol. 36, No. 2 (2022)

 On the Turán Number of the BlowUp of the Hexagon

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 11871199, 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: 20220519T07:00:00Z
DOI: 10.1137/21M1428510
Issue No: Vol. 36, No. 2 (2022)

 On Covering Segments with Unit Intervals

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Dan Bergren, Eduard Eiben, Robert Ganian, Iyad Kanj
Pages: 1200  1230
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 12001230, June 2022.
We study the problem of covering a set of segments on a line with the minimum number of unitlength 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 NPhard. This result implies several NPhardness 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 fixedparameter 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: 20220523T07:00:00Z
DOI: 10.1137/20M1336412
Issue No: Vol. 36, No. 2 (2022)

 2Modular Matrices

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: James Oxley, Zach Walsh
Pages: 1231  1248
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 12311248, 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 1modular, 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 nonparallel 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 nonparallel columns of a rank$r$ 2modular matrix is ($r + 2 \atop 2$)$  2$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220523T07:00:00Z
DOI: 10.1137/21M1419131
Issue No: Vol. 36, No. 2 (2022)

 Percolation on Random Graphs with a Fixed Degree Sequence

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Nikolaos Fountoulakis, Felix Joos, Guillem Perarnau
Pages: 1  46
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 146, 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: 20220104T08:00:00Z
DOI: 10.1137/20M1347607
Issue No: Vol. 36, No. 1 (2022)

 An EvansStyle Result for Block Designs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Ajani De Vas Gunasekara, Daniel Horsley
Pages: 47  63
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 4763, 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' nowproved 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: 20220104T08:00:00Z
DOI: 10.1137/20M1373219
Issue No: Vol. 36, No. 1 (2022)

 Computing the Tandem Duplication Distance is NPHard

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Manuel Lafond, Binhai Zhu, Peng Zou
Pages: 64  91
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 6491, 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 segmentthis 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 NPhard when the alphabet size is unbounded, settling the 16yearold open problem. We then show how to adapt the proof to $ \Sigma =4$, hence proving the NPhardness of the TD problem for any $ \Sigma \geq 4$. One of the tools we develop for the reduction is a new problem called CostEffective 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 fixedparameter tractable. Our results open the door to many other questions, and we conclude with several open problems.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220104T08:00:00Z
DOI: 10.1137/20M1356257
Issue No: Vol. 36, No. 1 (2022)

 Lattice Size of Plane Convex Bodies

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Anthony Harrison, Jenya Soprunova, Patrick Tierney
Pages: 92  102
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 92102, 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: 20220104T08:00:00Z
DOI: 10.1137/20M137536X
Issue No: Vol. 36, No. 1 (2022)

 Ramsey Numbers for Nontrivial Berge Cycles

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Jiaxi Nie, Jacques Verstraëte
Pages: 103  113
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 103113, January 2022.
In this paper, we consider an extension of cyclecomplete 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 3uniform 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}{2k1} + \frac{2}{\sqrt{\log t}}}$, and moreover, we show that if a conjecture of Erdös and Simonovits [Combinatorica, 2 (1982), pp. 275288] 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: 20220104T08:00:00Z
DOI: 10.1137/21M1396770
Issue No: Vol. 36, No. 1 (2022)

 A Note on Seminormality of Cut Polytopes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Michał Lasoń, Mateusz Michałek
Pages: 114  117
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 114117, January 2022.
We prove that seminormality of cut polytopes is equivalent to normality.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220104T08:00:00Z
DOI: 10.1137/20M138586X
Issue No: Vol. 36, No. 1 (2022)

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

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Georgios Amanatidis, Pieter Kleer
Pages: 118  146
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 118146, 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. 418445] introduced in the context of sampling bichromatic matchings.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220106T08:00:00Z
DOI: 10.1137/20M1352697
Issue No: Vol. 36, No. 1 (2022)

 Localized Codegree Conditions for Tight Hamilton Cycles in 3Uniform
Hypergraphs
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Pedro Araújo, Simón Piga, Mathias Schacht
Pages: 147  169
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 147169, January 2022.
We study sufficient conditions for the existence of Hamilton cycles in uniformly dense 3uniform hypergraphs. Problems of this type were first considered by Lenz, Mubayi, and Mycroft for loose Hamilton cycles, and AignerHorev 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 3uniform 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: 20220106T08:00:00Z
DOI: 10.1137/21M1408531
Issue No: Vol. 36, No. 1 (2022)

 Pure Pairs VI: Excluding an Ordered Tree

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Alex Scott, Paul Seymour, Sophie Spirkl
Pages: 170  187
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 170187, 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 ^{1o(1)}$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220106T08:00:00Z
DOI: 10.1137/20M1368331
Issue No: Vol. 36, No. 1 (2022)

 Understanding Popular Matchings via Stable Matchings

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Ágnes Cseh, Yuri Faenza, Telikepalli Kavitha, Vladlena Powers
Pages: 188  213
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 188213, 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 headtohead election against any matching where vertices are voters. Every stable matching is a minsize 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 headtohead election against any larger matching. Thus, every dominant matching is a maxsize 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 coNP 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 NPhardness 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 minsize (resp., maxsize) popular matching that is not stable (resp., dominant). A known result for which we give a new and simple proof is the NPhardness of finding a popular matching when $G$ is nonbipartite.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220110T08:00:00Z
DOI: 10.1137/19M124770X
Issue No: Vol. 36, No. 1 (2022)

 On Ordered Ramsey Numbers of Tripartite 3Uniform Hypergraphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Martin Balko, Máté Vizer
Pages: 214  228
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 214228, January 2022.
For an integer $k \geq 2$, an ordered $k$uniform hypergraph $\mathcal{H}=(H,
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220110T08:00:00Z
DOI: 10.1137/21M1404958
Issue No: Vol. 36, No. 1 (2022)

 On the Stability of the Graph Independence Number

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Zichao Dong, Zhuo Wu
Pages: 229  240
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 229240, January 2022.
Let $G$ be a graph on $n$ vertices of independence number $\alpha(G)$ such that every induced subgraph of $G$ on $nk$ 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ösRogers function.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220110T08: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 preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Zequn Lv, Mei Lu, Yi Zhang
Pages: 241  251
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 241251, 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: 20220113T08:00:00Z
DOI: 10.1137/20M1365557
Issue No: Vol. 36, No. 1 (2022)

 The Power of the WeisfeilerLeman Algorithm to Decompose Graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Sandra Kiefer, Daniel Neuen
Pages: 252  298
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 252298, January 2022.
The WeisfeilerLeman procedure is a widely used technique for graph isomorphism testing that works by iteratively computing an isomorphisminvariant 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 3connected components. We prove that the twodimensional WeisfeilerLeman algorithm implicitly computes the decomposition of a graph into its 3connected 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 3connected 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 WeisfeilerLeman 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: 20220124T08:00:00Z
DOI: 10.1137/20M1314987
Issue No: Vol. 36, No. 1 (2022)

 On the Largest Common Subtree of Random LeafLabeled Binary Trees

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: David J. Aldous
Pages: 299  314
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 299314, 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: 20220127T08:00:00Z
DOI: 10.1137/20M1347504
Issue No: Vol. 36, No. 1 (2022)

 Small Doubling in Groups with Moderate Torsion

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Vsevolod F. Lev
Pages: 315  335
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 315335, 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 onedimensional 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 wellknown Freiman's $(3n3)$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: 20220131T08:00:00Z
DOI: 10.1137/21M1397799
Issue No: Vol. 36, No. 1 (2022)

 On the Maximum Agreement Subtree Conjecture for Balanced Trees

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 336354, January 2022.
We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaflabeled 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 leaflabeled 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: 20220131T08: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 preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: ChienChung Huang, Naonori Kakimura, Simon Mauras, Yuichi Yoshida
Pages: 355  382
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 355382, March 2022.
Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the singlepass 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 singlepass 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}{2K1}+\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 weakoracle streaming algorithms for cardinality and matroid constraints with approximation ratios $\frac{K}{2K1}$ 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}{2K1}$ 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: 20220208T08:00:00Z
DOI: 10.1137/20M1357317
Issue No: Vol. 36, No. 1 (2022)

 Tropical Lines on Cubic Surfaces

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Marta Panizzut, Magnus Dehli Vigeland
Pages: 383  410
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 383410, 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: 20220208T08:00:00Z
DOI: 10.1137/20M136520X
Issue No: Vol. 36, No. 1 (2022)

 A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Mamadou M. Kanté, Christophe Paul, Dimitrios M. Thilikos
Pages: 411  435
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 411435, 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. 85100]. 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. 358402] 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: 20220210T08:00:00Z
DOI: 10.1137/20M1369361
Issue No: Vol. 36, No. 1 (2022)

 The Generalized Rainbow Turán Problem for Cycles

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Barnabás Janzer
Pages: 436  448
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 436448, March 2022.
Given an edgecolored 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 edgecolored 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^{k1})$ 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: 20220214T08:00:00Z
DOI: 10.1137/20M1351473
Issue No: Vol. 36, No. 1 (2022)

 Enumerating Integer Points in Polytopes with Bounded Subdeterminants

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Hongyi Jiang, Amitabh Basu
Pages: 449  460
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 449460, 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: 20220214T08:00:00Z
DOI: 10.1137/21M139935X
Issue No: Vol. 36, No. 1 (2022)

 Three Combinatorial Perspectives on Minimal Codes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Gianira N. Alfarano, Martino Borello, Alessandro Neri, Alberto Ravagnani
Pages: 461  489
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 461489, 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 AlonFü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: 20220215T08:00:00Z
DOI: 10.1137/21M1391493
Issue No: Vol. 36, No. 1 (2022)

 Reconstructibility of Matroid Polytopes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Guillermo PinedaVillavicencio, Benjamin Schröter
Pages: 490  508
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 490508, 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: 20220217T08: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 preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Victor Chepoi, Kolja Knauer, Manon Philibert
Pages: 509  535
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 509535, March 2022.
This paper considers completions of tope graphs of complexes of oriented matroids (COMs) to ample partial cubes of the same VapnikChervonenkis dimension (VCdimension). 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 conjectureone 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 VCdimension.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220224T08:00:00Z
DOI: 10.1137/20M1355434
Issue No: Vol. 36, No. 1 (2022)

 Target Set Selection in Dense Graph Classes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Pavel Dvořák, Dušan Knop, Tomáš Toufar
Pages: 536  572
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 536572, 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 socalled 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 modularwidtha 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: 20220224T08:00:00Z
DOI: 10.1137/20M1337624
Issue No: Vol. 36, No. 1 (2022)

 A Note on Infinite Antichain Density

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Paul Balister, Emil Powierski, Alex Scott, Jane Tan
Pages: 573  577
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 573577, 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: 20220301T08:00:00Z
DOI: 10.1137/21M143025X
Issue No: Vol. 36, No. 1 (2022)

 Digraphs and Variable Degeneracy

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Jørgen BangJensen, Thomas Schweser, Michael Stiebitz
Pages: 578  595
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 578595, 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 listversion 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 indegree and maximum outdegree.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220303T08: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 preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Sushmita Gupta, Saket Saurabh, Meirav Zehavi
Pages: 596  681
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 596681, March 2022.
Stable Marriage is a fundamental problem to both computer science and economics. Four wellknown NPhard optimization versions of this problem are the SexEqual Stable Marriage (SESMI), Balanced Stable Marriage (BSMI), maxStable Marriage with Ties (maxSMTI), and minStable Marriage with Ties (minSMTI) 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 exponentialtime hypothesis is false, all of these algorithms are optimal. Next, we study the treewidth ${\mathtt{tw}}$ of the rotation digraph. In this context, maxSMTI and minSMTI 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 exponentialtime 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: 20220309T08:00:00Z
DOI: 10.1137/19M130491X
Issue No: Vol. 36, No. 1 (2022)

 Characteristic Dependence of Syzygies of Random Monomial Ideals

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Caitlyn BoomsPeot, Daniel Erman, Jay Yang
Pages: 682  701
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 682701, March 2022.
When do syzygies depend on the characteristic of the field' Even for wellstudied families of examples, very little is known. For a family of random monomial ideals, namely, the StanleyReisner 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: 20220309T08: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 2Matchings, and Matroids
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Kenjiro Takazawa
Pages: 702  727
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 702727, 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 trianglefree 2matching, squarefree 2matching, 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 minmax theorem and a combinatorial algorithm for the unweighted version. We then provide a linear programming formulation with dual integrality and a primaldual 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 trianglefree 2matching algorithm, a squarefree 2matching algorithm, and an arborescence algorithm, respectively.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220314T07: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 preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Yahav Alon, Michael Krivelevich
Pages: 728  754
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 728754, 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: 20220314T07:00:00Z
DOI: 10.1137/20M1375838
Issue No: Vol. 36, No. 1 (2022)

 Regular Graphs with Few Longest Cycles

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Carol T. Zamfirescu
Pages: 755  776
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 755776, 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 4regular 4connected graphs, each containing exactly $c$ Hamiltonian cycles. We complement this by proving that the same conclusion holds for planar 4regular 3connected graphs, although it does not hold for planar 4regular 4connected graphs by a result of Brinkmann and Van Cleemput [European J. Combin., 97 (2021), 103395], and that it holds for 4regular graphs of connectivity 2 with the constant $144 < c$, which we believe to be minimal among all Hamiltonian 4regular graphs of sufficiently large order. We then disprove a conjecture of Haythorpe by showing that for every nonnegative integer $k$ there is a 5regular 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 3connected graphs with minimum degree $d$, with a bounded number of Hamiltonian cycles. It is shown that if a 3regular 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 3regular graphs with exactly two such components.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220321T07:00:00Z
DOI: 10.1137/21M1414048
Issue No: Vol. 36, No. 1 (2022)

 Bounding the Number of Edges of Matchstick Graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Jérémy Lavollée, Konrad J. Swanepoel
Pages: 777  785
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 777785, March 2022.
A matchstick graph is a crossingfree unitdistance 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{12n3}\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 $3nc\sqrt{n1/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: 20220324T07:00:00Z
DOI: 10.1137/21M1441134
Issue No: Vol. 36, No. 1 (2022)

 An Irrational Lagrangian Density of a Single Hypergraph

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Zilong Yan, Yuejian Peng
Pages: 786  822
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 786822, 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. 5157] and Erdös and Stone [Bull. Amer. Math. Soc., 52 (1946), pp. 10871091] showed that $\Pi_{\infty}^{(2)}=\Pi_{fin}^{(2)}=\Pi_{1}^{(2)}={0, {1 \over 2}, {2 \over 3}, ...,{l1 \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. 415454] 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;Ffree\}$, where $\lambda(G)$ is the Lagrangian of an $r$uniform graph $G$. Sidorenko [Combinatorica, 9 (1989), pp. 207215] 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: 20220329T07:00:00Z
DOI: 10.1137/21M1410798
Issue No: Vol. 36, No. 1 (2022)

 Computational Complexity of Biased DiffusionLimited Aggregation

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Nicolas Bitar, Eric Goles, Pedro Montealegre
Pages: 823  866
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 823866, March 2022.
Diffusionlimited aggregation (DLA) is a clustergrowth model that consists of a set of particles that are sequentially aggregated over a twodimensional 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 PComplete for 2DLA (thus for 3DLA). Later, we show that Prediction can be solved much more efficiently for 1DLA. In fact, we show that in that case, the problem is NLComplete. With respect to Realization, we show that when restricted to 2DLA the problem is in P, while in the 1DLA case, the problem is in L.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220331T07:00:00Z
DOI: 10.1137/18M1215815
Issue No: Vol. 36, No. 1 (2022)
