John Goldwasser
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
Research Interests
John Goldwasser has a total of 21 co-authors. Here are the top co-authors by number of shared publications:
- John Talbot
University College London
5 shared publications - Michael E. Young
Department of Psychological Sciences, Kansas State University, Manhattan, USA
5 shared publications - David Offner
Carnegie Mellon University
4 shared publications - Ryan Martin
Department of Statistics, North Carolina State University, Raleigh, USA
4 shared publications - Maria Axenovich
Karlsruhe Institute of Technology, Karlsruhe, Germany
3 shared publications Bernard Lidický
Iowa State University Ames IA USA
2 shared publications
Latest Publications
- 6 January 2025
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 41 (1) , 1-21
$12\cdots t$-Permutation Avoiding (0, 1)-Matrices- 6 January 2025
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 41 (1) , 1-21
$12\cdots t$-Permutation Avoiding (0, 1)-Matrices- Open Access
On hypercube statistics
Let $d \geq 1$ and $s \leq 2^d$ be nonnegative integers. For a subset $A$ of vertices of the hypercube $Q_n$ and $n\geq d$, let $λ(n,d,s,A)$ denote the fraction of subcubes $Q_d$ of $Q_n$ that contain exactly $s$ vertices of $A$. Let $λ(n,d,s)$ denote the maximum possible value of $λ(n,d,s,A)$ as $A$ ranges over all subsets of vertices of $Q_n$, and let $λ(d,s)$ denote the limit of this quantity as $n$ tends to infinity. We prove several lower and upper bounds on $λ(d,s)$, showing that for all admissible values of $d$ and $s$ it is larger than $0.28$. We also show that the values of $s=s(d)$ such that $λ(d,s)=1$ are exactly $\{0,2^{d-1},2^d\}$. In addition we prove that if $0<s< d/8$, then $λ(d, s) \leq 1 - Ω(1/s)$, and that if $s$ is divisible by a power of $2$ which is $Ω(s)$ then $λ(d,s) \geq 1-O(1/s)$. We suspect that $λ(d,1)=(1+o(1))/e$ where the $o(1)$-term tends to $0$ as $d$ tends to infinity, but this remains open, as does the problem of obtaining tight bounds for essentially all other quantities $λ(d,s)$.Open AccessOn hypercube statistics
Let $d \geq 1$ and $s \leq 2^d$ be nonnegative integers. For a subset $A$ of vertices of the hypercube $Q_n$ and $n\geq d$, let $λ(n,d,s,A)$ denote the fraction of subcubes $Q_d$ of $Q_n$ that contain exactly $s$ vertices of $A$. Let $λ(n,d,s)$ denote the maximum possible value of $λ(n,d,s,A)$ as $A$ ranges over all subsets of vertices of $Q_n$, and let $λ(d,s)$ denote the limit of this quantity as $n$ tends to infinity. We prove several lower and upper bounds on $λ(d,s)$, showing that for all admissible values of $d$ and $s$ it is larger than $0.28$. We also show that the values of $s=s(d)$ such that $λ(d,s)=1$ are exactly $\{0,2^{d-1},2^d\}$. In addition we prove that if $0<s< d/8$, then $λ(d, s) \leq 1 - Ω(1/s)$, and that if $s$ is divisible by a power of $2$ which is $Ω(s)$ then $λ(d,s) \geq 1-O(1/s)$. We suspect that $λ(d,1)=(1+o(1))/e$ where the $o(1)$-term tends to $0$ as $d$ tends to infinity, but this remains open, as does the problem of obtaining tight bounds for essentially all other quantities $λ(d,s)$. - 31 March 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 345 (8) , 112896
Polychromatic colorings of 1-regular and 2-regular subgraphs of complete graphs
- 31 March 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 345 (8) , 112896
Polychromatic colorings of 1-regular and 2-regular subgraphs of complete graphs
- Open Access
- 14 March 2022
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 38 (3) , 1-12
The Polychromatic Number of Small Subsets of the Integers Modulo n
- 14 March 2022
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 38 (3) , 1-12
Open AccessThe Polychromatic Number of Small Subsets of the Integers Modulo n
- Open Access
- 19 August 2021
- Published by Elsevier in Discrete Mathematics
- Vol. 344 (11) , 112585
Maximum density of vertex-induced perfect cycles and paths in the hypercube
- 19 August 2021
- Published by Elsevier in Discrete Mathematics
- Vol. 344 (11) , 112585
Open AccessMaximum density of vertex-induced perfect cycles and paths in the hypercube
- 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$. - Open Access
Polychromatic Colorings on the Hypercube
Given a subgraph G of the hypercube Q_n, a coloring of the edges of Q_n such that every embedding of G contains an edge of every color is called a G-polychromatic coloring. The maximum number of colors with which it is possible to G-polychromatically color the edges of any hypercube is called the polychromatic number of G. To determine polychromatic numbers, it is only necessary to consider a structured class of colorings, which we call simple. The main tool for finding upper bounds on polychromatic numbers is to translate the question of polychromatically coloring the hypercube so every embedding of a graph G contains every color into a question of coloring the 2-dimensional grid so that every so-called shape sequence corresponding to G contains every color. After surveying the tools for finding polychromatic numbers, we apply these techniques to find polychromatic numbers of a class of graphs called punctured hypercubes. We also consider the problem of finding polychromatic numbers in the setting where larger subcubes of the hypercube are colored. We exhibit two new constructions which show that this problem is not a straightforward generalization of the edge coloring problem.
Open AccessPolychromatic Colorings on the Hypercube
Given a subgraph G of the hypercube Q_n, a coloring of the edges of Q_n such that every embedding of G contains an edge of every color is called a G-polychromatic coloring. The maximum number of colors with which it is possible to G-polychromatically color the edges of any hypercube is called the polychromatic number of G. To determine polychromatic numbers, it is only necessary to consider a structured class of colorings, which we call simple. The main tool for finding upper bounds on polychromatic numbers is to translate the question of polychromatically coloring the hypercube so every embedding of a graph G contains every color into a question of coloring the 2-dimensional grid so that every so-called shape sequence corresponding to G contains every color. After surveying the tools for finding polychromatic numbers, we apply these techniques to find polychromatic numbers of a class of graphs called punctured hypercubes. We also consider the problem of finding polychromatic numbers in the setting where larger subcubes of the hypercube are colored. We exhibit two new constructions which show that this problem is not a straightforward generalization of the edge coloring problem.
- 1 January 2018
- Published by International Press of Boston in Journal of Combinatorics
- Vol. 9 (4) , 631-657
Polychromatic colorings on the hypercube
- 1 January 2018
- Published by International Press of Boston in Journal of Combinatorics
- Vol. 9 (4) , 631-657
Polychromatic colorings on the hypercube
- Open Access
Polychromatic colorings of complete graphs with respect to 1-,2-factors and Hamiltonian cycles
If G is a graph and H is a set of subgraphs of G, then an edge-coloring of G is called H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polychromatic number of G, denoted poly_H(G), is the largest number of colors in an H-polychromatic coloring. In this paper, poly_H(G) is determined exactly when G is a complete graph and H is the family of all 1-factors. In addition poly_H(G) is found up to an additive constant term when G is a complete graph and H is the family of all 2-factors, or the family of all Hamiltonian cycles.
Open AccessPolychromatic colorings of complete graphs with respect to 1-,2-factors and Hamiltonian cycles
If G is a graph and H is a set of subgraphs of G, then an edge-coloring of G is called H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polychromatic number of G, denoted poly_H(G), is the largest number of colors in an H-polychromatic coloring. In this paper, poly_H(G) is determined exactly when G is a complete graph and H is the family of all 1-factors. In addition poly_H(G) is found up to an additive constant term when G is a complete graph and H is the family of all 2-factors, or the family of all Hamiltonian cycles.
- Open Access
Vertex Ramsey problems in the hypercube
If we 2-color the vertices of a large hypercube what monochromatic substructures are we guaranteed to find? Call a set S of vertices from Q_d, the d-dimensional hypercube, Ramsey if any 2-coloring of the vertices of Q_n, for n sufficiently large, contains a monochromatic copy of S. Ramsey's theorem tells us that for any r \geq 1 every 2-coloring of a sufficiently large r-uniform hypergraph will contain a large monochromatic clique (a complete subhypergraph): hence any set of vertices from Q_d that all have the same weight is Ramsey. A natural question to ask is: which sets S corresponding to unions of cliques of different weights from Q_d are Ramsey? The answer to this question depends on the number of cliques involved. In particular we determine which unions of 2 or 3 cliques are Ramsey and then show, using a probabilistic argument, that any non-trivial union of 39 or more cliques of different weights cannot be Ramsey. A key tool is a lemma which reduces questions concerning monochromatic configurations in the hypercube to questions about monochromatic translates of sets of integers.
Open AccessVertex Ramsey problems in the hypercube
If we 2-color the vertices of a large hypercube what monochromatic substructures are we guaranteed to find? Call a set S of vertices from Q_d, the d-dimensional hypercube, Ramsey if any 2-coloring of the vertices of Q_n, for n sufficiently large, contains a monochromatic copy of S. Ramsey's theorem tells us that for any r \geq 1 every 2-coloring of a sufficiently large r-uniform hypergraph will contain a large monochromatic clique (a complete subhypergraph): hence any set of vertices from Q_d that all have the same weight is Ramsey. A natural question to ask is: which sets S corresponding to unions of cliques of different weights from Q_d are Ramsey? The answer to this question depends on the number of cliques involved. In particular we determine which unions of 2 or 3 cliques are Ramsey and then show, using a probabilistic argument, that any non-trivial union of 39 or more cliques of different weights cannot be Ramsey. A key tool is a lemma which reduces questions concerning monochromatic configurations in the hypercube to questions about monochromatic translates of sets of integers.