DODavid Offner

David Offner

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


David Offner has a total of 32 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Cycle Decompositions of Cartesian Products of Two Cycles

    by Moriah Aberle, Sarah Gold, Rivkah Moshe, David Offner

    We say a graph H decomposes a graph G if there exists a partition of the edges of G into subgraphs isomorphic to H. We seek to characterize necessary and sufficient conditions for a cycle of length k, denoted $$C_k$$ , to decompose the Cartesian product of two cycles $$C_m ~\square ~ C_n$$ . We prove that if m is a multiple of 3, then the Cartesian product of a cycle $$C_m$$ and any other cycle can be decomposed into 3 cycles of equal length. This extends work of Kotzig, who proved in 1973 that the Cartesian product of two cycles can always be decomposed into two cycles of equal length. We also show that if k, m, and n are positive, and k divides 4mn, then $$C_{4k}$$ decomposes $$C_{4m} ~\square ~ C_{4n}$$ .

  • Open Access

    Minimum packing density for sets of four integers

    by Cindy Li, David Offner, Iris Ye

    We prove that the set $\{0, 1, 4, 6\}$ achieves the minimum packing density among all sets of integers with cardinality four, with a density of $\frac{1}{7}$.

  • Open Access

    Cycle decompositions of cartesian products of two cycles

    by Moriah Aberle, Sarah Gold, Rivkah Moshe, David Offner

    We say a graph $H$ decomposes a graph $G$ if there exists a partition of the edges of $G$ into subgraphs isomorphic to $H$. We seek to characterize necessary and sufficient conditions for a cycle of length $k$, denoted $C_k$, to decompose the Cartesian product of two cycles $C_m ~\square~ C_n$. We prove that if $m$ is a multiple of 3, then the Cartesian product of a cycle $C_m$ and any other cycle can be decomposed into 3 cycles of equal length. This extends work of Kotzig, who proved in 1973 that the Cartesian product of two cycles can always be decomposed into two cycles of equal length. We also show that if $k$, $m$, and $n$ are positive, and $k$ divides $4mn$ then $C_{4k}$ decomposes $C_{4m} ~\square~ C_{4n}$.

  • Open Access

    A linear optimization approach to decision support with CANS data

    by David Offner, Dan Warner, Cara Yi, Wani Zhang

    This research is meant to make a contribution to the field of Communimetric (CMX) algorithms (Lyons, 2004, 2009). This is the science underscoring the behavioral health and child welfare assessment tools such as the Child and Adolescent Needs and Strengths (CANS) assessment, the Adult Needs and Strengths Assessment (ANSA), and the Family Advocacy and Support Tool (FAST), amongst others (https://praedfoundation.org/). These tools are used throughout the US child serving and adult mental health system not only to assure a standardized assessment process, but also to provide real-time Decision Support (DS) to assessors about client treatment planning and disposition. We propose a novel method for developing CMX DS utilizing linear optimization (commonly known also as linear programming (LP) or (mixed) integer linear programming (ILP or MILP)). Using administrative data from Pennsylvania’s Child Medicaid Behavioral Health system, a MILP model is developed to differentiate profiles that benefit from one of two programs in the Pennsylvania child system of care. The programs picked are both for children at risk of out of home placement, but their clinical models are different. There is often debate in the field as to which program is most appropriate for a given family, and thus the MILP model is meant to help facilitate this decision making. We propose both a method for developing a MILP model in Medicaid behavioral health, as well as a method for testing and validating the model. We then propose a method for identifying the impact on care that utilization of the model could have in facilitating improved care matching in a system. We close with a discussion of how this information could also be used for system planning, and program development issues.

  • Open Access

    Generalized Turán densities in the hypercube

    by Maria Axenovich, Laurin Benz, David Offner, Casey Tompkins

    A classical extremal, or Tur\'an-type problem asks to determine ${\rm ex}(G, H)$, the largest number of edges in a subgraph of a graph $G$ which does not contain a subgraph isomorphic to $H$. Alon and Shikhelman introduced the so-called generalized extremal number ${\rm ex}(G,T,H)$, defined to be the maximum number of subgraphs isomorphic to $T$ in a subgraph of $G$ that contains no subgraphs isomorphic to $H$. In this paper we investigate the case when $G = Q_n$, the hypercube of dimension $n$, and $T$ and $H$ are smaller hypercubes or cycles.

  • Open Access

    Long path and cycle decompositions of even hypercubes

    by Maria Axenovich, David Offner, Casey Tompkins

    We consider edge decompositions of the $n$-dimensional hypercube $Q_n$ into isomorphic copies of a given graph $H$. While a number of results are known about decomposing $Q_n$ into graphs from various classes, the simplest cases of paths and cycles of a given length are far from being understood. A conjecture of Erde asserts that if $n$ is even, $\ell < 2^n$ and $\ell$ divides the number of edges of $Q_n$, then the path of length $\ell$ decomposes $Q_n$. Tapadia et al.\ proved that any path of length $2^mn$, where $2^m<n$, satisfying these conditions decomposes $Q_n$. Here, we make progress toward resolving Erde's conjecture by showing that cycles of certain lengths up to $2^{n+1}/n$ decompose $Q_n$. As a consequence, we show that $Q_n$ can be decomposed into copies of any path of length at most $2^{n}/n$ dividing the number of edges of $Q_n$, thereby settling Erde's conjecture up to a linear factor.

  • Open Access

    Capture-time Extremal Cop-Win Graphs

    by David Offner, Kerry Ojakian

    We investigate extremal graphs related to the game of Cops and Robbers. We focus on graphs where a single cop can catch the robber; such graphs are called cop-win. The capture time of a cop-win graph is the minimum number of moves the cop needs to capture the robber. We consider graphs that are extremal with respect to capture time, i.e. their capture time is as large as possible given their order. We give a new characterization of the set of extremal graphs. For our alternative approach we assign a rank to each vertex of a graph, and then study which configurations of ranks are possible. We partially determine which configurations are possible, enough to prove some further extremal results. We leave a full classification as an open question.

  • Open Access

    An analysis of a fair division protocol for drawing legislative districts

    by Jessica De Silva, Brady Gales, Bryson Kagy, David Offner

    Landau, Reid, and Yershov [A Fair Division Solution to the Problem of Redistricting, \textit{Social Choice and Welfare}, 2008] propose a protocol for drawing legislative districts based on a two player fair division process, where each player is entitled to draw the districts for a portion of the state. We call this the \textit{LRY protocol}. Landau and Su [Fair Division and Redistricting, arXiv:1402.0862, 2014] propose a measure of the fairness of a state's districts called the \textit{geometric target}. In this paper we prove that the number of districts a party can win under the LRY protocol can be at most two fewer than their geometric target, assuming no geometric constraints on the districts, and provide examples to prove this bound is tight. We also show that if the LRY protocol is applied on a state with geometric constraints, the result can be arbitrarily far from the geometric target.

  • Open Access

    Polychromatic Colorings on the Integers

    by Maria Axenovich, John Goldwasser, Bernard Lidický, Ryan R. Martin, David Offner, John Talbot, Michael Young

    We show that for any set $S\subseteq \mathbb{Z}$, $|S|=4$ there exists a 3-coloring of $\mathbb{Z}$ in which every translate of $S$ receives all three colors. This implies that $S$ has a codensity of at most $1/3$, proving a conjecture of Newman [D. J. Newman, Complements of finite sets of integers, Michigan Math. J. 14 (1967) 481--486]. We also consider related questions in $\mathbb{Z}^d$, $d\geq 2$.