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] 
 Minimal Ramsey Graphs with Many Vertices of Small Degree

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: Simona Boyadzhiyska, Dennis Clemens, Pranshu Gupta
Pages: 1503  1528
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 15031528, September 2022.
Given any graph $H$, a graph $G$ is said to be $q$Ramsey for $H$ if every coloring of the edges of $G$ with $q$ colors yields a monochromatic subgraph isomorphic to $H$. Such a graph $G$ is said to be minimal $q$Ramsey for $H$ if additionally no proper subgraph $G'$ of $G$ is $q$Ramsey for $H$. In 1976, Burr, Erdös, and Lovász initiated the study of the parameter $s_q(H)$, defined as the smallest minimum degree among all minimal $q$Ramsey graphs for $H$. In this paper, we consider the problem of determining how many vertices of degree $s_q(H)$ a minimal $q$Ramsey graph for $H$ can contain. Specifically, we seek to identify graphs for which a minimal $q$Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property $s_q$abundant. Among other results, we prove that every cycle is $s_q$abundant for any integer $q\geq 2$. We also discuss the cases when $H$ is a clique or a clique with a pendant edge, extending previous results of Burr and coauthors and Fox and coauthors. To prove our results and construct suitable minimal Ramsey graphs, we use gadget graphs, which we call pattern gadgets and which generalize earlier constructions used in the study of minimal Ramsey graphs. We provide a new, more constructive proof of the existence of these gadgets.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220705T07:00:00Z
DOI: 10.1137/21M1393273
Issue No: Vol. 36, No. 3 (2022)

 Lossless Prioritized Embeddings

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: Michael Elkin, Ofer Neiman
Pages: 1529  1550
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 15291550, September 2022.
Given metric spaces $(X,d)$ and $(Y,\rho)$ and an ordering $x_1,x_2,\ldots,x_n$ of $(X,d)$, an embedding $f: X \rightarrow Y$ is said to have a prioritized distortion $\alpha(\cdot)$, for a function $\alpha(\cdot)$, if for any pair $x_j,x'$ of distinct points in $X$, the distortion provided by $f$ for this pair is at most $\alpha(j)$. If $Y$ is a normed space, the embedding is said to have prioritized dimension $\beta(\cdot)$ if $f(x_j)$ may have at most $\beta(j)$ nonzero coordinates. The notion of prioritized embedding was introduced by Filtser and the current authors in [M. Elkin, A. Filtser, and O. Neiman, SIAM J. Comput., 47 (2018), pp. 829858], where a rather general methodology for constructing such embeddings was developed. Though this methodology enabled [M. Elkin, A. Filtser, and O. Neiman, SIAM J. Comput., 47 (2018), pp. 829858] to come up with many prioritized embeddings, it typically incurs some loss in the distortion. In other words, in the worst case, prioritized embeddings obtained via this methodology incur distortion which is at least a constant factor off compared to the distortion of the classical counterparts of these embeddings. This constant loss is problematic for isometric embeddings. It is also troublesome for Matoušek's embedding of general metrics into $\ell_\infty$, which, for a parameter $k = 1,2,\ldots$, provides distortion $2k1$ and dimension $O(k \log n \cdot n^{1/k})$. All logarithms in this paper are base 2. In this paper we devise two lossless prioritized embeddings. The first one is an isometric prioritized embedding of tree metrics into $\ell_\infty$ with dimension $O(\log j)$, matching the worstcase guarantee of $O(\log n)$ of the classical embedding of [N. Linial, E. London, and Y. Rabinovich, Combinatorica, 15 (1995), pp. 215245]. The second one is a prioritized Matoušek embedding of general metrics into $\ell_\infty$, which, for a parameter $k=1,2,\ldots$, provides prioritized distortion $2 \lceil k {{\log j} \over {\log n}} \rceil  1$ and dimension $O(k \log n \cdot n^{1/k})$, again matching the worstcase guarantee $2k1$ in the distortion of the classical Matoušek embedding. We also provide a dimensionprioritized variant of Matoušek's embedding. Finally, we devise prioritized embeddings of general metrics into a single ultrametric and of general graphs into a single spanning tree, with asymptotically optimal distortion.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220705T07:00:00Z
DOI: 10.1137/21M1436221
Issue No: Vol. 36, No. 3 (2022)

 SelfDual Maps I: Antipodality

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: Luis Montejano, Jorge L. Ramírez Alfonsín, Ivan Rasskin
Pages: 1551  1566
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 15511566, September 2022.
A selfdual map $G$ is said to be antipodally selfdual if the dual map $G^*$ is antipodal embedded in $\mathbb{S}^2$ with respect to $G$. In this paper, we investigate necessary and/or sufficient conditions for a map to be antipodally selfdual. In particular, we present a combinatorial characterization for map $G$ to be antipodally selfdual in terms of certain involutive labelings. The latter lead us to obtain necessary conditions for a map to be strongly involutive (a notion relevant for its connection with convex geometric problems). We also investigate the relation of antipodally selfdual maps and the notion of antipodally symmetric maps. It turns out that the latter is a very helpful tool to study questions concerning the symmetry as well as the amphicheirality of links.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220705T07:00:00Z
DOI: 10.1137/20M1367076
Issue No: Vol. 36, No. 3 (2022)

 When Do GomoryHu Subtrees Exist'

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: Guyslain Naves, Bruce Shepherd
Pages: 1567  1585
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 15671585, September 2022.
GomoryHu (GH) trees are a classical sparsification technique for graph connectivity. For an edgecapacitated undirected graph $G=(V,E)$ and subset $Z \subseteq V$ of terminals, a GH tree is an edgecapacitated tree $T=(Z,E(T))$ such that for every $u,v \in Z$, the value of the minimum capacity $uv$ cut in $G$ is the same as in $T$. It is wellknown that there does not always exist a GH tree which is a subgraph (or minor if $Z \neq V$) of $G$. We characterize those graphterminal pairs $(G,Z)$ which always admit such a tree. We show that these are the graphs which have no terminal$K_{2,3}$ minor, that is, a $K_{2,3}$ minor whose nodes each corresponds to a terminal. We then show that the pairs $(G,Z)$ which forbid such $K_{2,3}$ terminalminors arise, roughly speaking, from socalled OkamuraSeymour instances, planar graphs whose outside face contains all terminals. One consequence is a result on cutsufficient pairs $(G,H)$, that is, multiflow instances where the cut condition is sufficient to guarantee a multiflow for any capacity/demand weights on $G/H$. Our results characterize the pairs $(G,Z)$ where $G$ is a graph, $Z \subseteq V(G)$, such that $(G,H)$ is cutsufficient for any demand graph $H$ on $Z$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220705T07:00:00Z
DOI: 10.1137/20M1356968
Issue No: Vol. 36, No. 3 (2022)

 Posets and Spaces of $k$Noncrossing RNA Structures

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: Vincent Moulton, Taoyang Wu
Pages: 1586  1611
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 15861611, September 2022.
RNA molecules are singlestranded analogues of DNA that can fold into various structures which influence their biological function within the cell. RNA structures can be modeled combinatorially in terms of a certain type of graph called an RNA diagram. In this paper we introduce a new poset of RNA diagrams ${\mathcal B}^r_{f,k}$, $r\ge 0$, $k \ge 1$, and $f \ge 3$, which we call the PennerWaterman poset, and, using results from the theory of multitriangulations, we show that this is a pure poset of rank $k(2f2k+1)+rf1$, whose geometric realization is the join of a simplicial sphere of dimension $k(f2k)1$ and an $\left((f+1)(k1)1\right)$simplex in case $r=0$. As a corollary for the special case $k=1$, we obtain a result due to Penner and Waterman concerning the topology of the space of RNA secondary structures. These results could eventually lead to new ways to study landscapes of RNA $k$noncrossing structures.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220707T07:00:00Z
DOI: 10.1137/21M1413316
Issue No: Vol. 36, No. 3 (2022)

 Spanning Trees at the Connectivity Threshold

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, Peleg Michaeli
Pages: 1612  1626
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 16121626, September 2022.
We present an explicit connected spanning structure that appears in a random graph just above the connectivity threshold with high probability.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220711T07:00:00Z
DOI: 10.1137/20M1380521
Issue No: Vol. 36, No. 3 (2022)

 The 9Connected Excluded Minors for the Class of Quasigraphic 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: Rong Chen
