Source author record

Jacob W. Cooper

Jacob W. Cooper appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms math.OC

Catalog footprint

What is connected

4works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming

A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with dual tree-depth d and largest entry D are solvable in time g(d,D)poly(n) for some function g. However, the dual tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth, and thus does not reflect its geometric structure. We prove that the minimum dual tree-depth of a row-equivalent matrix is equal to the branch-depth of the matroid defined by the columns of the matrix. We design a fixed parameter algorithm for computing branch-depth of matroids represented over a finite field and a fixed parameter algorithm for computing a row-equivalent matrix with minimum dual tree-depth. Finally, we use these results to obtain an algorithm for integer programming running in time g(d*,D)poly(n) where d* is the branch-depth of the constraint matrix; the branch-depth cannot be replaced by the more permissive notion of branch-width.

preprint2022arXiv

Uniform Turán density of cycles

In the early 1980s, Erdős and Sós initiated the study of the classical Turán problem with a uniformity condition: the uniform Turán density of a hypergraph $H$ is the infimum over all $d$ for which any sufficiently large hypergraph with the property that all its linear-size subhyperghraphs have density at least $d$ contains $H$. In particular, they raise the questions of determining the uniform Turán densities of $K_4^{(3)-}$ and $K_4^{(3)}$. The former question was solved only recently in [Israel J. Math. 211 (2016), 349-366] and [J. Eur. Math. Soc. 20 (2018), 1139-1159], while the latter still remains open for almost 40 years. In addition to $K_4^{(3)-}$, the only $3$-uniform hypergraphs whose uniform Turán density is known are those with zero uniform Turán density classified by Reiher, Rödl and Schacht [J. London Math. Soc. 97 (2018), 77-97] and a specific family with uniform Turán density equal to $1/27$. We develop new tools for embedding hypergraphs in host hypergraphs with positive uniform density and apply them to completely determine the uniform Turán density of a fundamental family of $3$-uniform hypergraphs, namely tight cycles $C_\ell^{(3)}$. The uniform Turán density of $C_\ell^{(3)}$, $\ell\ge 5$, is equal to $4/27$ if $\ell$ is not divisible by three, and is equal to zero otherwise. The case $\ell=5$ resolves a problem suggested by Reiher.

preprint2020arXiv

Hadwiger meets Cayley

We show that every connected $k$-chromatic graph contains at least $k^{k-2}$ spanning trees.

preprint2016arXiv

Weak regularity and finitely forcible graph limits

Graphons are analytic objects representing limits of convergent sequences of graphs. Lovász and Szegedy conjectured that every finitely forcible graphon, i.e. any graphon determined by finitely many graph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak $\varepsilon$-regular partition with the number of parts bounded by a polynomial in $\varepsilon^{-1}$. We construct a finitely forcible graphon $W$ such that the number of parts in any weak $\varepsilon$-regular partition of $W$ is at least exponential in $\varepsilon^{-2}/2^{5\log^*\varepsilon^{-2}}$. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.