David Offner
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
Research Subjects
David Offner has a total of 32 co-authors. Here are the top co-authors by number of shared publications:
- Ryan Martin
Department of Statistics, North Carolina State University, Raleigh, USA
5 shared publications - John Goldwasser
Department of Mathematics, West Virginia University, Morgantown, USA
4 shared publications - John Talbot
University College London
4 shared publications - Maria Axenovich
Karlsruhe Institute of Technology, Karlsruhe, Germany
4 shared publications - Michael E. Young
Department of Psychological Sciences, Kansas State University, Manhattan, USA
4 shared publications - Bernard Lidický
Department of Mathematics Iowa State University Ames Iowa USA
3 shared publications
Latest Publications
- Open Access
- 25 July 2025
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 41 (4) , 1-32
Cycle Decompositions of Cartesian Products of Two Cycles
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}$$ .- 25 July 2025
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 41 (4) , 1-32
Open AccessCycle Decompositions of Cartesian Products of Two Cycles
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
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 AccessMinimum packing density for sets of four integers
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
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 AccessCycle decompositions of cartesian products of two cycles
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
- 19 October 2023
- Published by Springer Nature in Research Square
A linear optimization approach to decision support with CANS data
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.
- 19 October 2023
- Published by Springer Nature in Research Square
Open AccessA linear optimization approach to decision support with CANS data
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
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 AccessGeneralized Turán densities in the hypercube
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
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 AccessLong path and cycle decompositions of even hypercubes
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. - 8 August 2019
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 271, 144-151
Comparing the power of cops to zombies in pursuit-evasion games
- 8 August 2019
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 271, 144-151
Comparing the power of cops to zombies in pursuit-evasion games
- Open Access
Capture-time Extremal Cop-Win Graphs
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 AccessCapture-time Extremal Cop-Win Graphs
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
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 AccessAn analysis of a fair division protocol for drawing legislative districts
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
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$.Open AccessPolychromatic Colorings on the Integers
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$.