Pages: 1627  1644
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 16271644, September 2022.
The class of quasigraphic matroids, recently introduced by Geelen, Gerards, and Whittle, is minor closed and contains both the class of liftedgraphic matroids and the class of frame matroids, each of which generalizes the class of graphic matroids. In this paper, we prove that the matroids $U_{3,7}$ and $U_{4,7}$ are the only 9connected excluded minors for the class of quasigraphic matroids.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220713T07:00:00Z
DOI: 10.1137/21M142784X
Issue No: Vol. 36, No. 3 (2022)

 Rainbow Perfect Matchings for 4Uniform 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: Hongliang Lu, Yan Wang, Xingxing Yu
Pages: 1645  1662
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 16451662, September 2022.
Let $n$ be a sufficiently large integer with $n\equiv 0\pmod 4$, and let $F_i \subseteq{[n]\choose 4}$, where $i\in [n/4]$. We show that if each vertex of $F_i$ is contained in more than ${n1\choose 3}{3n/4\choose 3}$ edges, then $\{F_1, \ldots ,F_{n/4}\}$ admits a rainbow matching, i.e., a set of $n/4$ edges consisting of one edge from each $F_i$. This generalizes a deep result of Khan J. Combin. Theory Ser. B, 116 (2016), pp. 333366. on perfect matchings in 4uniform hypergraphs.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220714T07:00:00Z
DOI: 10.1137/21M1442383
Issue No: Vol. 36, No. 3 (2022)

 A General Framework for Hypergraph Coloring

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: Ian M. Wanless, David R. Wood
Pages: 1663  1677
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 16631677, September 2022.
The Lovász Local Lemma is a powerful probabilistic technique for proving the existence of combinatorial objects. It is especially useful for coloring graphs and hypergraphs with bounded maximum degree. This paper presents a general theorem for coloring hypergraphs that in many instances matches or slightly improves upon the bounds obtained using the Lovász Local Lemma. Moreover, the theorem directly shows that there are exponentially many colorings. The elementary and selfcontained proof is inspired by a recent result for nonrepetitive colorings by Rosenfeld [Electron. J. Combin., 27 (2020), P3.43]. We apply our general theorem in the settings of proper hypergraph coloring, proper graph coloring, independent transversals, star coloring, nonrepetitive coloring, frugal coloring, Ramsey number lower bounds, and $k$SAT.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220714T07:00:00Z
DOI: 10.1137/21M1421015
Issue No: Vol. 36, No. 3 (2022)

 Counterexamples to a Conjecture of Harris on Hall Ratio

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: Adam Blumenthal, Bernard Lidický, Ryan R. Martin, Sergey Norin, Florian Pfender, Jan Volec
Pages: 1678  1686
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 16781686, September 2022.
The Hall ratio of a graph $G$ is the maximum value of $v(H) / \alpha(H)$ taken over all nonnull subgraphs $H \subseteq G$. For any graph, the Hall ratio is a lowerbound on its fractional chromatic number. In this note, we present various constructions of graphs whose fractional chromatic number grows much faster than their Hall ratio. This refutes a conjecture of Harris.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220718T07:00:00Z
DOI: 10.1137/18M1229420
Issue No: Vol. 36, No. 3 (2022)

 On the Cover Time of the Emerging Giant

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: Alan M. Frieze, Wesley Pegden, Tomasz Tkocz
Pages: 1687  1710
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 16871710, September 2022.
Let $p=\frac{1+\varepsilon}{n}$. It is known that if $N=\varepsilon^3n\to\infty$, then with high probability (w.h.p.) $G_{n,p}$ has a unique giant largest component. We show that if in addition, $\varepsilon=\varepsilon(n)\to 0$, then w.h.p. the cover time of $G_{n,p}$ is asymptotic to $n\log^2N$; previously Barlow, Ding, Nachmias, and Peres had shown this up to constant multiplicative factors.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220721T07:00:00Z
DOI: 10.1137/21M1441468
Issue No: Vol. 36, No. 3 (2022)

 The Structure of $I_4$Free and TriangleFree Binary 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: Peter Nelson, Kazuhiro Nomoto
