SIAM Journal on Discrete Mathematics

Submodularity is one of the most important properties in combinatorial optimization, and $k$-submodularity is a generalization of submodularity. Maximization of a $k$-submodular function requires an exponential number of value oracle queries, and ...

The notion of goodness for Ramsey numbers was introduced by Burr and Erdös in 1983. For graphs $G$ and $H$, let $G+H$ be the graph obtained from disjoint $G$ and $H$ by adding all edges between the vertices of $G$ and $H$. Denote $nH$ by the union of $n$ ...

We prove that if $G$ is a graph without 3-cycles and 4-cycles, then the discrete cubical homology of $G$ is trivial in dimension $d$ for all $d\ge 2$. We also construct a sequence $\{G_d\}$ of graphs such that this homology is nontrivial in dimension $d$ ...

This paper deals with the characterization and the recognition of graph classes. A popular way to characterize a graph class is to list a minimal set of forbidden induced subgraphs. Unfortunately, this strategy rarely leads to a very efficient recognition ...

Haviv [European J. Combin., 81 (2019), pp. 84--97] has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over $\mathbb{R}$. We show that this actually holds for all ...

Suppose ${\mathcal{F}}$ is a finite family of graphs. We consider the following meta-problem, called $\mathcal{F}$-Immersion Deletion: given a graph $G$ and integer $k$, decide whether the deletion of at most $k$ edges of $G$ can result in a graph that ...

Clustering is one of the fundamental tasks in data analytics and machine learning. In many situations, different clusterings of the same data set become relevant. For example, different algorithms for the same clustering task may return dramatically ...

BCH codes are among the best practical cyclic codes widely used in consumer electronics, communication systems, and storage devices. However, not much is known about BCH codes with large minimum distance. In this paper, we consider narrow-sense BCH codes of ...

We introduce a class of posets, which includes both ribbon posets (skew shapes) and $d$-complete posets, such that their number of linear extensions is given by a determinant of a matrix whose entries are products of hook lengths. We also give $q$-...

For $d\in\{5,6\}$, we classify arrangements of $d + 2$ points in ${RP}^{d-1}$ for which the minimum distance is as large as possible. To do so, we leverage ideas from matrix and convex analysis to determine the best possible codes that contain equiangular ...

Let $\vec{T}_k$ be the transitive tournament on $k$ vertices. We show that every oriented graph on $n=4m$ vertices with minimum total degree $(11/12+o(1))n$ can be partitioned into vertex disjoint $\vec{T}_4$'s, and this bound is asymptotically tight. We ...

Given a large graph $H$, does the binomial random graph $G(n,p)$ contain a copy of $H$ as an induced subgraph with high probability? This classical question has been studied extensively for various graphs $H$, going back to the study of the independence ...

A graph $G$ is Ramsey for a graph $H$ if every 2-coloring of the edges of $G$ contains a monochromatic copy of $H$. We consider the following question: if $H$ has bounded treewidth, is there a “sparse” graph $G$ that is Ramsey for $H$? Two notions of ...

We disprove a conjecture of Nagy on the maximum number of copies $N$($G$, $H$) of a fixed graph $G$ in a large graph $H$ with prescribed edge density. Nagy conjectured that for all $G$, the quantity $N$($G$, $H$) is asymptotically maximized by either a ...

We present two short proofs giving the best known asymptotic lower bound for the maximum element in a set of $n$ positive integers with distinct subset sums.

We interpret realizations of a graph on the sphere up to rotations as elements of a moduli space of curves of genus zero. We focus on those graphs that admit an assignment of edge lengths on the sphere resulting in a flexible object. Our interpretation of ...

We unify two popular graph classes, strongly chordal graphs and chordal bigraphs, by introducing an umbrella class that contains both classes and maintains their essential properties. This is done by allowing loops at vertices. Considering loops often has ...

This paper studies the fundamental relations among integer flows, modulo orientations, integer-valued and real-valued circular flows, and monotonicity of flows in signed graphs. A (signed) graph is modulo-$(2p+1)$-orientable if it has an orientation ...

We prove that every graph $G$ contains either $k$ edge-disjoint $K_4$-subdivisions or a set $X$ of at most $\ensuremath{O}(k^8 \log k)$ edges such that $G-X$ does not contain any $K_4$-subdivision. This shows that $K_4$-subdivisions have the edge-Erdös--...

For a given graph $H$, a graph $G$ is H-linked if, for every injection $\varphi: V(H) \to V(G)$, the graph $G$ contains a subdivision of $H$ with $\varphi(v)$ corresponding to $v$ for each $v\in V(H)$. Let $f(H)$ be the minimum integer $k$ such that every $...

We prove that for every nowhere dense class of graphs $\mathcal{C}$, positive integer $d$, and $\varepsilon>0$, the following holds: in every $n$-vertex graph $G$ from $\mathcal{C}$ one can find two disjoint vertex subsets $A,B\subseteq V(G)$ such that $|A|\...

We consider multiparty information-theoretic private protocols, and specifically their randomness complexity. The randomness complexity of private protocols is of interest both because random bits are considered a scarce resource and because of the ...

M. A. Henning and A. Yeo conjectured in [SIAM J. Discrete Math., 26 (2012), pp. 687--694] that a bipartite digraph of minimum out-degree at least 3 contains two vertex disjoint directed cycles of different lengths. In this paper, we disprove this ...

Algorithmic decidability is established for two order-theoretic properties of downward closed subsets defined by finitely many obstructions in two infinite posets. The properties under consideration are (a) being atomic, i.e., not being decomposable as a ...

An $m$-general set in $AG(n,q)$ is a set of points such that any subset of size $m$ is in general position. A 3-general set is often called a capset. In this paper, we study the maximum size of an $m$-general set in $AG(n,q)$, significantly improving ...

Let $B_n^{(k)}$ be the book graph which consists of $n$ copies of $K_{k+1}$ all sharing a common $K_k$, and let $C_m$ be a cycle of length $m$. In this paper, we first determine the exact value of $r(B_n^{(2)}, C_m)$ for $\frac{8}{9}n+112\le m\le \lceil\...

We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parameterization. ...

Golovach, Paulusma, and Song [Inform. and Comput., 237 (2014), pp. 204--214] asked to determine the parameterized complexity of the following problems parameterized by $k$: 1. Given a graph $G$, a clique modulator $D$ (a clique modulator is a set of vertices,...