Source author record

Michael Dairyko

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.NT quant-ph

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2019arXiv

Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets

Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph~ $G$ begin in one of two states, "dormant" or "active". Given a fixed integer $r$ , a dormant vertex becomes active if at any stage it has at least $r$ active neighbors, and it remains active for the duration of the process. Given an initial set of active vertices $A$ , we say that $G$ $r$ -percolates (from $A$ ) if every vertex in $G$ becomes active after some number of steps. Let $m(G,r)$ denote the minimum size of a set $A$ such that $G$ $r$ -percolates from $A$ . Bootstrap percolation has been studied in a number of settings, and has applications to both statistical physics and discrete epidemiology. Here, we are concerned with degree-based density conditions that ensure $m(G,2)=2$ . In particular, we give an Ore-type degree sum result that states that if a graph $G$ satisfies $σ_2(G)\ge n-2$ , then either $m(G,2)=2$ or $G$ is in one of a small number of classes of exceptional graphs. We also give a Chvátal-type degree condition: If $G$ is a graph with degree sequence $d_1\le d_2\le\dots\le d_n$ such that $d_i \geq i+1$ or $d_{n-i} \geq n-i-1$ for all $1 \leq i < \frac{n}{2}$ , then $m(G,2)=2$ or $G$ falls into one of several specific exceptional classes of graphs. Both of these results are inspired by, and extend, an Ore-type result in [D. Freund, M. Poloczek, and D. Reichman, Contagious sets in dense graphs, to appear in European J. Combin.]

preprint2016arXiv

Note on von Neumann and Rényi entropies of a Graph

We conjecture that all connected graphs of order $n$ have von Neumann entropy at least as great as the star $K_{1,n-1}$ and prove this for almost all graphs of order $n$ . We show that connected graphs of order $n$ have Rényi 2-entropy at least as great as $K_{1,n-1}$ and for $α>1$ , $K_n$ maximizes Rényi $α$ -entropy over graphs of order $n$ . We show that adding an edge to a graph can lower its von Neumann entropy.

preprint2014arXiv

Parking functions, Shi arrangements, and mixed graphs

The \emph{Shi arrangement} is the set of all hyperplanes in $\mathbb R^n$ of the form $x_j - x_k = 0$ or $1$ for $1 \le j < k \le n$ . Shi observed in 1986 that the number of regions (i.e., connected components of the complement) of this arrangement is $(n+1)^{n-1}$ . An unrelated combinatorial concept is that of a \emph{parking function}, i.e., a sequence $(x_1, x_2, ..., x_n)$ of positive integers that, when rearranged from smallest to largest, satisfies $x_k \le k$ . (There is an illustrative reason for the term \emph{parking function}.) It turns out that the number of parking functions of length $n$ also equals $(n+1)^{n-1}$ , a result due to Konheim and Weiss from 1966. A natural problem consists of finding a bijection between the $n$ -dimensional Shi arragnement and the parking functions of length $n$ . Stanley and Pak (1996) and Athanasiadis and Linusson 1999) gave such (quite different) bijections. We will shed new light on the former bijection by taking a scenic route through certain mixed graphs.

preprint2013arXiv

Four quotient set gems

Our aim in this note is to present four remarkable facts about quotient sets. These observations seem to have been overlooked by the Monthly, despite its intense coverage of quotient sets over the years.

preprint2012arXiv

Non-Contiguous Pattern Avoidance in Binary Trees

In this paper we consider the enumeration of binary trees avoiding non-contiguous binary tree patterns. We begin by computing closed formulas for the number of trees avoiding a single binary tree pattern with 4 or fewer leaves and compare these results to analogous work for contiguous tree patterns. Next, we give an explicit generating function that counts binary trees avoiding a single non-contiguous tree pattern according to number of leaves. In addition, we enumerate binary trees that simultaneously avoid more than one tree pattern. Finally, we explore connections between pattern-avoiding trees and pattern-avoiding permutations.

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.