Pages: 1711  1729
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 17111729, September 2022.
A simple binary matroid is called $I_4$free if none of its rank4 flats are independent sets. These objects can be equivalently defined as the sets $E$ of points in $\mbox{PG}(n1,2)$ for which $E \cap F$ is not a basis of $F$ for any fourdimensional flat $F$. We prove a decomposition theorem that exactly determines the structure of all $I_4$free and trianglefree matroids. In particular, our theorem implies that the $I_4$free and trianglefree matroids have critical number at most 2.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220721T07:00:00Z
DOI: 10.1137/20M1343099
Issue No: Vol. 36, No. 3 (2022)

 A $\frac{4}{3}$Approximation Algorithm for the Minimum 2Edge Connected
Multisubgraph Problem in the HalfIntegral Case
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: Sylvia Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, Lu Wang
Pages: 1730  1747
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 17301747, September 2022.
Given a connected undirected graph $\overline{G}$ on $n$ vertices and nonnegative edge costs $c$, the $\ensuremath{{2ECM}}$ problem is that of finding a 2edge connected spanning multisubgraph of $\overline{G}$ of minimum cost. The natural linear program (LP) for $\ensuremath{{2ECM}}$, which coincides with the subtour LP for the traveling salesman problem on the metric closure of $\overline{G}$, gives a lower bound on the optimal cost. For instances where this LP is optimized by a halfintegral solution $x$, Carr and Ravi (1998) showed that the integrality gap is at most $\frac43$: they show that the vector $\frac43 x$ dominates a convex combination of incidence vectors of 2edge connected spanning multisubgraphs of $\overline{G}$. We present a simpler proof of the result due to Carr and Ravi by applying an extension of Lovász's splittingoff theorem. Our proof naturally leads to a $\frac43$approximation algorithm for halfintegral instances. Given a halfintegral solution $x$ to the LP for $\ensuremath{{2ECM}}$, we give an $O(n^2)$time algorithm to obtain a 2edge connected spanning multisubgraph of $\overline{G}$ with cost at most $\frac43 c^T x$. We also consider a related problem of finding a cheap 2edge connected spanning subgraph of a 3regular, 3edge connected graph $G = (V,E)$ with arbitrary edge costs $c$. We give a polynomialtime Las Vegas algorithm that finds a random 2edge connected spanning subgraph $H$ of $G$ whose expected cost, $\mathbb{E}\left[{c(H)}\right]$, is at most $\frac45 c(E)$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220728T07:00:00Z
DOI: 10.1137/20M1372822
Issue No: Vol. 36, No. 3 (2022)

 On Discrete LOGBrunnMinkowski Type Inequalities

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: María A. Hernández Cifre, Eduardo Lucas
Pages: 1748  1760
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 17481760, September 2022.
The conjectured logBrunnMinkowski inequality says that the volume of centrally symmetric convex bodies $K,L\subset\mathbb{R}^n$ satisfies ${vol}\bigl((1\lambda)\cdot K+_0\lambda\cdot L\bigr) \geq{vol}(K)^{1\lambda}{vol}(L)^\lambda$, $\lambda\in(0,1)$, and is known to be true in the plane and for particular classes of symmetric convex bodies in $\mathbb{R}^n$. In this paper, we get some discrete logBrunnMinkowski type inequalities for the lattice point enumerator. Among others, we show that if $K,L\subset\mathbb{R}^n$ are unconditional convex bodies and $\lambda\in(0,1)$, then ${G}_n((1\lambda)\cdot(K+C_n)+_0\lambda\cdot(L+C_n)+(\frac{1}{2},\frac{1}{2})^n) \geq{G}_n(K)^{1\lambda}{G}_n(L)^\lambda, $ where $C_n=[1/2,1/2]^n$. Neither $C_n$ nor $(1/2,1/2)^n$ can be removed. Furthermore, it implies the (volume) logBrunnMinkowski inequality for unconditional convex bodies. The corresponding results in the $L_p$ setting for $0
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220728T07:00:00Z
DOI: 10.1137/21M1451725
Issue No: Vol. 36, No. 3 (2022)

 Grundy Distinguishes Treewidth from 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: Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi
