Subjects -> MATHEMATICS (Total: 1013 journals)
    - APPLIED MATHEMATICS (92 journals)
    - GEOMETRY AND TOPOLOGY (23 journals)
    - MATHEMATICS (714 journals)
    - MATHEMATICS (GENERAL) (45 journals)
    - NUMERICAL ANALYSIS (26 journals)
    - PROBABILITIES AND MATH STATISTICS (113 journals)

MATHEMATICS (714 journals)            First | 1 2 3 4     

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

  First | 1 2 3 4     

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

    • Free pre-print version: Loading...

      Authors: Simona Boyadzhiyska, Dennis Clemens, Pranshu Gupta
      Pages: 1503 - 1528
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1503-1528, 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 co-authors and Fox and co-authors. 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: 2022-07-05T07:00:00Z
      DOI: 10.1137/21M1393273
      Issue No: Vol. 36, No. 3 (2022)
       
  • Lossless Prioritized Embeddings

    • Free pre-print version: Loading...

      Authors: Michael Elkin, Ofer Neiman
      Pages: 1529 - 1550
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1529-1550, 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. 829--858], 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. 829--858] 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 $2k-1$ 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 worst-case guarantee of $O(\log n)$ of the classical embedding of [N. Linial, E. London, and Y. Rabinovich, Combinatorica, 15 (1995), pp. 215--245]. 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 worst-case guarantee $2k-1$ in the distortion of the classical Matoušek embedding. We also provide a dimension-prioritized 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: 2022-07-05T07:00:00Z
      DOI: 10.1137/21M1436221
      Issue No: Vol. 36, No. 3 (2022)
       
  • Self-Dual Maps I: Antipodality

    • Free pre-print version: Loading...

      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 1551-1566, September 2022.
      A self-dual map $G$ is said to be antipodally self-dual 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 self-dual. In particular, we present a combinatorial characterization for map $G$ to be antipodally self-dual 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 self-dual 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: 2022-07-05T07:00:00Z
      DOI: 10.1137/20M1367076
      Issue No: Vol. 36, No. 3 (2022)
       
  • When Do Gomory--Hu Subtrees Exist'

    • Free pre-print version: Loading...

      Authors: Guyslain Naves, Bruce Shepherd
      Pages: 1567 - 1585
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1567-1585, September 2022.
      Gomory--Hu (GH) trees are a classical sparsification technique for graph connectivity. For an edge-capacitated undirected graph $G=(V,E)$ and subset $Z \subseteq V$ of terminals, a GH tree is an edge-capacitated 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 well-known that there does not always exist a GH tree which is a subgraph (or minor if $Z \neq V$) of $G$. We characterize those graph-terminal 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}$ terminal-minors arise, roughly speaking, from so-called Okamura--Seymour instances, planar graphs whose outside face contains all terminals. One consequence is a result on cut-sufficient 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 cut-sufficient for any demand graph $H$ on $Z$.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-07-05T07:00:00Z
      DOI: 10.1137/20M1356968
      Issue No: Vol. 36, No. 3 (2022)
       
  • Posets and Spaces of $k$-Noncrossing RNA Structures

    • Free pre-print version: Loading...

      Authors: Vincent Moulton, Taoyang Wu
      Pages: 1586 - 1611
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1586-1611, September 2022.
      RNA molecules are single-stranded 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 Penner--Waterman poset, and, using results from the theory of multitriangulations, we show that this is a pure poset of rank $k(2f-2k+1)+r-f-1$, whose geometric realization is the join of a simplicial sphere of dimension $k(f-2k)-1$ and an $\left((f+1)(k-1)-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: 2022-07-07T07:00:00Z
      DOI: 10.1137/21M1413316
      Issue No: Vol. 36, No. 3 (2022)
       
  • Spanning Trees at the Connectivity Threshold

    • Free pre-print version: Loading...

      Authors: Yahav Alon, Michael Krivelevich, Peleg Michaeli
      Pages: 1612 - 1626
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1612-1626, 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: 2022-07-11T07:00:00Z
      DOI: 10.1137/20M1380521
      Issue No: Vol. 36, No. 3 (2022)
       
  • The 9-Connected Excluded Minors for the Class of Quasi-graphic Matroids

    • Free pre-print version: Loading...

      Authors: Rong Chen
      Pages: 1627 - 1644
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1627-1644, September 2022.
      The class of quasi-graphic matroids, recently introduced by Geelen, Gerards, and Whittle, is minor closed and contains both the class of lifted-graphic 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 9-connected excluded minors for the class of quasi-graphic matroids.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-07-13T07:00:00Z
      DOI: 10.1137/21M142784X
      Issue No: Vol. 36, No. 3 (2022)
       
  • Rainbow Perfect Matchings for 4-Uniform Hypergraphs

    • Free pre-print version: Loading...

      Authors: Hongliang Lu, Yan Wang, Xingxing Yu
      Pages: 1645 - 1662
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1645-1662, 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 ${n-1\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. 333--366. on perfect matchings in 4-uniform hypergraphs.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-07-14T07:00:00Z
      DOI: 10.1137/21M1442383
      Issue No: Vol. 36, No. 3 (2022)
       
  • A General Framework for Hypergraph Coloring

    • Free pre-print version: Loading...

      Authors: Ian M. Wanless, David R. Wood
      Pages: 1663 - 1677
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1663-1677, 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 self-contained 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: 2022-07-14T07:00:00Z
      DOI: 10.1137/21M1421015
      Issue No: Vol. 36, No. 3 (2022)
       
  • Counterexamples to a Conjecture of Harris on Hall Ratio

    • Free pre-print version: Loading...

      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 1678-1686, September 2022.
      The Hall ratio of a graph $G$ is the maximum value of $v(H) / \alpha(H)$ taken over all non-null subgraphs $H \subseteq G$. For any graph, the Hall ratio is a lower-bound 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: 2022-07-18T07:00:00Z
      DOI: 10.1137/18M1229420
      Issue No: Vol. 36, No. 3 (2022)
       
  • On the Cover Time of the Emerging Giant

    • Free pre-print version: Loading...

      Authors: Alan M. Frieze, Wesley Pegden, Tomasz Tkocz
      Pages: 1687 - 1710
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1687-1710, 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: 2022-07-21T07:00:00Z
      DOI: 10.1137/21M1441468
      Issue No: Vol. 36, No. 3 (2022)
       
  • The Structure of $I_4$-Free and Triangle-Free Binary Matroids

    • Free pre-print version: Loading...

      Authors: Peter Nelson, Kazuhiro Nomoto
      Pages: 1711 - 1729
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1711-1729, September 2022.
      A simple binary matroid is called $I_4$-free if none of its rank-4 flats are independent sets. These objects can be equivalently defined as the sets $E$ of points in $\mbox{PG}(n-1,2)$ for which $E \cap F$ is not a basis of $F$ for any four-dimensional flat $F$. We prove a decomposition theorem that exactly determines the structure of all $I_4$-free and triangle-free matroids. In particular, our theorem implies that the $I_4$-free and triangle-free matroids have critical number at most 2.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-07-21T07:00:00Z
      DOI: 10.1137/20M1343099
      Issue No: Vol. 36, No. 3 (2022)
       
  • A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected
           Multisubgraph Problem in the Half-Integral Case

    • Free pre-print version: Loading...

      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 1730-1747, 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 2-edge 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 half-integral 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 2-edge 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 splitting-off theorem. Our proof naturally leads to a $\frac43$-approximation algorithm for half-integral instances. Given a half-integral solution $x$ to the LP for $\ensuremath{{2ECM}}$, we give an $O(n^2)$-time algorithm to obtain a 2-edge connected spanning multisubgraph of $\overline{G}$ with cost at most $\frac43 c^T x$. We also consider a related problem of finding a cheap 2-edge connected spanning subgraph of a 3-regular, 3-edge connected graph $G = (V,E)$ with arbitrary edge costs $c$. We give a polynomial-time Las Vegas algorithm that finds a random 2-edge 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: 2022-07-28T07:00:00Z
      DOI: 10.1137/20M1372822
      Issue No: Vol. 36, No. 3 (2022)
       
  • On Discrete LOG-Brunn--Minkowski Type Inequalities

    • Free pre-print version: Loading...

      Authors: María A. Hernández Cifre, Eduardo Lucas
      Pages: 1748 - 1760
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1748-1760, September 2022.
      The conjectured log-Brunn--Minkowski 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 log-Brunn--Minkowski 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) log-Brunn--Minkowski inequality for unconditional convex bodies. The corresponding results in the $L_p$ setting for $0
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-07-28T07:00:00Z
      DOI: 10.1137/21M1451725
      Issue No: Vol. 36, No. 3 (2022)
       
  • Grundy Distinguishes Treewidth from Pathwidth

    • Free pre-print version: Loading...

      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 1761-1787, September 2022.
      Structural graph parameters, such as treewidth, pathwidth, and clique-width, 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 fixed-parameter 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 W-hard 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 first-fit algorithm. We show that this well-studied 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 para-NP--hard for clique-width. Hence, Grundy Coloring nicely captures the complexity trade-offs between the three most well-studied parameters. Completing the picture, we show that Grundy Coloring is FPT parameterized by modular-width.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-07-28T07:00:00Z
      DOI: 10.1137/20M1385779
      Issue No: Vol. 36, No. 3 (2022)
       
  • EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs

    • Free pre-print version: Loading...

      Authors: Margarita Akhmejanova, Maksim Zhukovskii
      Pages: 1788 - 1799
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1788-1799, 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: 2022-08-02T07:00:00Z
      DOI: 10.1137/21M1429655
      Issue No: Vol. 36, No. 3 (2022)
       
  • Ideal Membership Problem over 3-Element CSPs with Dual Discriminator
           Polymorphism

    • Free pre-print version: Loading...

      Authors: Arpitha P. Bharathi, Monaldo Mastrolilli
      Pages: 1800 - 1822
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1800-1822, 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 3-element domain and the dual discriminator polymorphism (constraints under this polymorphism are a generalization of the 2-satisfiability 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 long-term goal of identifying when IMP$_d$ is polynomial time solvable for a finite domain.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-02T07:00:00Z
      DOI: 10.1137/21M1397131
      Issue No: Vol. 36, No. 3 (2022)
       
  • Nontrivial t-Intersecting Families for Vector Spaces

    • Free pre-print version: Loading...

      Authors: Mengyu Cao, Benjian Lv, Kaishun Wang, Sanming Zhou
      Pages: 1823 - 1847
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1823-1847, 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 well-known Hilton--Milner theorem for vector spaces.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-04T07:00:00Z
      DOI: 10.1137/20M1357421
      Issue No: Vol. 36, No. 3 (2022)
       
  • On Multicolor Ramsey Numbers and Subset Coloring of Hypergraphs

    • Free pre-print version: Loading...

      Authors: Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky
      Pages: 1848 - 1860
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1848-1860, 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. 69--77] 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 Ramsey-like 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^{(r-1)} (r \chi(H)) + r)$, where $\log^{y}$ is the $\log$ function applied $y$ times.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-11T07:00:00Z
      DOI: 10.1137/21M1462003
      Issue No: Vol. 36, No. 3 (2022)
       
  • A Small Maximal Sidon Set in ${\mathbb{Z}}_2^n$

    • Free pre-print version: Loading...

      Authors: Maximus Redman, Lauren Rose, Raphael Walker
      Pages: 1861 - 1867
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1861-1867, September 2022.
      A Sidon set is a subset of an Abelian group with the property that each sum of two distinct elements is distinct. We construct a small maximal Sidon set of size $O((n \cdot 2^n)^{1/3})$ in the group ${\mathbb{Z}}_2^n$, generalizing a result of Ruzsa concerning maximal Sidon sets in the integers.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-16T07:00:00Z
      DOI: 10.1137/21M1454663
      Issue No: Vol. 36, No. 3 (2022)
       
  • A General Family of MSRD Codes and PMDS Codes with Smaller Field Sizes
           from Extended Moore Matrices

    • Free pre-print version: Loading...

      Authors: Umberto MartÍnez-Pen͂as
      Pages: 1868 - 1886
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1868-1886, September 2022.
      We construct six new explicit families of linear maximum sum-rank distance (MSRD) codes, each of which has the smallest field sizes among all known MSRD codes for some parameter regime. Using them and a previous result of the author, we provide two new explicit families of linear partial maximum distance separable (PMDS) codes with smaller field sizes than previous PMDS codes for some parameter regimes. Our approach is to characterize evaluation points that turn extended Moore matrices into the parity-check matrix of a linear MSRD code. We then produce such sequences from codes with good Hamming-metric parameters. The six new families of linear MSRD codes with smaller field sizes are obtained using MDS codes, Hamming codes, Bose--Chaudhuri--Hocquenghem codes, and three algebraic-geometry codes. The MSRD codes based on Hamming codes, of minimum sum-rank distance 3, meet a recent bound by Byrne, Gluesing-Luerssen, and Ravagnani [IEEE Trans. Inform. Theory, 67 (2021), pp. 6456--6475].
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-16T07:00:00Z
      DOI: 10.1137/20M1386001
      Issue No: Vol. 36, No. 3 (2022)
       
  • Adapting the Directed Grid Theorem into an FPT Algorithm

    • Free pre-print version: Loading...

      Authors: Victor Campos, Raul Lopes, Ana Karolinna Maia, Ignasi Sau
      Pages: 1887 - 1917
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1887-1917, September 2022.
      The grid theorem of Robertson and Seymour [J. Combin. Theory Ser. B, 41 (1986), pp. 92--114] is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the grid theorem in digraphs was conjectured by Johnson et al. [J. Combin. Theory Ser. B, 82 (2001), pp. 138--154] and proved by Kawarabayashi and Kreutzer [Proceedings of STOC, 2015, pp. 655--664]. Namely, they showed that there is a function $f(k)$ such that every digraph of directed tree-width at least $f(k)$ contains a cylindrical grid of order $k$ as a butterfly minor, and stated that their proof can be turned into an \sf XP algorithm, with parameter $k$, that either constructs a decomposition of the appropriate width or finds the claimed large cylindrical grid as a butterfly minor. In this paper, we adapt some of the steps of the proof of Kawarabayashi and Kreutzer to improve this \sf XP algorithm into a fixed-parameter tractable (\sf FPT) algorithm. Toward this, our main technical contributions are two \sf FPT algorithms with parameter $k$. The first one either produces an arboreal decomposition of width $3k-2$ or finds a haven of order $k$ in a digraph $D$, improving on the original result for arboreal decompositions by Johnson et al. [J. Combin. Theory Ser. B, 82 (2001), pp. 138--154]. The second algorithm finds a well-linked set of order $k$ in a digraph $D$ of large directed tree-width. As tools to prove these results, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices $T$ in \sf FPT time with parameter $ T $, a result that we consider to be of its own interest.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-16T07:00:00Z
      DOI: 10.1137/21M1452664
      Issue No: Vol. 36, No. 3 (2022)
       
  • On Lattice Width of Lattice-Free Polyhedra and Height of Hilbert Bases

    • Free pre-print version: Loading...

      Authors: Martin Henk, Stefan Kuhlmann, Robert Weismantel
      Pages: 1918 - 1942
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1918-1942, September 2022.
      We study the lattice width of lattice-free polyhedra given by ${A}{x}\leq{b}$ in terms of $\Delta({A})$, the maximal $n\times n$ minor in absolute value of ${A}\in\mathbb{Z}^{m\times n}$. Our main contribution is to link the lattice width of lattice-free polyhedra to the height of Hilbert bases and to the diameter of finite abelian groups. This leads to a bound on the lattice width of lattice-free pyramids which solely depends on $\Delta({A})$ provided a conjecture regarding the height of Hilbert bases holds. Further, we exploit a combination of techniques to obtain novel bounds on the lattice width of simplices. A second part of the paper is devoted to a study of the above-mentioned Hilbert basis conjecture. We give a complete characterization of the Hilbert basis if $\Delta({A}) = 2$ which implies the conjecture in that case and prove its validity for simplicial cones.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-16T07:00:00Z
      DOI: 10.1137/21M145416X
      Issue No: Vol. 36, No. 3 (2022)
       
  • On the Power of Choice for Boolean Functions

    • Free pre-print version: Loading...

      Authors: Nicolas Fraiman, Lyuben Lichev, Dieter Mitsche
      Pages: 1943 - 1954
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1943-1954, September 2022.
      In this paper we consider a variant of the well-known Achlioptas process for graphs adapted to monotone Boolean functions. Fix a number of choices $r\in \mathbb N$ and a sequence of increasing functions $(f_n)_{n\ge 1}$ such that, for every $n\ge 1$, $f_n:\{0,1\}^n\mapsto \{0,1\}$. Given $n$ bits which are all initially equal to 0, at each step $r$ 0-bits are sampled uniformly at random and are proposed to an agent. Then, the agent selects one of the proposed bits and turns it from 0 to 1 with the goal to reach $f_n^{-1}(1)$ as quickly as possible. We nearly characterize the conditions on $(f_n)_{n\ge 1}$ under which an acceleration by a factor of $r(1+o(1))$ is possible and underline the wide applicability of our results by giving examples from the fields of Boolean functions and graph theory.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-16T07:00:00Z
      DOI: 10.1137/21M1449245
      Issue No: Vol. 36, No. 3 (2022)
       
  • Elimination Distances, Blocking Sets, and Kernels for Vertex Cover

    • Free pre-print version: Loading...

      Authors: Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
      Pages: 1955 - 1990
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1955-1990, September 2022.
      The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for ${\mathsf{NP}}$-hard problems. Motivated by the great variety of positive and negative results for kernelization for Vertex Cover subject to different parameters and graph classes, we seek to unify and generalize them using so-called blocking sets. A blocking set is a set of vertices such that no optimal vertex cover contains all vertices in the blocking set, and the study of minimal blocking sets played implicit and explicit roles in many existing results. We show that in the most-studied setting, parameterized by the size of a deletion set to a specified graph class ${\mathcal{C}}$, bounded minimal blocking set size is necessary but not sufficient to get a polynomial kernelization. Under mild technical assumptions, bounded minimal blocking set size is shown to allow an essentially tight polynomial-time reduction in the number of connected components. We then determine the exact maximum size of minimal blocking sets for graphs of bounded elimination distance to any hereditary class $\mathcal{C}$, including the case of graphs of bounded treedepth. We get similar but not tight bounds for certain nonhereditary classes $\mathcal{C}$, including the class ${\mathcal{C}}_{{\mathrm{LP}}}$ of graphs where integral and fractional vertex cover size coincide. These bounds allow us to derive polynomial kernels for Vertex Cover parameterized by the size of a deletion set to graphs of bounded elimination distance to, e.g., forest, bipartite, or ${\mathcal{C}}_{\mathrm{LP}}$ graphs.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-24T07:00:00Z
      DOI: 10.1137/20M1335285
      Issue No: Vol. 36, No. 3 (2022)
       
  • The Flow Index of Regular Class I Graphs

    • Free pre-print version: Loading...

      Authors: Jiaao Li, Xueliang Li, Meiling Wang
      Pages: 1991 - 2003
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1991-2003, September 2022.
      For integers $k$ and $d$ with $k\ge 2d>0$, a circular ${k}/{d}$-flow of a graph $G$ is an orientation together with a mapping from $E(G)$ to $\{\pm d, \pm (d+1),\ldots,\pm (k-d)\}$ such that, for each vertex of $G$, the sum of images on outgoing edges is equal to the sum of images on incoming edges. Related to the four color problem, a classical result of Tutte shows that a cubic graph admits a circular $4/1$-flow if and only if it is Class I (i.e., $3$-edge-colorable). Tutte's $3$-flow conjecture implies that every $5$-regular Class I graph admits a nowhere-zero $3$-flow (equivalently, a circular $6/2$-flow) as a special case. Steffen in 2015 conjectured that every $(2t+1)$-regular Class I graph admits a circular $(2t+2)/t$-flow. He also proposed a more general conjecture that every $(2t+1)$-odd-edge-connected $(2t+1)$-regular graph admits a circular $(2t+2)/t$-flow for any integer $t\ge 2$, which includes the circular flow conjecture of Jaeger (1981) stating that every $2t$-edge-connected graph admits a circular $(2t+2)/t$-flow for any even $t\ge 2$. Jaeger's conjecture was disproved in 2018 for all even $t\ge 6$, and based on these results, Mattiolo and Steffen recently constructed counterexamples to Steffen's conjecture for Class I graphs when $t=4k+2$ for any integer $k\ge 1$. In this paper, we extend the above results and construct infinitely many $2t$-edge-connected $(2t+1)$-regular Class I graphs without circular $(2t+2)/t$-flows for any integer $t\in \{6,8,10\}$ or $t\geq 12$. Our result provides more general counterexamples to Steffen's two conjectures for both even and odd $t$ and simultaneously generalizes the counterexamples of Jaeger's circular flow conjecture to regular Class I graphs.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-24T07:00:00Z
      DOI: 10.1137/21M1393169
      Issue No: Vol. 36, No. 3 (2022)
       
  • Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph

    • Free pre-print version: Loading...

      Authors: Sepehr Hajebi, Yanjia Li, Sophie Spirkl
      Pages: 2004 - 2027
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2004-2027, September 2022.
      For a positive integer $r$ and graphs $G$ and $H$, we denote by $G+H$ the disjoint union of $G$ and $H$ and by $rH$ the union of $r$ mutually disjoint copies of $H$. Also, we say $G$ is $H$-free if $H$ is not isomorphic to an induced subgraph of $G$. We use $P_t$ to denote the path on $t$ vertices. For a fixed positive integer $k$, the List-$k$-Coloring Problem is to decide, given a graph $G$ and a list $L(v)\subseteq \{1,\ldots,k\}$ of colors assigned to each vertex $v$ of $G$, whether $G$ admits a proper coloring $\phi$ with $\phi(v)\in L(v)$ for every vertex $v$ of $G$, and the $k$-Coloring Problem is the List-$k$-Coloring Problem restricted to instances with $L(v)=\{1,\ldots, k\}$ for every vertex $v$ of $G$. We prove that, for every positive integer $r$, the List-$5$-Coloring Problem restricted to $rP_3$-free graphs can be solved in polynomial time. Together with known results, this gives a complete dichotomy for the complexity of the List-5-Coloring Problem restricted to $H$-free graphs: For every graph $H$, assuming P$\neq$NP, the List-5-Coloring Problem restricted to $H$-free graphs can be solved in polynomial time if and only if, $H$ is an induced subgraph of either $rP_3$ or $P_5+rP_1$ for some positive integer $r$. As a hardness counterpart, we also show that the $k$-Coloring Problem restricted to $rP_4$-free graphs is NP-complete for all $k\geq 5$ and $r\geq 2$.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-30T07:00:00Z
      DOI: 10.1137/21M1443352
      Issue No: Vol. 36, No. 3 (2022)
       
  • Planar Turán Number of the 6-Cycle

    • Free pre-print version: Loading...

      Authors: Debarun Ghosh, Ervin Györi, Ryan R. Martin, Addisu Paulos, Chuanqi Xiao
      Pages: 2028 - 2050
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2028-2050, September 2022.
      Let ${\rm ex}_{\mathcal{P}}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$, ${\rm ex}_{\mathcal{P}}(n,T,H)$ is the well-studied function, the planar Turán number of $H$, denoted by ${\rm ex}_{\mathcal{P}}(n,H)$. The topic of extremal planar graphs was initiated by Dowden [J. Graph Theory, 83 (2016), pp. 213--230]. He obtained a sharp upper bound for both ${\rm ex}_{\mathcal{P}}(n,C_4)$ and ${\rm ex}_{\mathcal{P}}(n,C_5)$. Later on, Lan, Shi, and Song continued this topic and proved that ${\rm ex}_{\mathcal{P}}(n,C_6)\leq \frac{18(n-2)}{7}$. In this paper, we give a sharp upper bound ${\rm ex}_{\mathcal{P}}(n,C_6) \leq \frac{5}{2}n-7$, for all $n\geq 18$, which improves Lan, Shi, and Song's result. We also pose a conjecture on ${\rm ex}_{\mathcal{P}}(n,C_k)$, for $k\geq 7$.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-30T07:00:00Z
      DOI: 10.1137/21M140657X
      Issue No: Vol. 36, No. 3 (2022)
       
  • The Smallest Classes of Binary and Ternary Matroids Closed under Direct
           Sums and Complements

    • Free pre-print version: Loading...

      Authors: James Oxley, Jagdeep Singh
      Pages: 2051 - 2072
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2051-2072, September 2022.
      The class of cographs or complement-reducible graphs is the class of graphs that can be generated from $K_1$ using the operations of disjoint union and complementation. By analogy, this paper introduces the class of binary comatroids as the class of matroids that can be generated from the empty matroid using the operations of direct sum and taking complements inside of binary projective space. We show that a proper flat of a binary comatroid is a binary comatroid. Our main result identifies those binary noncomatroids for which every proper flat is a binary comatroid. The paper also proves the corresponding results for ternary matroids.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-30T07:00:00Z
      DOI: 10.1137/21M1453852
      Issue No: Vol. 36, No. 3 (2022)
       
  • Exchange Properties of Finite Set-Systems

    • Free pre-print version: Loading...

      Authors: Peter Frankl, János Pach, Dömötör Pálvölgyi
      Pages: 2073 - 2081
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2073-2081, September 2022.
      In a recent breakthrough, Adiprasito, Avvakumov, and Karasev constructed a triangulation of the $n$-dimensional real projective space with a subexponential number of vertices. They reduced the problem to finding a small downward closed set-system $\cal F$ covering an $n$-element ground set which satisfies the following condition: for any two disjoint members $A, B\in\cal F$, there exist $a\in A$ and $b\in B$ such that either $B\cup\{a\}\in\cal F$ and $A\cup\{b\}\setminus\{a\}\in\cal F$, or $A\cup\{b\}\in\cal F$ and $B\cup\{a\}\setminus\{b\}\in\cal F$. Denoting by $f(n)$ the smallest cardinality of such a family $\cal F$, they proved that $f(n) B $, there exists $a\in A$ such that $B\cup\{a\}\in\cal F$. In this case, we prove that the size of the smallest $\cal F$ satisfying this stronger condition lies between $2^{\Omega(\sqrt{n}\log n)}$ and $2^{O(n\log\log n/\log n)}$.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-30T07:00:00Z
      DOI: 10.1137/21M145149X
      Issue No: Vol. 36, No. 3 (2022)
       
  • Shorter Labeling Schemes for Planar Graphs

    • Free pre-print version: Loading...

      Authors: Marthe Bonamy, Cyril Gavoille, Michał Pilipczuk
      Pages: 2082 - 2099
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2082-2099, September 2022.
      An adjacency labeling scheme for a given class of graphs is an algorithm that, for every graph $G$ from the class, assigns bit strings (labels) to vertices of $G$ so that for any two vertices $u,v$, whether $u$ and $v$ are adjacent can be determined by a fixed procedure that examines only their labels. It is known that planar graphs with $n$ vertices admit a labeling scheme with labels of bit length $(2+o(1))\log{n}$. In this work we improve this bound by designing a labeling scheme with labels of bit length $(\frac{4}{3}+o(1))\log{n}$. All the labels of the input graph can be computed in polynomial time, while adjacency can be decided from the labels in constant time. In graph-theoretical terms, this implies an explicit construction of a graph on $n^{4/3+o(1)}$ vertices that contains all planar graphs on $n$ vertices as induced subgraphs, improving the previous best upper bound of $n^{2+o(1)}$. Our labeling scheme can be generalized to larger classes of topologically constrained graphs, for instance, to graphs embeddable in any fixed surface or to $k$-planar graphs for any fixed $k$, at the cost of larger second-order terms.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-31T07:00:00Z
      DOI: 10.1137/20M1330464
      Issue No: Vol. 36, No. 3 (2022)
       
  • The Extremal Function for Excluding Geometry Minors over Prime Fields

    • Free pre-print version: Loading...

      Authors: Peter Nelson, Zach Walsh
      Pages: 2100 - 2120
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2100-2120, September 2022.
      A frame template over a field $\mathbb F$ describes the precise way in which a given $\mathbb F$-representable matroid is close to being a frame matroid. Our main result determines the maximum-rank projective or affine geometry that is described by a given frame template over a prime field. Subject to the matroid minors hypothesis of Geelen, Gerards, and Whittle, we use our result to determine, for each projective or affine geometry $N$ over a prime field $\mathbb F$, a best-possible upper bound on the number of elements in a simple $\mathbb F$-representable matroid $M$ of sufficiently large rank with no $N$-minor.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-08-31T07:00:00Z
      DOI: 10.1137/21M1410750
      Issue No: Vol. 36, No. 3 (2022)
       
  • Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and
           Parity Problems

    • Free pre-print version: Loading...

      Authors: Kazuki Matoya, Taihei Oki
      Pages: 2121 - 2158
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2121-2158, September 2022.
      Spanning trees are a representative example of linear matroid bases that are efficiently countable. Perfect matchings of Pfaffian bipartite graphs are a countable example of common bases of two matrices. Generalizing these two, Webb Counting Bases, Ph.D. thesis, University of Waterloo, 2004 introduced the notion of Pfaffian pairs as a pair of matrices for which counting of their common bases is tractable via the Cauchy--Binet formula. This paper studies counting on linear matroid problems extending Webb's work. We first introduce “Pfaffian parities” as an extension of Pfaffian pairs to the linear matroid parity problem, which is a common generalization of the linear matroid intersection problem and the matching problem. We show that a large number of efficiently countable discrete structures are interpretable as special cases of Pfaffian pairs and parities. Our study then turns to algorithmic aspects. We observe that the fastest randomized algorithms for the linear matroid intersection and parity problems by Harvey SIAM J. Comput., 39 (2009), pp. 679--702 and Cheung, Lau, and Leung ACM Trans. Algorithms, 10 (2014), pp. 1--26 can be derandomized for Pfaffian pairs and parities. We further present polynomial-time algorithms to count the number of minimum-weight solutions on weighted Pfaffian pairs and parities. Our algorithms make use of Frank's weight-splitting lemma for the weighted matroid intersection problem and the algebraic optimality criterion of the weighted linear matroid parity problem given by Iwata and Kobayashi SIAM J. Comput., 51 (2002) pp. STOC17-238--STOC17-280.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-09-06T07:00:00Z
      DOI: 10.1137/21M1421751
      Issue No: Vol. 36, No. 3 (2022)
       
  • The Complexity of Approximating the Complex-Valued Ising Model on Bounded
           Degree Graphs

    • Free pre-print version: Loading...

      Authors: Andreas Galanis, Leslie A. Goldberg, Andres Herrera-Poyatos
      Pages: 2159 - 2204
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2159-2204, September 2022.
      We study the complexity of approximating the partition function $Z_{\mathrm{Ising}}(G; \beta)$ of the Ising model in terms of the relation between the edge interaction $\beta$ and a parameter $\Delta$ which is an upper bound on the maximum degree of the input graph $G$. Following recent trends in both statistical physics and algorithmic research, we allow the edge interaction $\beta$ to be any complex number. Many recent partition function results focus on complex parameters, both because of physical relevance and because of the key role of the complex case in delineating the tractability/intractability phase transition of the approximation problem. In this work we establish both new tractability results and new intractability results. Our tractability results show that $Z_{\mathrm{Ising}}(-; \beta)$ has an FPTAS when $\lvert \beta - 1 \rvert / \lvert \beta + 1 \rvert < \tan(\pi / (4 \Delta - 4))$. The core of the proof is showing that there are no inputs $G$ that make the partition function $0$ when $\beta$ is in this range. Our result significantly extends the known zero-free region of the Ising model (and hence the known approximation results). Our intractability results show that it is $\mathrm{\#P}$-hard to multiplicatively approximate the norm and to additively approximate the argument of $Z_{\mathrm{Ising}}(-; \beta)$ when $\beta \in \mathbb{C}$ is an algebraic number such that $\beta \not \in \mathbb{R} \cup \{i, -i\}$ and $\lvert \beta - 1\rvert / \lvert \beta + 1 \rvert> 1 / \sqrt{\Delta - 1}$. These are the first results to show intractability of approximating $Z_{\mathrm{Ising}}(-, \beta)$ on bounded degree graphs with complex $\beta$. Moreover, we demonstrate situations in which zeros of the partition function imply hardness of approximation in the Ising model.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-09-06T07:00:00Z
      DOI: 10.1137/21M1454043
      Issue No: Vol. 36, No. 3 (2022)
       
  • Faster 3-Coloring of Small-Diameter Graphs

    • Free pre-print version: Loading...

      Authors: Michał Dȩbsk, Marta Piecyk, Paweł Rza̧żewski
      Pages: 2205 - 2224
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2205-2224, September 2022.
      We study the 3-Coloring problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for $n$-vertex diameter-2 graphs this problem can be solved in subexponential time $2^{\mathcal{O}(\sqrt{n \log n})}$. Whether the problem can be solved in polynomial time remains a well-known open question in the area of algorithmic graph theory. In this paper we present an algorithm that solves 3-Coloring in $n$-vertex diameter-2 graphs in time $2^{\mathcal{O}(n^{1/3} \log^{2} n)}$. This is the first improvement upon the algorithm of Mertzios and Spirakis in the general case, i.e., without putting any further restrictions on the instance graph. In addition to standard branchings and reducing the problem to an instance of 2-Sat, the crucial building block of our algorithm is a combinatorial observation about 3-colorable diameter-2 graphs, which is proven using a probabilistic argument. As a side result, we show that 3-Coloring can be solved in time $2^{\mathcal{O}( (n \log n)^{2/3})}$ in $n$-vertex diameter-3 graphs. This is the first algorithm for 3-Coloring which works in subexponential time for all diameter-3 graphs. We also discuss generalizations of our results to the weighted variant of 3-Coloring.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-09-06T07:00:00Z
      DOI: 10.1137/21M1447714
      Issue No: Vol. 36, No. 3 (2022)
       
  • Poincaré Polynomials of Odd Diagram Classes

    • Free pre-print version: Loading...

      Authors: Neil Fan, Peter Guo
      Pages: 2225 - 2237
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2225-2237, September 2022.
      An odd diagram class is a set of permutations with the same odd diagram. Brenti, Carnevale, and Tenner [Comb. Theory, 2 (2022), 13] showed that each odd diagram class is an interval in the Bruhat order. They conjectured that such intervals are rank-symmetric. In this paper, we present an algorithm to partition an odd diagram class in a uniform manner. As an application, we obtain that the Poincaré polynomial of an odd diagram class factors into polynomials of the form $1+t+\cdots+t^m$. This, in particular, resolves the conjecture of Brenti, Carnevale, and Tenner [Comb. Theory, 2 (2022), 13].
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-09-12T07:00:00Z
      DOI: 10.1137/22M1470517
      Issue No: Vol. 36, No. 3 (2022)
       
  • Rank of the Vertex-Edge Incidence Matrix of r-Out Hypergraphs

    • Free pre-print version: Loading...

      Authors: Colin Cooper, Alan Frieze
      Pages: 2238 - 2257
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2238-2257, September 2022.
      We consider the rank of a class of sparse Boolean matrices of size $n \times n$. In particular, we show that the probability that such a matrix has full rank, and is thus invertible, is a positive constant with value about 0.2574 for large $n$. The matrices arise as the vertex-edge incidence matrix of 1-out 3-uniform hypergraphs. The result that the null space is bounded in expectation can be contrasted with results for the usual models of sparse Boolean matrices, based on the vertex-edge incidence matrix of random $k$-uniform hypergraphs. For this latter model, the expected co-rank is linear in the number of vertices $n$, [A. Coja-Oghlan et al., in Proceedings of SODA, 2020, pp. 579--591], [C. Cooper, A. M. Frieze, and W. Pegden, in Proceedings of SODA, 2019, pp. 946--955]. For fields of higher order, the co-rank is typically Poisson distributed.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-09-13T07:00:00Z
      DOI: 10.1137/21M1467572
      Issue No: Vol. 36, No. 3 (2022)
       
  • The Overfullness of Graphs with Small Minimum Degree and Large Maximum
           Degree

    • Free pre-print version: Loading...

      Authors: Yan Cao, Guantao Chen, Guangming Jing, Songling Shan
      Pages: 2258 - 2270
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2258-2270, September 2022.
      Given a simple graph $G$, denote by $\Delta(G)$, $\delta(G)$, and $\chi'(G)$ the maximum degree, the minimum degree, and the chromatic index of $G$, respectively. We say $G$ is $\Delta$-critical if $\chi'(G)=\Delta(G)+1$ and $\chi'(H)\le \Delta(G)$ for every proper subgraph $H$ of $G$, and $G$ is overfull if $ E(G)>\Delta(G) \lfloor V(G) /2 \rfloor$. Since a maximum matching in $G$ can have size at most $\lfloor V(G) /2 \rfloor$, it follows that $\chi'(G) = \Delta(G) +1$ if $G$ is overfull. Conversely, let $G$ be a $\Delta$-critical graph. The well known overfull conjecture of Chetwynd and Hilton asserts that $G$ is overfull provided $\Delta(G)> V(G) /3$. In this paper, we show that any $\Delta$-critical graph $G$ is overfull if $\Delta(G) - 7\delta(G)/4\ge (3 V(G) -17)/4$.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-09-13T07:00:00Z
      DOI: 10.1137/21M1432776
      Issue No: Vol. 36, No. 3 (2022)
       
  • Distribution of Distances in Five Dimensions and Related Problems

    • Free pre-print version: Loading...

      Authors: François Clément, Thang Pham
      Pages: 2271 - 2281
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2271-2281, September 2022.
      In this paper, we study the Erdös--Falconer distance problem in five dimensions for sets of Cartesian product structures. More precisely, we show that for $A\subset \mathbb{F}_p$ with $ A \gg p^{\frac{13}{22}}$, then $\Delta(A^5)=\mathbb{F}_p$. When $ A-A \sim A $, we are able to obtain stronger conclusions as follows: łinebreak 1. If $p^{13/22}\ll A \ll p^{\frac{2}{3}}$, then $(A-A)^2+A^2+A^2+A^2+A^2=\mathbb{F}_p$. 2. If $p^{4/7}\ll A \ll p^{\frac{2}{3}}$, then $(A-A)^2+(A-A)^2+A^2+A^2+A^2+A^2=\mathbb{F}_p$. We also prove that if $p^{4/7}\ll A-A =K A \le p^{5/8}$, then $ A^2+A^2 \gg \min \{ \frac{p}{K^4}, \frac{ A ^{8/3}}{K^{7/3}p^{2/3}}\}$. As a consequence, $ A^2+A^2 \gg p$ when $ A \sim p^{5/8}$ and $K\sim 1$, where $A^2=\{x^2: x\in A\}$.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-09-22T07:00:00Z
      DOI: 10.1137/21M1447088
      Issue No: Vol. 36, No. 3 (2022)
       
  • A Spectral Independence View on Hard Spheres via Block Dynamics

    • Free pre-print version: Loading...

      Authors: Tobias Friedrich, Andreas Göbel, Martin S. Krejca, Marcus Pappik
      Pages: 2282 - 2322
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 2282-2322, September 2022.
      The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand canonical partition function of the hard-sphere model in $d$ dimensions. Up to a fugacity of $\lambda < e/2^d$, the runtime of our algorithm is polynomial in the volume of the system. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance, we use block dynamics, a Markov chain that generalizes the more frequently studied Glauber dynamics by grouping the vertices of the graph into blocks and updating an entire block instead of a single vertex in each step. We prove rapid mixing of block dynamics, based on disjoint cliques as blocks, up to the tree threshold of the univariate hard-core model. This is achieved by adapting the spectral expansion method, which was recently used for bounding the mixing time of Glauber dynamics within the same parameter regime.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-09-22T07:00:00Z
      DOI: 10.1137/21M143697X
      Issue No: Vol. 36, No. 3 (2022)
       
  • An Improved Upper Bound for the Ring Loading Problem

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

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

    • Free pre-print version: Loading...

      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 1249-1273, 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 quasi-polynomial time, a near-optimal 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: 2022-06-01T07:00:00Z
      DOI: 10.1137/21M1425487
      Issue No: Vol. 36, No. 2 (2022)
       
  • Perfect Matchings in the Semirandom Graph Process

    • Free pre-print version: Loading...

      Authors: Pu Gao, Calum MacRury, Paweł Prałat
      Pages: 1274 - 1290
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1274-1290, 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: 2022-06-01T07:00:00Z
      DOI: 10.1137/21M1446939
      Issue No: Vol. 36, No. 2 (2022)
       
  • Completing and Extending Shellings of Vertex Decomposable Complexes

    • Free pre-print version: Loading...

      Authors: Michaela Coleman, Anton Dochtermann, Nathan Geist, Suho Oh
      Pages: 1291 - 1305
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1291-1305, 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_{n-1}^{(d)}$, the $d$-skeleton of the $(n-1)$-dimensional simplex. A well-known 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 ridge-chordal 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: 2022-06-02T07:00:00Z
      DOI: 10.1137/21M1445119
      Issue No: Vol. 36, No. 2 (2022)
       
  • The Ising Antiferromagnet and Max Cut on Random Regular Graphs

    • Free pre-print version: Loading...

      Authors: Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei, Gregory B. Sorkin
      Pages: 1306 - 1342
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1306-1342, 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 information-theoretic threshold of the disassortative stochastic block model on random regular graphs coincides with the Kesten--Stigum bound.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-06-02T07: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 pre-print version: Loading...

      Authors: Raphael M. Steiner
      Pages: 1343 - 1362
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1343-1362, June 2022.
      A conjecture by Lichiardopol [SIAM J. Discrete Math., 28 (2014), pp. 1618--1627] states that for every $k \ge 1$ there exists an integer $g(k)$ such that every digraph of minimum out-degree at least $g(k)$ contains $k$ vertex-disjoint directed cycles of pairwise distinct lengths. Motivated by Lichiardopol's conjecture, we study the existence of vertex-disjoint 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$ vertex-disjoint 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 arc-disjoint 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 in-degree at least $K$ contains 3 vertex-disjoint directed cycles of pairwise distinct lengths.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-06-06T07:00:00Z
      DOI: 10.1137/20M1382398
      Issue No: Vol. 36, No. 2 (2022)
       
  • A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense
           Regular Graphs

    • Free pre-print version: Loading...

      Authors: Viresh Patel, Fabian Stroh
      Pages: 1363 - 1393
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1363-1393, June 2022.
      We give a polynomial-time 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 polynomial-time 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 NP-complete 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: 2022-06-07T07:00:00Z
      DOI: 10.1137/20M1356191
      Issue No: Vol. 36, No. 2 (2022)
       
  • Planarity and Genus of Sparse Random Bipartite Graphs

    • Free pre-print version: Loading...

      Authors: Tuan A. Do, Joshua Erde, Mihyun Kang
      Pages: 1394 - 1415
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1394-1415, 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: 2022-06-13T07:00:00Z
      DOI: 10.1137/20M1341817
      Issue No: Vol. 36, No. 2 (2022)
       
  • Robust Connectivity of Graphs on Surfaces

    • Free pre-print version: Loading...

      Authors: Peter Bradshaw, Tomáš MasařÍk, Jana Novotná, Ladislav Stacho
      Pages: 1416 - 1435
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1416-1435, 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 well-known NP-hard 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. Leibniz-Zent. 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 edge-maximal 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 long-standing 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: 2022-06-16T07:00:00Z
      DOI: 10.1137/21M1417077
      Issue No: Vol. 36, No. 2 (2022)
       
  • Online Assortment and Market Segmentation under Bertrand Competition with
           Set-Dependent Revenues

    • Free pre-print version: Loading...

      Authors: S. Rasoul Etesami
      Pages: 1436 - 1466
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1436-1466, 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 well-known multinomial logit model, a well-justified 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 buyer-seller 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: 2022-06-16T07:00:00Z
      DOI: 10.1137/21M1400134
      Issue No: Vol. 36, No. 2 (2022)
       
  • A Matroid Generalization of the Super-Stable Matching Problem

    • Free pre-print version: Loading...

      Authors: Naoyuki Kamiyama
      Pages: 1467 - 1482
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1467-1482, June 2022.
      A super-stable matching is a solution concept in the variant of the stable matching problem in which the preferences may contain ties. Irving proposed a polynomial-time algorithm for the problem of checking the existence of a super-stable matching and finding a super-stable matching if a super-stable matching exists. In this paper, we consider a matroid generalization of a super-stable matching. We call our generalization of a super-stable matching a super-stable 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 polynomial-time algorithm for the problem of checking the existence of a super-stable common independent set and finding a super-stable common independent set if a super-stable common independent set exists.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-06-21T07:00:00Z
      DOI: 10.1137/21M1437214
      Issue No: Vol. 36, No. 2 (2022)
       
  • On Generalized Turán Results in Height Two Posets

    • Free pre-print version: Loading...

      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 1483-1495, 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 2-chains in a butterfly-free 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 2-chains in a family that has no 5-path and asymptotic estimates for the number of 2-chains in a family with no 6-path.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-06-23T07:00:00Z
      DOI: 10.1137/21M1457254
      Issue No: Vol. 36, No. 2 (2022)
       
  • Hamiltonian Cycles in 4-Connected Planar and Projective Planar
           Triangulations with Few 4-Separators

    • Free pre-print version: Loading...

      Authors: On-Hei Solomon Lo, Jianguo Qian
      Pages: 1496 - 1501
      Abstract: SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1496-1501, June 2022.
      Whitney proved in 1931 that every 4-connected 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 4-connected planar triangulations. In stark contrast, Alahmadi, Aldred, and Thomassen in 2020 showed that every 5-connected 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 4-connected triangulations with few 4-separators. Recently, Liu and Yu in 2021 showed that every 4-connected planar triangulation with $O(n / \log n)$ 4-separators 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 4-connected planar or projective planar triangulation with $O(n)$ 4-separators has exponentially many hamiltonian cycles.
      Citation: SIAM Journal on Discrete Mathematics
      PubDate: 2022-06-30T07:00:00Z
      DOI: 10.1137/21M1419556
      Issue No: Vol. 36, No. 2 (2022)
       
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
 


Your IP address: 44.201.95.84
 
Home (Search)
API
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-