Pages: 1761  1787
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 17611787, September 2022.
Structural graph parameters, such as treewidth, pathwidth, and cliquewidth, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the “price of generality” of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status deteriorate from fixedparameter tractable (FPT) to intractable' This type of question is by now very well studied, but somewhat strikingly, the algorithmic frontier between the two (arguably) most central width notions, treewidth and pathwidth, is still not understood: currently, no natural graph problem is known to be Whard for one but FPT for the other. Indeed, a surprising development of the last few years has been the observation that, for many of the most paradigmatic problems, their complexities for the two parameters actually coincide exactly, despite the fact that treewidth is a much more general parameter. It would thus appear that the extra generality of treewidth over pathwidth often comes “for free.” Our main contribution in this paper is to uncover the first natural example where this generality comes with a high price. We consider Grundy Coloring, a variation of coloring where one seeks to calculate the worst possible coloring that could be assigned to a graph by a greedy firstfit algorithm. We show that this wellstudied problem is FPT parameterized by pathwidth; however, it becomes significantly harder (W[1]hard) when parameterized by treewidth. Furthermore, we show that Grundy Coloring makes a second complexity jump for more general widths, as it becomes paraNPhard for cliquewidth. Hence, Grundy Coloring nicely captures the complexity tradeoffs between the three most wellstudied parameters. Completing the picture, we show that Grundy Coloring is FPT parameterized by modularwidth.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220728T07:00:00Z
DOI: 10.1137/20M1385779
Issue No: Vol. 36, No. 3 (2022)

 EMSO(FO$^2$) 01 Law Fails for All Dense Random 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: Margarita Akhmejanova, Maksim Zhukovskii
Pages: 1788  1799
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 17881799, September 2022.
In this paper, we disprove EMSO(FO$^2$) convergence law for the binomial random graph $G(n,p)$ for any constant probability $p$. More specifically, we prove that there exists an existential monadic second order sentence with 2 first order variables such that, for every $p\in(0,1)$, the probability that it is true on $G(n,p)$ does not converge.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220802T07:00:00Z
DOI: 10.1137/21M1429655
Issue No: Vol. 36, No. 3 (2022)

 Ideal Membership Problem over 3Element CSPs with Dual Discriminator
Polymorphism
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: Arpitha P. Bharathi, Monaldo Mastrolilli
Pages: 1800  1822
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 18001822, September 2022.
In this paper we examine polynomial ideals that are the vanishing ideals of solution sets of combinatorial problems encoded by constraint satisfaction problems over a finite language. We consider a 3element domain and the dual discriminator polymorphism (constraints under this polymorphism are a generalization of the 2satisfiability problem). Assuming the graded lexicographic ordering of monomials, we show that the reduced Gröbner basis of ideals whose varieties are closed under this polymorphism can be computed in polynomial time. This proves polynomial time solvability of the ideal membership problem (IMP) with restrictions on degree $d=O(1)$, which we call IMP$_d$, for these constrained problems. It is a first step toward the challenging longterm goal of identifying when IMP$_d$ is polynomial time solvable for a finite domain.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220802T07:00:00Z
DOI: 10.1137/21M1397131
Issue No: Vol. 36, No. 3 (2022)

 Nontrivial tIntersecting Families for Vector Spaces

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: Mengyu Cao, Benjian Lv, Kaishun Wang, Sanming Zhou
Pages: 1823  1847
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 18231847, September 2022.
Let $V$ be an $n$dimensional vector space over a finite field $\mathbb{F}_q$. In this paper we describe the structure of maximal nontrivial $t$intersecting families of $k$dimensional subspaces of $V$ with large size. We also determine the nontrivial $t$intersecting families with maximum size. In the special case when $t=1$ our result gives rise to the wellknown HiltonMilner theorem for vector spaces.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220804T07:00:00Z
DOI: 10.1137/20M1357421
Issue No: Vol. 36, No. 3 (2022)

 On Multicolor Ramsey Numbers and Subset Coloring of 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: Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky
Pages: 1848  1860
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 18481860, January 2022.
For $n\geq s> r\geq 1$ and $k\geq 2$, write $n \rightarrow (s)_{k}^r$ if every hyperedge coloring with $k$ colors of the complete $r$uniform hypergraph on $n$ vertices has a monochromatic subset of size $s$. Improving upon previous results by M. Axenovich, A. Gyárfás, H. Liu, and D. Mubayi [Discrete Math., 322 (2014), pp. 6977] and P. Erdös, A. Hajnal, A. Máté, and R. Rado, [Combinatorial set theory: Partition Relations for Cardinals, Elsevier, Amsterdam, 1984] we show that $if r \geq 3 and n \nrightarrow (s)_k^r, then 2^n \nrightarrow (s+1)_{k+3}^{r+1}.$ This improves some of the known lower bounds on multicolor hypergraph Ramsey numbers. Given a hypergraph $H=(V,E)$, we consider the Ramseylike problem of coloring all $r$subsets of $V$ such that no hyperedge of size $\geq r+1$ is monochromatic. We provide upper and lower bounds on the number of colors necessary in terms of the chromatic number $\chi(H)$. In particular we show that this number is $O(\log^{(r1)} (r \chi(H)) + r)$, where $\log^{y}$ is the $\log$ function applied $y$ times.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220811T07:00:00Z
DOI: 10.1137/21M1462003
Issue No: Vol. 36, No. 3 (2022)

 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)

 On HopConstrained Steiner Trees in TreeLike Metrics

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 Böhm, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Bertrand Simon
Pages: 1249  1273
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 12491273, June 2022.
We consider the problem of computing a Steiner tree of minimum cost under a hop constraint that requires the depth of the tree to be at most $k$. Our main result is an exact algorithm for metrics induced by graphs with bounded treewidth that runs in time $n^{O(k)}$. For the special case of a path, we give a simple algorithm that solves the problem in polynomial time, even if $k$ is part of the input. The main result can be used to obtain, in quasipolynomial time, a nearoptimal solution that violates the $k$hop constraint by at most one hop for more general metrics induced by graphs of bounded highway dimension and bounded doubling dimension. For nonmetric graphs, we rule out an $o(\log n)$approximation, assuming P$\,\neq\,$NP even when relaxing the hop constraint by any additive constant.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220601T07:00:00Z
DOI: 10.1137/21M1425487
Issue No: Vol. 36, No. 2 (2022)

 Perfect Matchings in the Semirandom Graph Process

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: Pu Gao, Calum MacRury, Paweł Prałat
Pages: 1274  1290
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 12741290, June 2022.
The semirandom graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the player independently and uniformly at random. The player then adaptively selects a vertex $v$ and adds the edge $uv$ to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a perfect matching in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves a perfect matching in $\beta n$ rounds, where the value of $\beta < 1.206$ is derived from a solution to some system of differential equations. This improves upon the previously best known upper bound of $(1+2/e+o(1)) \, n < 1.736 \, n$ rounds. We also improve the previously best lower bound of $(\ln 2 + o(1)) \, n> 0.693 \, n$ and show that the player cannot achieve the desired property in less than $\alpha n$ rounds, where the value of $\alpha> 0.932$ is derived from a solution to another system of differential equations. As a result, the gap between the upper and lower bounds is decreased roughly four times.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220601T07:00:00Z
DOI: 10.1137/21M1446939
Issue No: Vol. 36, No. 2 (2022)

 Completing and Extending Shellings of Vertex Decomposable Complexes

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: Michaela Coleman, Anton Dochtermann, Nathan Geist, Suho Oh
Pages: 1291  1305
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 12911305, June 2022.
We say that a pure $d$dimensional simplicial complex $\Delta$ on $n$ vertices is shelling completable if $\Delta$ can be realized as the initial sequence of some shelling of $\Delta_{n1}^{(d)}$, the $d$skeleton of the $(n1)$dimensional simplex. A wellknown conjecture of Simon posits that any shellable complex is shelling completable. In this note we prove that vertex decomposable complexes are shelling completable. In fact we show that if $\Delta$ is a vertex decomposable complex, then there exists an ordering of its ground set $V$ such that adding the revlex smallest missing $(d+1)$subset of $V$ results in a complex that is again vertex decomposable. We explore applications to matroids and shifted complexes, as well as connections to ridgechordal complexes and $k$decomposability. We also show that if $\Delta$ is a $d$dimensional complex on at most $d+3$ vertices, then the notions of shellable, vertex decomposable, shelling completable, and extendably shellable are all equivalent.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220602T07:00:00Z
DOI: 10.1137/21M1445119
Issue No: Vol. 36, No. 2 (2022)

 The Ising Antiferromagnet and Max Cut on Random Regular 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: Amin CojaOghlan, Philipp Loick, Balázs F. Mezei, Gregory B. Sorkin
Pages: 1306  1342
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 13061342, June 2022.
The Ising antiferromagnet is an important statistical physics model with close connections to the Max Cut problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry breaking phase transition predicted by physicists. Additionally, we rigorously establish upper bounds on the Max Cut of random regular graphs predicted by Zdeborová and Boettcher [J. Stat. Mech., 2010 (2010), P02020]. As an application we prove that the informationtheoretic threshold of the disassortative stochastic block model on random regular graphs coincides with the KestenStigum bound.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220602T07:00:00Z
DOI: 10.1137/20M137999X
Issue No: Vol. 36, No. 2 (2022)

 Disjoint Cycles with Length Constraints in Digraphs of Large Connectivity
or Large Minimum Degree
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: Raphael M. Steiner
Pages: 1343  1362
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 13431362, June 2022.
A conjecture by Lichiardopol [SIAM J. Discrete Math., 28 (2014), pp. 16181627] states that for every $k \ge 1$ there exists an integer $g(k)$ such that every digraph of minimum outdegree at least $g(k)$ contains $k$ vertexdisjoint directed cycles of pairwise distinct lengths. Motivated by Lichiardopol's conjecture, we study the existence of vertexdisjoint directed cycles satisfying length constraints in digraphs of large connectivity or large minimum degree. Our main result is that for every $k \in \mathbb{N}$, there exists $s(k) \in \mathbb{N}$ such that every strongly $s(k)$connected digraph contains $k$ vertexdisjoint directed cycles of pairwise distinct lengths. In contrast, for every $k \in \mathbb{N}$ we construct a strongly $k$connected digraph containing no two vertex or arcdisjoint directed cycles of the same length. It is an open problem whether $g(3)$ exists. Here we prove the existence of an integer $K$ such that every digraph of minimum out and indegree at least $K$ contains 3 vertexdisjoint directed cycles of pairwise distinct lengths.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220606T07:00:00Z
DOI: 10.1137/20M1382398
Issue No: Vol. 36, No. 2 (2022)

 A PolynomialTime Algorithm to Determine (Almost) Hamiltonicity of Dense
Regular 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: Viresh Patel, Fabian Stroh
Pages: 1363  1393
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 13631393, June 2022.
We give a polynomialtime algorithm for detecting very long cycles in dense regular graphs. Specifically, we show that, given $\alpha \in (0,1)$, there exists a $c=c(\alpha)$ such that the following holds: there is a polynomialtime algorithm that, given a $D$regular graph $G$ on $n$ vertices with $D\geq \alpha n$, determines whether $G$ contains a cycle on at least $n  c$ vertices. The problem becomes NPcomplete if we drop either the density or the regularity condition. The algorithm combines tools from extremal graph theory and spectral partitioning as well as some further algorithmic ingredients.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220607T07:00:00Z
DOI: 10.1137/20M1356191
Issue No: Vol. 36, No. 2 (2022)

 Planarity and Genus of Sparse Random Bipartite 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: Tuan A. Do, Joshua Erde, Mihyun Kang
Pages: 1394  1415
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 13941415, June 2022.
The genus of the binomial random graph $G(n,p)$ is well understood for a wide range of $p=p(n)$. Recently, the study of the genus of the random bipartite graph $G(n_1,n_2,p)$, with partition classes of size $n_1$ and $n_2$, was initiated by Mohar and Jing, who showed that when $n_1$ and $n_2$ are comparable in size and $p=p(n_1,n_2)$ is significantly larger than $(n_1n_2)^{\frac{1}{2}}$ the genus of the random bipartite graph has a similar behavior to that of the binomial random graph. In this paper we show that there is a threshold for planarity of the random bipartite graph at $p=(n_1n_2)^{\frac{1}{2}}$ and investigate the genus close to this threshold, extending the results of Mohar and Jing. It turns out that there is qualitatively different behavior in the case where $n_1$ and $n_2$ are comparable, when with high probability (whp) the genus is linear in the number of edges, than in the case where $n_1$ is asymptotically smaller than $n_2$, when whp the genus behaves like the genus of a sparse random graph $G(n_1,q)$ for an appropriately chosen $q=q(p,n_1,n_2)$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220613T07:00:00Z
DOI: 10.1137/20M1341817
Issue No: Vol. 36, No. 2 (2022)

 Robust Connectivity of Graphs on 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: Peter Bradshaw, Tomáš MasařÍk, Jana Novotná, Ladislav Stacho
Pages: 1416  1435
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 14161435, June 2022.
Let $\Lambda(T)$ denote the set of leaves in a tree $T$. One natural problem is to look for a spanning tree $T$ of a given graph $G$ such that $\Lambda(T)$ is as large as possible. This problem is called maximum leaf number, and it is a wellknown NPhard problem. Equivalently, the same problem can be formulated as the minimum connected dominating set problem, where the task is to find a smallest subset of vertices $D\subseteq V(G)$ such that every vertex of $G$ is in the closed neighborhood of $D$. Throughout recent decades, these two equivalent problems have received considerable attention, ranging from pure graph theoretic questions to practical problems related to the construction of wireless networks. Recently, a similar but stronger notion was defined by Bradshaw, Masařík, and Stacho [Flexible list colorings in graphs with special degeneracy conditions, in Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), LIPIcs. Leibniz Int. Proc. Inform. 181, Schloss Dagstuhl. LeibnizZent. Inform., Wadern, 2020, article 31]. They introduced a new invariant for a graph $G$, called the robust connectivity and written as $\kappa_\rho(G)$, defined as the minimum value $\frac{ R \cap \Lambda (T) }{ R }$ taken over all nonempty subsets $R\subseteq V(G)$, where $T = T(R)$ is a spanning tree on $G$ chosen to maximize $ R \cap \Lambda(T) $. Large robust connectivity was originally used to show flexible choosability in nonregular graphs. In this paper, we investigate some interesting properties of robust connectivity for graphs embedded in surfaces. We prove a tight asymptotic bound of $\Omega(\gamma^{\frac{1}{r}})$ for the robust connectivity of $r$connected graphs of Euler genus $\gamma$. Moreover, we give a surprising connection between the robust connectivity of graphs with an edgemaximal embedding in a surface and the surface connectivity of that surface, which describes to what extent large induced subgraphs of embedded graphs can be cut out from the surface without splitting the surface into multiple parts. For planar graphs, this connection provides an equivalent formulation of a longstanding conjecture of Albertson and Berman [A conjecture on planar graphs, in Graph Theory and Related Topics, Academic Press, San Diego, CA, 1979, p. 57], which states that every planar graph on $n$ vertices contains an induced forest of size at least $n/2$.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220616T07:00:00Z
DOI: 10.1137/21M1417077
Issue No: Vol. 36, No. 2 (2022)

 Online Assortment and Market Segmentation under Bertrand Competition with
SetDependent Revenues
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: S. Rasoul Etesami
Pages: 1436  1466
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 14361466, June 2022.
We consider an online assortment problem with $[n]=\{1,2,\ldots,n\}$ sellers, each holding exactly one item $i\in[n]$ with initial inventory $c_i\in \mathbb{Z}_+$, and a sequence of homogeneous buyers arriving over a finite time horizon $t=1,2,\ldots,m$. There is an online platform whose goal is to offer a subset $S_t\subseteq [n]$ of sellers to the arriving buyer at time $t$ to maximize the expected revenue derived over the entire horizon while respecting the inventory constraints. Given an assortment $S_t$ at time $t$, it is assumed that the buyer will select an item from $S_t$ based on the wellknown multinomial logit model, a welljustified choice model from the economic literature. In this model, the revenue obtained from selling an item $i$ at a given time $t$ critically depends on the assortment $S_t$ offered at that time and is given by the Nash equilibrium of a Bertrand game among the sellers in $S_t$. This imposes a strong dependence/externality among the offered assortments, sellers' revenues, and inventory levels. Despite that challenge, we devise a constant competitive algorithm for the online assortment problem with homogeneous buyers. It answers a question in [Z. Zheng and R. Srikant, Optimal Search Segmentation Mechanisms for Online Platform Markets, preprint, arXiv:1908.07489, 2019] that considered the static version of the assortment problem with only one buyer and no inventory constraints. We also show that the online assortment problem with heterogeneous buyers does not admit a constant competitive algorithm. To compensate that issue, we then consider the assortment problem under an offline setting with heterogeneous buyers. Under a mild market consistency assumption, we show that the generalized Bertrand game admits a pure Nash equilibrium over general buyerseller bipartite graphs. Finally, we develop an $O(\ln m)$approximation algorithm for optimal market segmentation of the generalized Bertrand game which allows the platform to derive higher revenues by partitioning the market into smaller pools.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220616T07:00:00Z
DOI: 10.1137/21M1400134
Issue No: Vol. 36, No. 2 (2022)

 A Matroid Generalization of the SuperStable Matching 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: Naoyuki Kamiyama
Pages: 1467  1482
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 14671482, June 2022.
A superstable matching is a solution concept in the variant of the stable matching problem in which the preferences may contain ties. Irving proposed a polynomialtime algorithm for the problem of checking the existence of a superstable matching and finding a superstable matching if a superstable matching exists. In this paper, we consider a matroid generalization of a superstable matching. We call our generalization of a superstable matching a superstable common independent set. This can be considered as a generalization of the matroid generalization of a stable matching for strict preferences proposed by Fleiner. We propose a polynomialtime algorithm for the problem of checking the existence of a superstable common independent set and finding a superstable common independent set if a superstable common independent set exists.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220621T07:00:00Z
DOI: 10.1137/21M1437214
Issue No: Vol. 36, No. 2 (2022)

 On Generalized Turán Results in Height Two Posets

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ózsef Balogh, Ryan R. Martin, Dániel T. Nagy, Balázs Patkós
Pages: 1483  1495
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 14831495, June 2022.
For given posets $P$ and $Q$ and an integer $n$, the generalized Turán problem for posets asks for the maximum number of copies of $Q$ in a $P$free subset of the $n$dimensional Boolean lattice, $2^{[n]}$. In this paper, among other results, we show the following: (i) For every $n\geq 5$, the maximum number of 2chains in a butterflyfree subfamily of $2^{[n]}$ is $\lceil\frac{n}{2} \rceil\binom{n}{\lfloor n/2\rfloor}$. (ii) For every fixed $s$, $t$ and $k$, a $K_{s,t}$free family in $2^{[n]}$ has $O (n\binom{n}{\lfloor n/2\rfloor})$ $k$chains. (iii) For every $n\geq 3$, the maximum number of $2$chains in an ${N}$free family is $\binom{n}{\lfloor n/2\rfloor}$, where ${N}$ is a poset on 4 distinct elements $\{p_1,p_2,q_1,q_2\}$ for which $p_1 < q_1$, $p_2 < q_1$ and $p_2 < q_2$. (iv) We also prove exact results for the maximum number of 2chains in a family that has no 5path and asymptotic estimates for the number of 2chains in a family with no 6path.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220623T07:00:00Z
DOI: 10.1137/21M1457254
Issue No: Vol. 36, No. 2 (2022)

 Hamiltonian Cycles in 4Connected Planar and Projective Planar
Triangulations with Few 4Separators
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: OnHei Solomon Lo, Jianguo Qian
Pages: 1496  1501
Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 14961501, June 2022.
Whitney proved in 1931 that every 4connected planar triangulation is hamiltonian. Later, Hakimi, Schmeichel, and Thomassen in 1979 conjectured that every such triangulation on $n$ vertices has at least $2(n  2)(n  4)$ hamiltonian cycles. Along this direction, Brinkmann, Souffriau, and Van Cleemput in 2018 established a linear lower bound on the number of hamiltonian cycles in 4connected planar triangulations. In stark contrast, Alahmadi, Aldred, and Thomassen in 2020 showed that every 5connected triangulation of the plane or the projective plane has exponentially many hamiltonian cycles. This gives the motivation to study the number of hamiltonian cycles of 4connected triangulations with few 4separators. Recently, Liu and Yu in 2021 showed that every 4connected planar triangulation with $O(n / \log n)$ 4separators has a quadratic number of hamiltonian cycles. By adapting the framework of Alahmadi, Aldred, and Thomassen, we strengthen the last two aforementioned results. We prove that every 4connected planar or projective planar triangulation with $O(n)$ 4separators has exponentially many hamiltonian cycles.
Citation: SIAM Journal on Discrete Mathematics
PubDate: 20220630T07:00:00Z
DOI: 10.1137/21M1419556
Issue No: Vol. 36, No. 2 (2022)
