# The complexity of multilayer $d$-dimensional circuits

Sitdikov Timur Rashidovich111Google LLC, London, UK
Kalachev Gleb Vyacheslavovich222Lomonosov Moscow State University, Moscow,
Russia

###### Abstract

In this paper we research a model of multilayer circuits with a single logical
layer. We consider $\lambda$-separable graphs as a support for circuits. We
establish the Shannon function lower bound
$\max\left(\frac{2^{n}}{n},\frac{2^{n}(1-\lambda)}{\log k}\right)$ for this
type of circuits where $k$ is the number of layers. For $d$-dimensional
graphs, which are $\lambda$-separable for $\lambda=\frac{d-1}{d}$, this gives
the Shannon function lower bound $\frac{2^{n}}{\min(n,d\log k)}$. For
multidimensional rectangular circuits the proved lower bound asymptotically
matches to the upper bound.

###### Contents

  1. 1 Introduction
  2. 2 Key definitions and results
    1. 2.1 Multilayer circuits
    2. 2.2 Supports
      1. 2.2.1 Classes of graphs $\mathcal{G}(q,\theta)$ and $\mathcal{G}(\lambda,q,\theta)$
      2. 2.2.2 $d$-dimensional graphs
    3. 2.3 Other designations and agreements
    4. 2.4 Results
    5. 2.5 The structure of the paper
  3. 3 Graph separators and their properties
    1. 3.1 Definitions and the simplest properties of separators
    2. 3.2 Partitioning of $\lambda$-separable graphs
  4. 4 Lower bound for $\lambda$-separable supports
    1. 4.1 Auxiliary lemmas
    2. 4.2 The lower bound theorem
  5. 5 Lower bound for $d$-dimensional circuits
    1. 5.1 Properties of $d$-dimensional graphs
    2. 5.2 Shannon function bounds
  6. 6 Conclusion

##  1 Introduction

The problem of designing circuits which compute Boolean functions and are
optimal or suboptimal in some sense appeared in the middle of the 20th century
due to the rapid development of computer technology. One of the most intensive
studied circuit models since the 1950s is Boolean circuits. The number of
gates (also _size_ or _complexity_) is a natural complexity measure for
Boolean circuits. One may define the complexity of a Boolean function as the
minimal size of a Boolean circuit computing the function. Muller [26] showed
that the size of every Boolean function of $n$ variables does not exceed
$O\left(\frac{2^{n}}{n}\right)$. Lupanov [14] proved that the complexity of
almost all Boolean functions over the standard basis $\\{\vee,\&,\neg\\}$ is
asymptotically equal to $\frac{2^{n}}{n}$. Also Lupanov obtained asymptotic
bound for the complexity of Boolean functions with respect to any finite
basis.

In practice when designing Boolean circuits one must take into account several
factors like placement of gates, wiring, etc. Models of Boolean circuits
considering these factors to some extent were studied in some papers appeared
since the 1960s. Korshunov [12] obtained size bounds for Boolean circuits
embedded in a 3-dimensional space with lower-bounded distances between gates,
lower-bounded distances between wires and upper-bounded lengths of wires.
Kravtsov [13] considered Boolean circuits with gates placed in cells of a
rectangular grid and proved the order of $2^{n}$ for the Shannon function.
McColl [24] obtained Shannon function lower bound $\Omega(2^{n})$ for planar
circuits.

Models of cellular circuits similar to Kravtsov’s model were considered in
several more recent papers. Albrecht [3] showed that Shannon function
asymptotics for cellular circuits has a form $c\cdot 2^{n}$, where $c$ is a
constant dependent on a basis. Gribok [4] obtained Shannon function
asymptotics to $2^{n}$ for a special basis of cellular elements. The
connection between size and other complexity measures for cellular circuits
also has been examined. Cheremisin [17] showed that it’s impossible to design
a cellular circuit of optimal size and activity simultaneously for a binary
decoder. Kalachev [7, 8, 9, 10, 11] researched simultaneous minimization of a
size, depth and activity for cellular circuits. Efimov [5, 6] examined
potential of three-dimensional cellular circuits.

VLSI circuits are one of the closest to practice circuit models. In VLSI
circuits length of wires define the signal propagation time between gates.
VLSI circuits have been considered in a number of papers and books (Thompson
[29], Ullman [30]). Kramer and van Leeuwen [22] researched simultaneous
minimization of size (area) and period.

Another direction of research is a connection between complexity measures for
different circuit models. Savage [27, 28] examined the connection between VLSI
circuits and planar circuits. Shkalikova [18] showed a relation between the
area of flat circuits and the volume of three-dimensional circuits.

The bounds of size proved for the mentioned above circuit models are above
Lupanov’s bound $\frac{2^{n}}{n}$ for Boolean circuits size. One of the
reasons for this difference is that it’s impossible to conduct arbitrary
number of wires between gates under spatial constraints. If Boolean circuits
are embedded into a graph (e.g. rectangular grid), the number of wires that
can be conducted between fragments of the graph is naturally bounded by the
size of edge separator in the graph.

In this paper we examine the relation between Shannon function and
separability properties of the graph where Boolean circuits are embedded. We
consider embeddings with constraints from [15]:

  * •

No more than one non-trivial gate of a Boolean circuit can be embedded into
any vertex of a graph.

  * •

No more than $k$ wires of a Boolean circuit can be embedded into any edge of a
graph.

The main result of this paper is the lower bound of Shannon function for
graphs with separator of size $O(p^{\lambda})$, where $p$ is the order of a
graph and $0<\lambda<1$. We call such graphs as $\lambda$-separable. We also
show that the proved lower bound is applicable to circuits embedded into a
space with $2$ or more dimensions. Given the Shannon function upper bound for
multidimensional rectangular circuits [15], we obtain the Shannon function
asymptotics for this model of circuits.

##  2 Key definitions and results

###  2.1 Multilayer circuits

The model if multilayer circuits with a single logical layer was considered in
[15]. Let’s briefly summarize key definitions.

According to [16, p. 148], a Boolean circuit in a basis $B$ is a labeled
directed acyclic graph. The labeling of vertices defines which vertices are
inputs or outputs. It also maps all non-input vertices to Boolean functions
from the basis $B$. Edges (wires) of a Boolean circuit are labeled by
integers, and for each vertex the labeling of its input edges defines the
order of arguments for the Boolean function mapped to the vertex.

A _support_ is a nonempty graph with a finite or countable number of vertices.
In general a support may contain multiple edges or self-loops.

An _embedding_ of a Boolean circuit $S$ into a support $T$ is a homomorphism
$h\colon S\to T$.

A _circuit with a support_ $T$ is a pair $(S,h)$ where $S$ is a Boolean
circuit and $h$ is an embedding of $S$ into $T$. We use the term "circuit"
instead of "circuit with a support" for brevity where it would not cause a
misreading. A circuit $(S,h)$ computes a Boolean function $f$ if a Boolean
circuit $S$ computes $f$.

In practical terms these definitions may be interpreted as follows. One of the
problems in VLSI design is an embedding of gates and wires into a plate. The
plate may be considered as a graph, i.e. as a support for Boolean circuits.

Usually there are some constraints on embeddings in circuit design problems.
In this paper we consider the following constraints.

######  Constraint 1.

Any vertex of a support may contain no more than one gate computing non-
constant Boolean function.

######  Constraint 2.

Any edge of a support may contain no more than $k$ wires of a Boolean circuit.

These constraints may be interpreted as follows. A circuit consists of $k$
"layers" where only one layer is "logical" (i.e. may contain gates computing
non-constant Boolean functions). The remaining layers are used only for
wiring. Therefore we call the circuits under constraints 1–2 as _multilayer
circuits_.

Let’s denote by $M_{k}^{T}$ the set of all $k$-layer circuits with a support
$T$.

The _complexity_ of a multilayer circuit if the number of support vertices
used in the corresponding embedding. If $M$ is a set of multilayer circuits
and $f$ is a Boolean function, one may naturally define the complexity of the
function $f$ in the set $M$ as the minimal complexity of a circuit from $M$
computing $f$. If no such a circuit exists in $M$, we may formally consider
infinity as the complexity of $f$. Let’s denote the complexity of the function
$f$ in the set $M$ as $L(M,f)$.

One may naturally define the Shannon function of the complexity of $k$-layer
circuits with the support $T$:

$L(M_{k}^{T},n)=\max_{f\in B_{n}}L(M_{k}^{T},f).$

###  2.2 Supports

The properties of a support are crucial for embeddings, as under the same
constraints different supports in general admit completely different sets of
embeddings. In this paper we consider $\lambda$-separable graphs as supports.
We also consider $d$-dimensional graphs as an important special case of
$\lambda$-separable graphs.

A class $\mathcal{G}$ of graphs is _monotone_ if every subgraph of a graph in
$\mathcal{G}$ is also in $\mathcal{G}$.

####  2.2.1 Classes of graphs $\mathcal{G}(q,\theta)$ and
$\mathcal{G}(\lambda,q,\theta)$

Let $q\in\mathbb{N}$ and $\theta>1$ be some constants. Let’s define class of
graphs $\mathcal{G}(q,\theta)$ as the set of all supports with the following
properties:

  * •

Degree of each vertex in $T$ is bounded by $q$.

  * •

For any integer $p$ the number of different non-isomorphic subgraphs of $T$
with $p$ vertices does not exceed $\theta^{p}$.

The first property (bounding for vertex degree) is a natural limitation for
circuit design problems. The second property is met for several important
categories of graphs, including planar graphs [19] and $d$-dimensional graphs
defined below.

The formal definition of $\lambda$-separability is considered in the section
3. Substantively each subgraph of a $\lambda$-separable support can be split
into smaller fragments by removing $O(p^{\lambda})$ vertices (edges), where
$p$ is the number of vertices in the subgraph and $0<\lambda<1$.

Let’s denote the subclass of $\lambda$-separable supports from
$\mathcal{G}(q,\theta)$ as $\mathcal{G}(\lambda,q,\theta)$.

####  2.2.2 $d$-dimensional graphs

Let $d\geq 2$ be an integer. A support $T$ is a _$d$ -dimensional graph_, if
there are constants $c_{v}>0,c_{e}>0$ such that $T$ can be embedded into
$d$-dimensional Euclidean space with pairwise distances between vertices no
less than $c_{v}$ and edge lengths no greater than $c_{e}$.

######  Remark 1.

The constraints in the definition above are similar to the constraints in the
definition of circuits with volumetric gates from Korshunov’s paper [12].

######  Remark 2.

We can always assume that one of the constants $c_{v}$ and $c_{e}$ is equal to
$1$. Below we assume that $c_{v}=1$.

######  Remark 3.

It’s clear that every finite support is a $d$-dimensional graph with a great
enough value of $c_{e}$. Therefore the definition of $d$-dimensional graphs is
senseless for finite supports. However one may define a _monotone class of
$d$-dimensional graphs with a parameter $c_{e}$_, where the constant $c_{e}$
is common for all graphs in the class. It’s obvious that such a class is a
monotone class of graphs. Below we omit the constant $c_{e}$ and speak about a
_$d$ -dimensional class of graphs_ in cases when the value of $c_{e}$ is not
important.

######  Example 1.

The graph of a $d$-dimensional grid is a $d$-dimensional graph. It’s
sufficient to consider $c_{e}=1$.

######  Example 2.

One can prove that the graph of an infinite binary tree is not $d$-dimensional
for any $d$. Indeed, the number of vertices at distance $p$ from the root
depends on $p$ exponentially, though the number of $d$-dimensional balls with
radii $1$ that can be placed into a ball with radii $c_{e}\cdot d$ is
$O(p^{d})$.

Embedding of Boolean circuits into $d$-dimensional grid was considered in
[15]. As in that paper, we use the term _multidimensional rectangular
circuits_ for such circuits and use the notation $M_{k}^{d}$ instead of
$M_{k}^{\mathbb{Z}^{d}}$.

In section 5 we prove that all $d$-dimensional supports belong to classes
$\mathcal{G}(\lambda,q,\theta)$ for $\lambda=\frac{d-1}{d}$ and some values of
$q$ and $\theta$.

###  2.3 Other designations and agreements

The expression $\log a$ always denotes a base two logarithm of $a$. We
formally assume that $x\log x=0$ for $x=0$.

We denote by $B_{n,m}$ the set of Boolean functions with $n$ inputs and $m$
outputs ($n\geq 0$, $m\geq 1$).

The expression $f(x)\lesssim g(x)$ corresponds to the inequality
$\varlimsup_{x\to\infty}\frac{f(x)}{g(x)}\leq 1$. Similarly we use the
expression $f(x)\gtrsim g(x)$. We may use a complex condition when passing to
a limit, e. g. $f(n,k)\lesssim g(n,k)$ as $k\to\infty$, $\log k\leq n$.

###  2.4 Results

In this paper for every support $T\in\mathcal{G}(\lambda,q,\theta)$ we prove
that

$L(M_{k}^{T},n)\gtrsim\max\left(\frac{2^{n}}{n},\frac{2^{n}(1-\lambda)}{\log
k}\right)\quad\mbox{as}\quad k\to\infty,\ n\to\infty.$

It is also proved that every $d$-dimensional support belongs to the class
$\mathcal{G}(\lambda,q,\theta)$ for $\lambda=\frac{d-1}{d}$ and some constants
$q$ and $\theta$. Therefore the following estimation holds for for
$d$-dimensional supports:

$L(M_{k}^{T},n)\gtrsim\frac{2^{n}}{\min(n,d\log k)}\quad\mbox{as}\quad
k\to\infty,\ n\to\infty.$

An upper bound of Shannon function for multidimensional rectangular circuits
matching the lower bound above was proved in [15]. Thus we have the
asymptotics of Shannon function for multidimensional rectangular circuits:

$L(M_{k}^{d},n)\sim\frac{2^{n}}{\min(n,d\log k)}\quad\mbox{as}\quad
k\to\infty,\ n\to\infty.$

###  2.5 The structure of the paper

In this paper all the proofs are divided into three sections.

Section 3 contains definitions related to graph separators. The main result of
the section is lemma 2. The point of the lemma is that $\lambda$-separable
graphs supporting "good" (in some sense) partitioning into two parts also
support "good" partitioning into many parts.

Section 4 contains the proof of the lower bound for Shannon function of the
complexity for supports from classes $\mathcal{G}(\lambda,q,\theta)$. The key
part of this section is lemma 7.

Section 5 is devoted to the proof of the lower bound for Shannon function for
$d$-dimensional supports. The section also contains the asymptotics of Shannon
function for multidimensional rectangular circuits as a corollary. Essentially
it’s proved that every $d$-dimensional support belongs to a class
$\mathcal{G}(\lambda,q,\theta)$ for $\lambda=\frac{d-1}{d}$ and some constants
$q$ and $\theta$.

##  3 Graph separators and their properties

###  3.1 Definitions and the simplest properties of separators

In this section we provide the definitions of edge and vertex separators in
graphs and prove some of the simplest properties of separators.

##### Edge separators.

We define edge separators similarly to the definitions of vertex separators
from [23].

######  Definition 1.

Let $f\colon\mathbb{N}\to\mathbb{R}$ be a function. A monotone class of graphs
$\mathcal{G}$ is _edge $f(p)$-separable_ if there exist constants
$\frac{1}{2}\leq\alpha<1$, $\beta\geq 0$, $m\geq 2$ such that any graph
$G\in\mathcal{G}$ with $p$ vertices ($p\geq m$) can be split into two
subgraphs with no more than $\alpha p$ vertices each and no more than $\beta
f(p)$ edges between the subgraphs.

######  Remark 4.

The constant $m$ is technically important, since it allows not to consider
some corner cases. For example graph $K_{1}$ cannot be split into two nonempty
subgraphs in principle, thus we may always assume that $m\geq 2$. In general
$m$ may be greater than $2$.

######  Definition 2.

Let $f\colon\mathbb{N}\to\mathbb{R}$ be a function. A support $T$ is _edge
$f(p)$-separable_ if the monotone class of all finite subgraphs of $T$ is edge
$f(p)$-separable.

The interesting case is when $f(p)$ is a slowly growing function. Essentially
this allows to use the divide-and-conquer technique for obtaining effective
algorithms and non-trivial lower bounds in proofs. In this paper we consider
the function $p^{\lambda}$ with $0<\lambda<1$ as $f(p)$. We also call edge
$p^{\lambda}$-separable supports and monotone classes of graphs as _edge
$\lambda$-separable_.

##### Vertex separators.

The following definition of a vertex separator is a modification of definition
2.1 from [25] applied to monotone classes of graphs.

######  Definition 3.

Let $f\colon\mathbb{N}\to\mathbb{R}$ be a function. A monotone class of graphs
$\mathcal{G}$ is _vertex $f(p)$-separable_ if there exist constants
$\frac{1}{2}\leq\alpha<1$, $\beta\geq 0$, $m\geq 2$ such that for any graph
$G\in\mathcal{G}$ with $p$ vertices ($p\geq m$) there exists a partition of
$V(G)$ into three parts $A$, $B$, $C$ satisfying the following conditions:

  * •

There are no edges from $A$ to $B$.

  * •

$|A|,|B|\leq\alpha p$.

  * •

$|C|\leq\beta f(p)$.

It’s obvious that for any monotone class of graphs edge $f(p)$-separability
implies vertex $f(p)$-separability, as one may consider endpoints of an edge
separator as a vertex separator. The converse is not always true. For example,
the class of stars $K_{1,p}$ and their subgraphs is vertex $1$-separable, but
is not edge $1$-separable.

The following simple lemma shows that for monotone classes of graphs with
bounded vertex degree vertex $f(p)$-separability implies edge
$f(p)$-separability.

######  Lemma 1.

Let $\mathcal{G}$ be a monotone class of vertex $f(p)$-separable graphs with
parameters $\alpha$, $\beta$, $m$ where vertex degree of any graph is bounded
by $q$. Then $\mathcal{G}$ is edge $f(p)$-separable with parameters
$\max\left(\frac{2}{3},\alpha\right)$, $q\beta$ and $\max(m,2)$.

###### Proof.

We’ll show how to obtain an edge separator from a vertex separator.

Let $G\in\mathcal{G}$, $|V(G)|=p\geq\max(m,2)$. By the definition of vertex
separability $V(G)$ can be divided into three sets $A,B,C$, where $C$ is a
separator. Here $|A|,|B|\leq\alpha p$, $|C|\leq\beta f(p)$.

Let’s move vertices from $C$ to $A$ and $B$ in a way to keep the sizes of the
resulting sets as close to each other as possible. Let’s denote the resulting
sets by $A^{\prime}$ and $B^{\prime}$. Considering the way of constructing
$A^{\prime}$ and $B^{\prime}$, we obtain
$1\leq|A^{\prime}|,|B^{\prime}|\leq\max\left(\frac{2}{3},\alpha\right)\cdot
p$.

Each edge connecting $A^{\prime}$ and $B^{\prime}$ is incident to at least one
vertex from $C$. Since vertex degree is bounded by $q$, the total number of
such edges does not exceed $q|C|\leq q\beta f(p)$.

Since values $\max\left(\frac{2}{3},\alpha\right)$, $q\beta$ and $\max(m,2)$
do not depend on a graph, edge $f(p)$-separability of $\mathcal{G}$ is proved.
∎

Thereby when we define a class $\mathcal{G}(\lambda,q,\theta)$ it does not
matter whether we use edge $\lambda$-separability or vertex
$\lambda$-separability, as all graphs from the class have vertex degree
bounded by $q$.

###  3.2 Partitioning of $\lambda$-separable graphs

Informally the key result of this section is the following statement. Since a
$\lambda$-separable graph can be split into two disconnected parts of
comparable size by removing a small number of edges, the graph can also be
split into many disconnected parts of bounded size by removing a small number
of edges.

The following lemma is the modification of lemma 1 from [20] for planar
graphs.

######  Lemma 2.

Let $\mathcal{G}$ be a monotone class of edge $\lambda$-separable graphs with
parameters $\alpha$, $\beta$ and $m$, where $0<\lambda<1$,
$\frac{1}{2}\leq\alpha<1$, $\beta\geq 0$, $m\geq 2$. Then for each $r\geq m-1$
and for each graph $G\in\mathcal{G}$ with $p$ vertices there exists partition
of $G$ into subgraphs such that

  * •

The number of vertices in each subgraph does not exceed $r$.

  * •

The total number of edges mutually connecting subgraphs does not exceed
$\frac{\delta pr^{\lambda}}{r}$, where $\delta$ is a constant common for all
graphs of the class and for all values of $r$.

We call the corresponding partition of the graph as _$r^{\lambda}$
-partition_.

###### Proof.

The proof of the lemma is similar to the proof of lemma 1 from [20]. We
provide the detailed version of the proof for completeness.

Let $r\geq m-1$, $G\in\mathcal{G}$, $|V(G)|=p$. If $p\leq r$, then the trivial
partition containing a single graph $G$ suffices.

Let $p>r$. By the definition of edge $\lambda$-separability graph $G$ can be
partitioned into two subgraphs $A$ and $B$ with no more than $\alpha p$
vertices each and no more than $\beta p^{\lambda}$ mutually connecting edges.
Since $\mathcal{G}$ is a monotone class, $A,B\in\mathcal{G}$. Thus both $A$
and $B$ can be similarly partitioned into two subgraphs. Let’s recursively
partition all the subgraphs until we have only pieces with no more than $r$
vertices.

Let’s prove that the obtained partition is a $r^{\lambda}$-partition.

The constraint on the number of vertices in subgraphs (no more than $r$
vertices per subgraph) is satisfied by the algorithm of partitioning.

Let $X$ be the total number of edges deleted during the algorithm. We prove an
upper bound for $X$. Let’s split all subgraphs partitioned at any step of the
algorithm into sets $\mathcal{G}_{i}$ depending on the size of a subgraph. We
include into $\mathcal{G}_{1}$ subgraphs with a size from a half-open interval
$(r,r\alpha^{-1}]$. Similarly we include into $\mathcal{G}_{2}$ subgraphs with
a size from a half-open interval $(r\alpha^{-1},r\alpha^{-2}]$, and so on. If
$t=\lceil\log_{\alpha}\frac{r}{p}\rceil$, the last set $\mathcal{G}_{t}$
includes subgraphs with a size from $(r\alpha^{-(t-1)},r\alpha^{-t}]$.

Let $1\leq i\leq t$. Consider the set $\mathcal{G}_{i}$. Note that vertex sets
of distinct subgraphs from $\mathcal{G}_{i}$ do not intersect, since the ratio
of sizes of such subgraphs is less than $\alpha$. Therefore the total size of
all subgraphs in $\mathcal{G}_{i}$ does not exceed $p$. Hence
$|\mathcal{G}_{i}|\leq\frac{p}{r}\cdot\alpha^{i-1}$. At the same time the
total number of edges deleted when partitioning a graph from $\mathcal{G}_{i}$
does not exceed $\beta(r/\alpha^{i})^{\lambda}$.

By summing over all subgraphs from sets $\mathcal{G}_{i}$ we obtain

$X\leq\beta\sum_{i=1}^{t}\frac{\alpha^{i-1}p}{r}\left(\frac{r}{\alpha^{i}}\right)^{\lambda}\leq\frac{\beta}{\alpha^{\lambda}(1-\alpha^{1-\lambda})}\cdot\frac{pr^{\lambda}}{r}.$

This matches the constraint on the number of edges mutually connecting
subgraphs of a $r^{\lambda}$-partition. ∎

We use the following auxiliary notation below. Let $M,S>0$. We denote by
$K(M,S)$ the number of tuples $(x_{1},\dots,x_{t})$ satisfying the condition

$1\leq x_{i}\leq M,\qquad\sum_{i=1}^{t}x_{i}\leq S.$ (1)

If $\mathcal{G}$ is a monotone $\lambda$-separable class of graphs with vertex
degree bounded by $q$, the properties of $r^{\lambda}$-partition may be stated
as follows. Let $\bar{p}=\\{p_{i}\\}_{i=1}^{t}$ be a tuple of sizes of
$r^{\lambda}$-partition subgraphs, and let $\bar{s}=\\{s_{i}\\}_{i=1}^{t}$ be
a tuple of numbers of edges connecting $r^{\lambda}$-partition subgraphs with
the rest of the graph. Then

$\bar{p}\in K(r,p),\qquad\bar{s}\in K\left(qr,\frac{\delta
pr^{\lambda}}{r}\right).$ (2)

##  4 Lower bound for $\lambda$-separable supports

In this section we prove the key result of this paper namely a theorem on the
lower bound for all supports from classes $\mathcal{G}(\lambda,q,\theta)$.

$L(M_{k}^{T},n)\gtrsim\max\left(\frac{2^{n}}{n},\frac{2^{n}(1-\lambda)}{\log
k}\right).$

Note that the lower bound depends only on the separability function.
Parameters $q$ and $\theta$ do not affect the lower bound.

Substantively the proof is obtained in the following way. We partition a
subgraph of a support into small fragments. Then we bound the number of
Boolean functions computable in the subgraph by the number of Boolean
functions computable in the fragments and the number of ways to conduct wires
between the fragments.

Since the proof is technically involved we prove several auxiliary lemmas in a
separate section 4.1. The proof of the main theorem is finished in section
4.2.

###  4.1 Auxiliary lemmas

The following lemma is an immediate corollary of a classic lemma [16].

######  Lemma 3 ([16], p. 198–200).

Let $N(n,m,L)$ be the number of Boolean functions with no more than $n$
inputs, no more than $m$ outputs and the complexity not greater than $L$. Then
there exists a constant $c$ such that

$N(n,m,L)\leq\bigl{(}c(n+L)\bigr{)}^{n+m+L}.$

We use $r^{\lambda}$-partitioning of support subgraphs to obtain the lower
bound. Technical lemma 4 bounds the number of Boolean operators computable in
fragments of a $r^{\lambda}$-partition.

Let $p$ and $s$ be positive integers. Denote by $Z(p,s)$ the number of Boolean
functions with no more than $s$ inputs and outputs in total and the complexity
not greater than $p$.

Recall the notation $K(M,S)$ introduced in section 3 for sets of tuples
satisfying conditions (1). When proving lemma 4 we use the following simple
property:

$\mbox{If}\quad\bar{x}=\\{x_{i}\\}_{i=1}^{t}\in
K(M,S),\quad\mbox{then}\quad\sum_{i=1}^{t}x_{i}\log x_{i}\leq S\log M.$ (3)

We also use the following inequality for non-negative $x$ and $y$:

$(x+y)\log(x+y)\leq x\log x+y\log y+x+y,$ (4)

which under the assumption $0\log 0=0$ is a corollary of the binary entropy
bound $-a\log a-(1-a)\log(1-a)\leq 1$ for $a=\frac{x}{x+y}$.

######  Lemma 4.

Let $q\geq 1$, $b\geq 0$, $d>0$ be constants and let $k\to\infty$ be a
parameter. Denote $r=(k\log k)^{d}$. Let $L$, $M$ be numbers and
$\bar{p}=\\{p_{i}\\}_{i=1}^{t}$, $\bar{s}=\\{s_{i}\\}_{i=1}^{t}$,
$\bar{u}=\\{u_{i}\\}_{i=1}^{t}$ be tuples satisfying the following conditions:

$\displaystyle\bar{p}\in K(r,L),\qquad\bar{s}\in K\left(qkr,\frac{bL}{\log
k}\right),\qquad u_{i}\geq 0,\qquad\sum_{i=1}^{t}u_{i}\leq M.$ (5)

Then

$\sum_{i=1}^{t}\log Z(p_{i},s_{i}+u_{i})\leq
d\Biggl{(}1+O\biggl{(}\frac{\log\log k}{\log k}\biggr{)}\Biggr{)}L\log k+M\log
M+O(M).$ (6)

###### Proof.

Using lemma 3, we have

$Z(p_{i},s_{i}+u_{i})\leq\bigl{(}c(p_{i}+s_{i}+u_{i})\bigr{)}^{p_{i}+s_{i}+u_{i}}.$

Taking the logarithm and summing by all tuple elements, we obtain

$\sum_{i=1}^{t}\log
Z(p_{i},s_{i}+u_{i})\leq\sum_{i=1}^{t}(p_{i}+s_{i}+u_{i})(\log
c+\log(p_{i}+s_{i}+u_{i})).$ (7)

Using twice (4), then (3) with (5), we bound the right side of (7):

$\displaystyle\sum_{i=1}^{t}$ $\displaystyle(p_{i}+s_{i}+u_{i})(\log
c+\log(p_{i}+s_{i}+u_{i}))\leq$ $\displaystyle\leq\sum_{i=1}^{t}(p_{i}\log
p_{i}+s_{i}\log s_{i}+u_{i}\log u_{i}+(p_{i}+s_{i}+u_{i})(\log c+2))\leq$
$\displaystyle\leq L\log r+\frac{bL}{\log k}\underbrace{\log(qkr)}_{O(\log
k)}+M\log M+\underbrace{(\log c+2)\left(L+\frac{bL}{\log
k}+M\right)}_{O(L+M)}=$ $\displaystyle=L\log r+M\log M+O(L+M).$

Substituting the bound into, (7) we obtain

$\displaystyle\sum_{i=1}^{t}\log Z(p_{i},s_{i}+u_{i})$ $\displaystyle\leq
L\log r+M\log M+O(L+M)=$ $\displaystyle=Ld(\log k+\log\log k)+M\log M+O(L+M)=$
$\displaystyle=\Biggl{(}1+O\biggl{(}\frac{\log\log k}{\log
k}\biggr{)}\Biggr{)}Ld\log k+M\log M+O(M).$

∎

The following two lemmas allow to obtain a trivial lower bound for Shannon
function for circuits with arbitrary support.

######  Lemma 5 ([16], theorem 11.5).

For each constant $\epsilon>0$ the ratio of Boolean functions of $n$ variables
satisfying the inequality

$L(f)\geq(1-\epsilon)\frac{2^{n}}{n},$

approaches $1$ as $n\to\infty$.

######  Lemma 6.

Let $T$ be an arbitrary support, $k\in\mathbb{N}$, $n\to\infty$. Then

$L(M_{k}^{T},n)\gtrsim\frac{2^{n}}{n}.$

###### Proof.

The lemma is an immediate corollary of lemma 5 and the fact that the
complexity of a multilayer circuit is not less than the size of the
corresponding Boolean circuit. ∎

###  4.2 The lower bound theorem

In this section we finish the proof of lower asymptotic bound for
$L(M_{k}^{T},n)$, where $T\in\mathcal{G}(\lambda,q,\theta)$. We also prove a
corollary allowing to obtain a lower bound for supports having separability
function of more general type, e. g. $\log p$, $\sqrt{p}\log\log p$, etc.

######  Lemma 7.

Let $T\in\mathcal{G}(\lambda,q,\theta)$. Let $N_{k}^{T}(n,m,L)$ be the number
of Boolean functions in $B_{n,m}$ computable by $k$-layer circuits in $T$ with
size not greater than $L$. Then as $k\to\infty$, the following inequality
holds:

$\displaystyle\log N_{k}^{T}(n,m,L)$ $\displaystyle\leq\frac{L\log
k}{1-\lambda}\Biggl{(}1+O\biggl{(}\frac{\log\log k}{\log
k}\biggr{)}\Biggr{)}+$ $\displaystyle+(n+m)\bigl{(}\log
L+\log(n+m)\bigr{)}+O(n+m).$

###### Proof.

Let’s denote $r=(k\log k)^{\frac{1}{1-\lambda}}$. We consider only great
enough values of $k$ to suffice the conditions on $r$ from lemma 2. Thus every
finite subgraph $G$ of the support $T$ has a $r^{\lambda}$-partition which we
denote by $P(G)$.

We can build a mapping between $k$-layer circuits of size not greater than $L$
computing a Boolean function in $B_{n,m}$ and tuples of the following objects:

  1. 1.

Subgraph $G$ of the support where we embed the corresponding Boolean circuit.

  2. 2.

A tuple $\bar{v}$ of vertices of $G$ where we embed inputs and outputs of the
Boolean circuit.

  3. 3.

A set of directed wires between fragments of $P(G)$.

  4. 4.

A tuple of Boolean functions computed in fragments of $P(G)$.

It is easy to see that circuits computing different Boolean functions are
mapped to different tuples. Thus we can bound the number of Boolean functions
by the number of possible tuples. Obviously we can bound the number of
elements per each tuple item and find the product of the bounds.

Denote the corresponding upper bounds as $A_{1},A_{2},A_{3},A_{4}$ (here the
correspondence is defined by the order of items above).

As $T\in\mathcal{G}(\lambda,q,\theta)$, we have

$A_{1}\leq\theta+\theta^{2}+\dots+\theta^{L}\leq\frac{\theta^{L+1}}{\theta-1}.$

Let’s bound $A_{2}$. Obviously there exist $L^{n+m}$ tuples of $n+m$ vertices
of $G$. Hence $A_{2}\leq L^{n+m}$.

The number of edges between the fragments of the $r^{\lambda}$-partition
$P(G)$ is bounded by $\frac{\delta Lr^{\lambda}}{r}=\frac{\delta L}{k\log k}$,
where $\delta$ is a constant. In each of these edges we can conduct no more
than $k$ wires. Thus there can be no more than $\frac{\delta L}{\log k}$ wires
mutually connecting the fragments of $P(G)$. For each of these wires there are
three options: directed in one way, directed in the opposite way and missed.
Therefore

$A_{3}\leq 3^{\frac{\delta L}{\log k}}.$

We introduce the following notation to obtain the bound for $A_{4}$. Let
$G_{i}$ be the fragments of $P(G)$, $t$ be the number of the fragments,
$p_{i}$ be the number of vertices in $i$-th fragment, $s_{i}$ be the number of
wires that can be conducted outside from $G_{i}$, $u_{i}$ be the total number
of inputs and outputs of the Boolean circuit embedded into $G_{i}$ (i. e. the
number of items in the tuple $\bar{v}$ corresponding to the vertices of
$G_{i}$). It’s clear that each Boolean function computable in $G_{i}$ must
have no more than $p_{i}$ gates and no more than $s_{i}+u_{i}$ inputs and
outputs in total. Hence the following inequality holds:

$A_{4}\leq\prod_{i=1}^{t}Z(p_{i},s_{i}+u_{i}).$

By multiplying the bounds for $A_{i}$ we obtain

$N_{k}^{T}(n,m,L)\leq\frac{\theta^{L+1}}{\theta-1}\cdot L^{n+m}\cdot
3^{\frac{\delta L}{\log k}}\cdot\prod_{i=1}^{t}Z(p_{i},s_{i}+u_{i}).$

Taking the logarithm and omitting the negative addend be obtain

$\displaystyle\log N_{k}^{T}(n,m,L)$
$\displaystyle\leq\underbrace{(L+1)\log\theta}_{O(L)}+(n+m)\log L+$
$\displaystyle+\underbrace{\frac{\delta L}{\log k}\log
3}_{o(L)}+\sum_{i=1}^{t}\log Z(p_{i},s_{i}+u_{i}).$ (8)

Let’s bound the sum $\sum_{i=1}^{t}\log Z(p_{i},s_{i}+u_{i})$ in the right
side of (4.2). We claim that we can apply lemma 4.

We obtain the following conditions for tuples $\bar{p}=\\{p_{i}\\}_{i=1}^{t}$,
$\bar{s}=\\{s_{i}\\}_{i=1}^{t}$ by using (2): $\bar{p}\in K(r,L)$, $\bar{s}\in
K\left(qkr,\frac{\delta L}{\log k}\right)$. For tuple
$\bar{u}=\\{u_{i}\\}_{i=1}^{t}$ it’s obvious that $u_{i}\geq 0$,
$\sum_{i=1}^{t}u_{i}\leq n+m$. Finally we have $q\geq 1$, $\delta\geq 0$,
$\frac{1}{1-\lambda}>0$, $k\to\infty$ and $r=(k\log k)^{\frac{1}{1-\lambda}}$.
Thus all conditions of lemma 4 are satisfied. Hence

$\displaystyle\sum_{i=1}^{t}\log Z(p_{i},s_{i}+u_{i})$
$\displaystyle\leq\frac{L\log k}{1-\lambda}\Biggl{(}1+O\biggl{(}\frac{\log\log
k}{\log k}\biggr{)}\Biggr{)}+$ $\displaystyle+(n+m)\log(n+m)+O(n+m).$

Combining the bounds for addends in the right side of (4.2), we obtain

$\displaystyle\log N_{k}^{T}(n,m,L)$ $\displaystyle\leq\frac{L\log
k}{1-\lambda}\Biggl{(}1+O\biggl{(}\frac{\log\log k}{\log
k}\biggr{)}\Biggr{)}+$ $\displaystyle+(n+m)\bigl{(}\log
L+\log(n+m)\bigr{)}+O(n+m).$

∎

In this paper we are interested in the case when $n+m$ is small compared to
$L$. In this case we can simplify the inequality in lemma 7.

######  Corollary 1.

Under the conditions of lemma 7, if $k\to\infty$ and $n+m\leq L/\log L$, then

$\log N_{k}^{T}(n,m,L)\leq\frac{L\log
k}{1-\lambda}\Biggl{(}1+O\biggl{(}\frac{\log\log k}{\log
k}\biggr{)}\Biggr{)}.$

######  Lemma 8.

Let $T\in\mathcal{G}(\lambda,q,\theta)$, $k\to\infty$, $n\to\infty$. Then

$L(M_{k}^{T},n)\geq\frac{2^{n}(1-\lambda)}{\log
k}\Biggl{(}1+O\biggl{(}\frac{\log\log k}{\log k}\biggr{)}\Biggr{)}.$

###### Proof.

It follows from lemma 6 that for great enough values of $n$ and any $k$ the
inequality below holds:

$L(M_{k}^{T},n)\geq\frac{1}{2}\cdot\frac{2^{n}}{n}.$ (9)

Let $k\to\infty$, $n\to\infty$. We denote $L=L(M_{k}^{T},n)$ for brevity.
Using the term $N_{k}^{T}(n,m,L)$ defined in lemma 7, we obtain the identity

$N_{k}^{T}(n,1,L)=2^{2^{n}}.$

It follows from (9) that $n=O(\log L)=o(L/\log L)$. By applying corollary 1 of
lemma 7 we obtain

$2^{n}\leq\frac{L\log k}{1-\lambda}\Biggl{(}1+O\biggl{(}\frac{\log\log k}{\log
k}\biggr{)}\Biggr{)}.$

This implies to the claim of the lemma. ∎

######  Theorem 1.

Let $0<\lambda<1$, $T\in\mathcal{G}(\lambda,q,\theta)$. Then

$L(M_{k}^{T},n)\gtrsim\max\left(\frac{2^{n}}{n},\frac{2^{n}(1-\lambda)}{\log
k}\right)\quad\mbox{as}\quad k\to\infty,\ n\to\infty.$

###### Proof.

It follows from lemmas 6 and 8. ∎

Hereby we obtained the lower bound for $\lambda$-separable supports, i. e. for
supports with separability function like $p^{\lambda}$. Using theorem 1 one
can obtain lower bound for supports with separability function like $\log p$,
$\sqrt{p}\log\log p$, etc.

######  Corollary 2.

Let $0\leq\lambda_{0}<1$, $f(p)=O(p^{\lambda})$ for all $\lambda>\lambda_{0}$.
Let $T\in\mathcal{G}(q,\theta)$ be a $f(p)$-separable support. Then

$L(M_{k}^{T},n)\gtrsim\max\left(\frac{2^{n}}{n},\frac{2^{n}(1-\lambda_{0})}{\log
k}\right)\quad\mbox{as}\quad k\to\infty,\ n\to\infty.$ (10)

###### Proof.

Let $\lambda>\lambda_{0}$. It’s clear that $T$ is $p^{\lambda}$-separable. By
theorem 1,
$L(M_{k}^{T},n)\gtrsim\max\left(\frac{2^{n}}{n},\frac{2^{n}(1-\lambda)}{\log
k}\right)$ as $k\to\infty$, $n\to\infty$.

Denote $g(\lambda,k,n)=\max\left(\frac{2^{n}}{n},\frac{2^{n}(1-\lambda)}{\log
k}\right)$. We have

$\liminf_{\begin{subarray}{c}k\to\infty\\\
n\to\infty\end{subarray}}\frac{L(M^{T}_{k},n)}{g(\lambda,k,n)}\geq
1\quad\mbox{ as }\quad\lambda_{0}<\lambda<1.$

It’s easy to see that
$\frac{g(\lambda,k,n)}{g(\lambda_{0},k,n)}\geq\frac{1-\lambda}{1-\lambda_{0}}$,
therefore

$A:=\liminf_{\begin{subarray}{c}k\to\infty\\\
n\to\infty\end{subarray}}\frac{L(M^{T}_{k},n)}{g(\lambda_{0},k,n)}\geq\liminf_{\begin{subarray}{c}k\to\infty\\\
n\to\infty\end{subarray}}\frac{1-\lambda}{1-\lambda_{0}}\cdot\frac{L(M^{T}_{k},n)}{g(\lambda,k,n)}\geq\frac{1-\lambda}{1-\lambda_{0}}$

for all $\lambda_{0}<\lambda<1$.

Hence
$A\geq\sup\limits_{1>\lambda>\lambda_{0}}\frac{1-\lambda}{1-\lambda_{0}}=1$.
The latter implies to (10). ∎

##  5 Lower bound for $d$-dimensional circuits

In this section we prove lower bound for $d$-dimensional circuits and
asymptotics for $d$-dimensional rectangular circuits. In substance the lower
bound for $d$-dimensional circuits is a corollary for the lower bound for
$\lambda$-separable supports, since we prove that all $d$-dimensional supports
belong to classes $\mathcal{G}(\lambda,q,\theta)$.

###  5.1 Properties of $d$-dimensional graphs

Indeed we have to prove that $d$-dimensional graphs have three properties:
bounded vertex degree, exponentially bounded number of non-isomorphic
subgraphs, and $\lambda$-separability.

######  Lemma 9.

Let $T$ be a $d$-dimensional support (accordingly let $\mathcal{G}$ be a class
of $d$-dimensional graphs) with a parameter $c_{e}$. Then vertex degree of $T$
(accordingly of any graph is $\mathcal{G}$) is bounded by $(2c_{e}+1)^{d}$.

###### Proof.

When placing arbitrary $d$-dimensional graph into $d$-dimensional space the
neighborhood of any vertex is placed into a ball of radii $c_{e}$. Since
$d$-dimensional balls with radii $0.5$ and centers in graph vertices do not
intersect and lie inside a ball with radii $c_{e}+0.5$, the number of such
balls cannot exceed the ratio of volumes of $d$-dimensional balls with radii
$c_{e}+0.5$ and $0.5$ respectively. This ratio is equal to $(2c_{e}+1)^{d}$. ∎

######  Lemma 10.

Let $T$ be a $d$-dimensional graph. Then the number of non-labeled subgraphs
of $T$ with $n$ vertices does not exceed $\theta^{n}$, where $\theta$ is a
constant.

###### Proof.

Immediately follows from the remark to lemma 2 in [12]. ∎

We apply the results of [25] to prove $\lambda$-separability of
$d$-dimensional graphs.

######  Definition 4 ([25], definition 2.3).

Let $\alpha\geq 1$ be given, and let $B=\\{B_{1},B_{2},\dots,B_{p}\\}$ be a
set of closed $d$-dimensional balls with non-overlapping interiors. The
_$\alpha$ -overlap graph_ for $B$ is the undirected graph with vertices
$V=\\{1,2,\dots,p\\}$ and edges

$E=\\{\\{i,j\\}\colon B_{i}\cap(\alpha\cdot B_{j})\neq\varnothing\text{ and
}(\alpha\cdot B_{i})\cap B_{j}\neq\varnothing\\},$

where $\alpha\cdot B_{j}$ is a ball centered as $B_{j}$ and having $\alpha$
times greater radii.

The following lemma shows the connection between $d$-dimensional graphs and
$\alpha$-overlap graphs.

######  Lemma 11.

Let $\mathcal{G}$ be a class of $d$-dimensional graphs with a parameter
$c_{e}$. Then each graph in $\mathcal{G}$ can be supplemented by some number
of edges (maybe $0$) resulting to a $2c_{e}$-overlap graph in a
$d$-dimensional space.

###### Proof.

Let $G\in\mathcal{G}$. Consider the placement of $G$ into a $d$-dimensional
space, and let $G^{\prime}$ be the $2c_{e}$-overlap graph for the balls of
radii $0.5$ and centers in the vertices of $G$. Since the distance between
centers of any two balls is not less than $1$, interiors of the balls do not
intersect.

If there is an edge between two vertices in $G$, the distance between the
centers of the corresponding balls does not exceed $c_{e}$. Therefore balls
with the same centers and radii $0.5$ and $0.5\cdot 2c_{e}=c_{e}$ respectively
would intersect. Hence all edges of $G$ are also edges of $G^{\prime}$. ∎

######  Lemma 12 ([25], theorem 2.4).

Let $d\geq 1$, $\alpha\geq 1$ be constants. Then there exists a function

$f(p)=O\left(\alpha\cdot p^{\frac{d-1}{d}}+c(\alpha,d)\right)$

such that each $\alpha$-overlap graph in a $d$-dimensional space is vertex
$f(p)$-separable. The separator splits its parent graph into pieces with no
more than $\frac{d+1}{d+2}$ of the initial number of vertices.

Essentially lemma 12 claims $\frac{d-1}{d}$-separability of all
$\alpha$-overlap graphs in a $d$-dimensional space.

######  Remark 5.

In the source [25] lemma 12 was stated in a slightly different way.
Considering any $\alpha$-overlap graph in $d$-dimensional space, it was
claimed that the graph has a separator of size bounded by $O\left(\alpha\cdot
p^{\frac{d-1}{d}}+c(\alpha,d)\right)$. Since the separability function is
common for all graphs in a monotone class, we modified the statement of the
lemma in this paper to emphasize the independence of the separability function
from individual graphs.

######  Corollary 3.

Let $\mathcal{G}$ be a class of $d$-dimensional graphs. Then $\mathcal{G}$ is
$p^{\frac{d-1}{d}}$-separable.

###### Proof.

Immediately follows from lemmas 11 and 12. ∎

###  5.2 Shannon function bounds

#####  $d$-dimensional circuits.

We apply the properties of $d$-dimensional graphs proved in the previous
section and obtain the lower bound for $d$-dimensional circuits.

######  Theorem 2.

Let $T$ be a $d$-dimensional support. Then

$L(M_{k}^{T},n)\gtrsim\frac{2^{n}}{\min(n,d\log k)}\quad\mbox{as}\quad
k\to\infty,\ n\to\infty.$

###### Proof.

Immediately follows from theorem 1, lemmas 9, 10 and corollary 3. ∎

##### Multidimensional rectangular circuits.

Multidimensional rectangular circuits are a special case of $d$-dimensional
circuits, thus the lower bound from theorem 2 is also applicable for these
circuits.

An upper bound of Shannon function for multidimensional rectangular circuits
was proved in [15].

######  Lemma 13 ([15], theorem 1).

$L(M_{k}^{d},n)\lesssim\frac{2^{n}}{\min(n,d\log k)}\quad\mbox{as}\quad
k\to\infty,\ n\to\infty.$

Applying theorem 2 and lemma 13 we obtain the asymptotics of Shannon function
for multidimensional rectangular circuits.

######  Corollary 4.

$L(M_{k}^{d},n)\sim\frac{2^{n}}{\min(n,d\log k)}\quad\mbox{as}\quad
k\to\infty,\ n\to\infty.$

##  6 Conclusion

In this paper we proved the lower bound for Shannon function
$L(M_{k}^{T},n)\gtrsim\max\left(\frac{2^{n}}{n},\frac{2^{n}(1-\lambda)}{\log
k}\right)$ for any support $T$ from a class $\mathcal{G}(\lambda,q,\theta)$.
An important special case of such supports are $d$-dimensional graphs for
which thereby we proved the lower bound
$L(M_{k}^{T},n)\gtrsim\frac{2^{n}}{\min(n,d\log k)}$.

A natural direction of developing the obtained results is examining classes of
graphs with a separability function different from $p^{\lambda}$. For example,
graphs supporting a placement in a hyperbolic space are of interest. It was
proved in [21] that such graphs have logarithmic separability function.
Corollary 2 of theorem 1 allows to obtain a lower bound for Shannon function
for such graphs. However the question about upper bounds remains open.

## References

  * [1]
  * [2]
  * [3] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [4] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [5] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [6] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [7] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [8] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [9] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [10] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [11] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [12] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [13] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [14] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [15] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [16] , , . Т. : , (), , , , № , , , ред. , , , ; , ; , , , ISBN: () (), с., , arXiv: , (совм. с )
  * [17] , ‘‘’’, , (), , , :, ( ), , () (), с., , arXiv: , (совм. с ) .
  * [18] , ‘‘’’, : , , . Т. : , (), , , , № , , , ред. , , , ; , ; , , , , ISBN: () (), с., , arXiv: , (совм. с ) .
  * [19] , ‘‘’’, , (), , , :, ( ), , () (), pp., , arXiv: , (with ) .
  * [20] , ‘‘’’, , (), , , :, ( ), , () (), pp., , arXiv: , (with ) .
  * [21] , ‘‘’’, : , , . V. : , (), , , , no. , , , ed. , , , ; , ; , , , , ISBN: () (), pp., , arXiv: , (with ) .
  * [22] , ‘‘’’, : , , . V. : , (), , , , no. , , , eds. , , , ; , ; , , , , ISBN: () (), pp., , arXiv: , (with ) .
  * [23] , ‘‘’’, , (), , , :, ( ), , () (), pp., , arXiv: , (with ) .
  * [24] , ‘‘’’, , (), , , :, ( ), , () (), pp., , arXiv: , (with ) .
  * [25] , ‘‘’’, , (), , , :, ( ), , () (), pp., , arXiv: , (with ) .
  * [26] , ‘‘’’, , (), , , :, ( ), , () (), pp., , arXiv: , (with ) .
  * [27] , ‘‘’’, : , , . V. : , (), , , , no. , , , eds. , , , ; , ; , , , , ISBN: () (), pp., , arXiv: , (with ) .
  * [28] , ‘‘’’, , (), , , :, ( ), , () (), pp., , arXiv: , (with ) .
  * [29] , ‘‘’’, : , , . V. : , (), , , , no. , , , ed. , , , ; , ; , , , , ISBN: () (), pp., , arXiv: , (with ) .
  * [30] , , . V. : , (), , , , no. , , , ed. , , , ; , ; , , , ISBN: () (), pp., , arXiv: , (with ) .


* Han et al. [2014] Han, Z., To, G.N.S., Fu, S.C., Chao, C.Y.H., Weng, W., Huang, Q., 2014.  Effect of human movement on airborne disease transmission in an airplane cabin: study using numerical modeling and quantitative risk analysis.  BMC infectious diseases 14, 434\.  doi:10.1186/1471-2334-14-434.
  * Han et al. [2013] Han, Z.Y., Weng, W.G., Huang, Q.Y., 2013.  Characterizations of particle size distribution of the droplets exhaled by sneeze.  Journal of The Royal Society Interface 10, 20130560.  doi:10.1098/rsif.2013.0560.
  * Hasan et al. [2010] Hasan, M.A., Lange, C.F., King, M.L., 2010.  Effect of artificial mucus properties on the characteristics of airborne bioaerosol droplets generated during simulated coughing.  Journal of Non-Newtonian Fluid Mechanics 165, 1431 – 1441.  doi:10.1016/j.jnnfm.2010.07.005.
  * He et al. [2011] He, Q., Niu, J., Gao, N., Zhu, T., Wu, J., 2011.  Cfd study of exhaled droplet transmission between occupants under different ventilation strategies in a typical office room.  Building and Environment 46, 397 – 408.  doi:10.1016/j.buildenv.2010.08.003.
  * Helbing et al. [2005] Helbing, D., Buzna, L., Johansson, A., Werner, T., 2005\.  Self-organized pedestrian crowd dynamics: Experiments, simulations, and design solutions.  Transportation Science 39, 1–24.  doi:10.1287/trsc.1040.0108.
  * Helbing and Molnar [1995] Helbing, D., Molnar, P., 1995\.  Social force model for pedestrian dynamics.  Physical Review E 51, 395–414.  doi:10.1103/PhysRevE.51.4282.
  * Hermans et al. [2015] Hermans, E., Bhamla, M.S., Kao, P., Fuller, G.G., Vermant, J., 2015.  Lung surfactants and different contributions to thin film stability.  Soft matter 11, 8048–8057.  doi:10.1039/C5SM01603G.
  * Huang et al. [2020] Huang, C., Wang, Y., Li, X., Ren, L., Zhao, J., Hu, Y., Zhang, L., Fan, G., Xu, J., Gu, X., Cheng, Z., Yu, T., Xia, J., Wei, Y., Wu, W., Xie, X., Yin, W., Li, H., Liu, M., Xiao, Y., Gao, H., Guo, L., Xie, J., Wang, G., Jiang, R., Gao, Z., Jin, Q., Wang, J., Cao, B., 2020.  Clinical features of patients infected with 2019 novel coronavirus in Wuhan, China.  The Lancet 395, 497 – 506.  doi:10.1016/S0140-6736(20)30183-5.
  * ICTV [2020] ICTV, 2020.  International Committee on Taxonomy of Viruses.  Available at https://ictv.global/taxonomy/.  Accessed 8.5.2020.
  * Ijaz et al. [1985] Ijaz, M.K., Brunner, A.H., Sattar, S.A., Nair, R.C., Johnson-Lussenburg, C.M., 1985.  Survival characteristics of airborne human coronavirus 229e.  Journal of General Virology 66, 2743–2748.  doi:10.1099/0022-1317-66-12-2743.
  * Jasak et al. [1999] Jasak, H., Weller, H., Gosman, A., 1999.  High resolution nvd differencing scheme for arbitrarily unstructured meshes.  International Journal for Numerical Methods in Fluids 31, 431–449.  doi:10.1002/(SICI)1097-0363(19990930)31:2<431::AID-FLD884>3.0.CO;2-T.
  * Jin et al. [2020] Jin, Y., Yang, H., Ji, W., Wu, W., Chen, S., Zhang, W., Duan, G., 2020\.  Virology, epidemiology, pathogenesis, and control of covid-19.  Viruses 12.  doi:10.3390/v12040372.
  * Kim et al. [2013] Kim, I., Galiza, R., LuisFerreira, 2013.  Modeling pedestrian queuing using micro-simulation.  Transportation Research Part A: Policy and Practice 49, 232–240.  doi:10.1016/j.tra.2013.01.018.
  * King et al. [2015] King, M.F., Noakes, C.J., Sleigh, P.A., 2015.  Modeling environmental contamination in hospital single- and four-bed rooms.  Indoor Air 25, 694–707.  doi:10.1111/ina.12186.
  * Kutter et al. [2018] Kutter, J.S., Spronken, M.I., Fraaij, P.L., Fouchier, R.A., Herfst, S., 2018.  Transmission routes of respiratory viruses among humans.  Current Opinion in Virology 28, 142 – 151.  doi:10.1016/j.coviro.2018.01.001.
  * Larson et al. [2005] Larson, J.S., Bradlow, E.T., Fader, P.S., 2005.  An exploratory look at supermarket shopping paths.  International Journal of Research in Marketing 22, 395–414.  doi:10.1016/j.ijresmar.2005.09.005.
  * Laurila et al. [2019] Laurila, E., Roenby, J., Maakala, V., Peltonen, P., Kahila, H., Vuorinen, V., 2019\.  Analysis of viscous fluid flow in a pressure-swirl atomizer using large-eddy simulation.  International Journal of Multiphase Flow 113, 371 – 388.  doi:10.1016/j.ijmultiphaseflow.2018.10.008.
  * Lenhart et al. [2004] Lenhart, S.W., Seitz, T., Trout, D., Bollinger, N., 2004\.  Issues affecting respirator selection for workers exposed to infectious aerosols: Emphasis on healthcare settings.  Applied Biosafety 9, 20–36.  doi:10.1177/153567600400900104.
  * Leung et al. [2020] Leung, N.H., Chu, D.K., Shiu, E.Y., Chan, K.H., McDevitt, J.J., Hau, B.J., Yen, H.L., Li, Y., Ip, D.K., Peiris, J.M., et al., 2020.  Respiratory virus shedding in exhaled breath and efficacy of face masks.  Nature Medicine , 1–5doi:10.1038/s41591-020-0843-2.
  * Li et al. [2018a] Li, F., Liu, J., Ren, J., Cao, X., 2018a.  Predicting contaminant dispersion using modified turbulent schmidt numbers from different vortex structures.  Building and Environment 130, 120 – 127.  doi:10.1016/j.buildenv.2017.12.023.
  * Li et al. [2003] Li, W., Moore, M.J., Vasilieva, N., Sui, J., Wong, S.K., Berne, M.A., Somasundaran, M., Sullivan, J.L., Luzuriaga, K., Greenough, T.C., Choe, H., Farzan, M., 2003\.  Angiotensin-converting enzyme 2 is a functional receptor for the sars coronavirus.  Nature 426, 450–454.  doi:10.1038/nature02145.
  * Li et al. [2018b] Li, X., Shang, Y., Yan, Y., Yang, L., Tu, J., 2018b.  Modelling of evaporation of cough droplets in inhomogeneous humidity fields using the multi-component eulerian-lagrangian approach.  Building and Environment 128, 68 – 76.  doi:10.1016/j.buildenv.2017.11.025.
  * Li et al. [2005] Li, Y., Huang, X., Yu, I.T.S., Wong, T., Qian, H., 2005\.  Role of air distribution in sars transmission during the largest nosocomial outbreak in hong kong.  Indoor air 15, 83—95.  doi:10.1111/j.1600-0668.2004.00317.x.
  * Li et al. [2007] Li, Y., Leung, G., Tang, J., Yang, X., Chao, C.Y.H., Lin, J., Lu, J., Nielsen, P., Niu, J., Qian, H., Sleigh, A., Su, H.J.J., Sundell, J., Wong, T., Yuen, P., 2007.  Role of ventilation in airborne transmission of infectious agents in the built environment - a multidisciplinary systematic review.  Indoor Air 17, 2—18.  doi:10.1111/j.1600-0668.2006.00445.x.
  * Licina et al. [2015] Licina, D., Melikov, A., Pantelic, J., Sekhar, C., Tham, K.W., 2015.  Human convection flow in spaces with and without ventilation: personal exposure to floor-released particles and cough-released droplets.  Indoor Air 25, 672–682.  doi:10.1111/ina.12177.
  * Lindsley et al. [2015] Lindsley, W.G., Noti, J.D., Blachere, F.M., Thewlis, R.E., Martin, S.B., Othumpangat, S., Noorbakhsh, B., Goldsmith, W.T., Vishnu, A., Palmer, J.E., Clark, K.E., Beezhold, D.H., 2015\.  Viable influenza a virus in airborne particles from human coughs.  Journal of Occupational and Environmental Hygiene 12, 107–113.  doi:10.1080/15459624.2014.973113.
  * Lindsley et al. [2012] Lindsley, W.G., Pearce, T.A., Hudnall, J.B., Davis, K.A., Davis, S.M., Fisher, M.A., Khakoo, R., Palmer, J.E., Clark, K.E., Celik, I., Coffey, C.C., Blachere, F.M., Beezhold, D.H., 2012.  Quantity and size distribution of cough-generated aerosol particles produced by influenza patients during and after illness.  Journal of Occupational and Environmental Hygiene 9, 443–449.  doi:10.1080/15459624.2012.684582.
  * Lindsley et al. [2013] Lindsley, W.G., Reynolds, J.S., Szalajda, J.V., Noti, J.D., Beezhold, D.H., 2013.  A cough aerosol simulator for the study of disease transmission by human cough-generated aerosols.  Aerosol Science and Technology 47, 937–944.  doi:10.1080/02786826.2013.803019.
  * Liu et al. [2017] Liu, L., Li, Y., Nielsen, P.V., Wei, J., Jensen, R.L., 2017\.  Short-range airborne transmission of expiratory droplets between two people.  Indoor Air 27, 452–462.  doi:10.1111/ina.12314.
  * Liu and You [2012] Liu, W., You, X., 2012.  Transportation and risk analysis of influenza indoor and outdoor transportation and exposure risk analysis of influenza aerosol.  Indoor and Built Environment 45, 614 – 621.  doi:10.1177/1420326X11426164.
  * Loudon and Roberts [1967] Loudon, R.G., Roberts, R.M., 1967\.  Droplet expulsion from the respiratory tract.  Am Rev Respir Dis. 95, 435–442.  doi:doi:10.1164/arrd.1967.95.3.435.
  * Lu et al. [2020] Lu, J., Gu, J., Li, K., Xu, C., Su, W., Lai, Z., Zhou, D., Yu, C., Xu, B., Yang, Z., 2020.  Covid-19 outbreak associated with air conditioning in restaurant, guangzhou, china, 2020.  Emerging infectious diseases 26.  doi:10.3201/eid2607.200764.
  * Macher [1999] Macher, J., 1999.  Bioaerosols: Assessment and Control.  ACGIH (American Conference of Governmental Industrial Hygienists).
  * Maronga et al. [2020] Maronga, B., Banzhaf, S., Burmeister, C., Esch, T., Forkel, R., Fröhlich, D., Fuka, V., Gehrke, K.F., Geletič, J., Giersch, S., Gronemeier, T., Groß, G., Heldens, W., Hellsten, A., Hoffmann, F., Inagaki, A., Kadasch, E., Kanani-Sühring, F., Ketelsen, K., Khan, B.A., Knigge, C., Knoop, H., Krč, P., Kurppa, M., Maamari, H., Matzarakis, A., Mauder, M., Pallasch, M., Pavlik, D., Pfafferott, J., Resler, J., Rissmann, S., Russo, E., Salim, M., Schrempf, M., Schwenkel, J., Seckmeyer, G., Schubert, S., Sühring, M., von Tils, R., Vollmer, L., Ward, S., Witha, B., Wurps, H., Zeidler, J., Raasch, S., 2020\.  Overview of the palm model system 6.0.  Geoscientific Model Development 13, 1335–1372.  doi:10.5194/gmd-13-1335-2020.
  * Maronga et al. [2015] Maronga, B., Gryschka, M., Heinze, R., Hoffmann, F., Kanani-Sühring, F., Keck, M., Ketelsen, K., Letzel, M.O., Sühring, M., Raasch, S., 2015\.  The parallelized large-eddy simulation model (palm) version 4.0 for atmospheric and oceanic flows: model formulation, recent developments, and future perspectives.  Geoscientific Model Development 8, 2515–2551.  doi:10.5194/gmd-8-2515-2015.
  * McGrattan et al. [2019] McGrattan, K., Hostikka, S., Floyd, J., McDermott, R., Vanella, M., 2019.  Fire dynamics simulator technical reference guide. volume 1: Mathematical model.  NIST special publication 1018, 195\.
  * McGrattan et al. [2012] McGrattan, K., McDermott, R., Floyd, J., Hostikka, S., Forney, G., Baum, H., 2012\.  Computational fluid dynamics modelling of fire.  International Journal of Computational Fluid Dynamics 26, 349–361.  doi:10.1080/10618562.2012.659663.
  * Melegaro et al. [2011] Melegaro, A., Jit, M., Gay, N., Zagheni, E., Edmunds, W.J., 2011.  What types of contacts are important for the spread of infections? using contact survey data to explore european mixing patterns.  Epidemics 3, 143 – 151.  doi:10.1016/j.epidem.2011.04.001.
  * Mittal et al. [2020] Mittal, R., Ni, R., Seo, J.H., 2020.  The flow physics of covid-19.  Journal of Fluid Mechanics 894, F2.  doi:10.1017/jfm.2020.330.
  * Morawska et al. [2017] Morawska, L., Ayoko, G., Bae, G., Buonanno, G., Chao, C., Clifford, S., Fu, S., Hänninen, O., He, C., Isaxon, C., Mazaheri, M., Salthammer, T., Waring, M., Wierzbicka, A., 2017\.  Airborne particles in indoor environment of homes, schools, offices and aged care facilities: The main routes of exposure.  Environment International 108, 75 – 83.  doi:10.1016/j.envint.2017.07.025.
  * Morawska and Cao [2020] Morawska, L., Cao, J., 2020\.  Airborne transmission of sars-cov-2: The world should face the reality.  Environment International 139, 105730\.  doi:10.1016/j.envint.2020.105730.
  * Oboho et al. [2015] Oboho, I.K., Tomczyk, S.M., Al-Asmari, A.M., Banjar, A.A., Al-Mugti, H., Aloraini, M.S., Alkhaldi, K.Z., Almohammadi, E.L., Alraddadi, B.M., Gerber, S.I., Swerdlow, D.L., Watson, J.T., Madani, T.A., 2015.  2014 mers-cov outbreak in jeddah — a link to health care facilities.  New England Journal of Medicine 372, 846–854.  doi:10.1056/NEJMoa1408636.
  * Olmedo et al. [2012] Olmedo, I., Nielsen, P.V., Ruiz de Adana, M., Jensen, R.L., Grzelecki, P., 2012.  Distribution of exhaled contaminants and personal exposure in a room using three different air distribution strategies.  Indoor Air 22, 64–76.  doi:10.1111/j.1600-0668.2011.00736.x.
  * Papineni and Rosenthal [1997] Papineni, R.S., Rosenthal, F.S., 1997\.  The size distribution of droplets in the exhaled breath of healthy human subjects.  Journal of Aerosol Medicine 10, 105–116.  doi:10.1089/jam.1997.10.105.
  * Park et al. [2019] Park, W.B., Kwon, N.J., Choi, S.J., Kang, C.K., Choe, P.G., Kim, J.Y., Yun, J., Lee, G.W., Seong, M.W., Kim, N.J., Seo, J.S., Oh, M.d., 2019\.  Virus isolation from the first patient with sars-cov-2 in korea.  Journal of Korean Medical Science 35\.  doi:10.3346/jkms.2020.35.e84.
  * Peltonen et al. [2019] Peltonen, P., Saari, K., Kukko, K., Vuorinen, V., Partanen, J., 2019.  Large-eddy simulation of local heat transfer in plate and pin fin heat exchangers confined in a pipe flow.  International Journal of Heat and Mass Transfer 134, 641 – 655.  doi:10.1016/j.ijheatmasstransfer.2019.01.046.
  * Peltonen et al. [2018] Peltonen, P., Vuorinen, V., Marin, G., Karttunen, A.J., Karppinen, M., 2018.  Numerical study on the fluid dynamical aspects of atomic layer deposition process.  Journal of Vacuum Science & Technology A 36, 021516.  doi:10.1116/1.5018475.
  * REHVA [2020] REHVA, 2020.  REHVA COVID-19 guidance document, April 3, 2020 (Ver. 2). Federation of European Heating, Ventilation and Air Conditioning Associations.  Available at https://www.rehva.eu/activities/covid-19-guidance.  Accessed 15.5.2020.
  * Riley et al. [1978] Riley, E.C., Murphy, G., Riley, R.L., 1978.  Airborne Spread Of Measles In A Suburban Elementary School.  American Journal of Epidemiology 107, 421–432.  doi:10.1093/oxfordjournals.aje.a112560.
  * Riley et al. [2003] Riley, S., Fraser, C., Donnelly, C.A., Ghani, A.C., Abu-Raddad, L.J., Hedley, A.J., Leung, G.M., Ho, L.M., Lam, T.H., Thach, T.Q., Chau, P., Chan, K.P., Lo, S.V., Leung, P.Y., Tsang, T., Ho, W., Lee, K.H., Lau, E.M.C., Ferguson, N.M., Anderson, R.M., 2003.  Transmission dynamics of the etiological agent of sars in hong kong: Impact of public health interventions.  Science 300, 1961–1966.  doi:10.1126/science.1086478.
  * Rothe et al. [2020] Rothe, C., Schunk, M., Sothmann, P., Bretzel, G., Froeschl, G., Wallrauch, C., Zimmer, T., Thiel, V., Janke, C., Guggemos, W., Seilmaier, M., Drosten, C., Vollmar, P., Zwirglmaier, K., Zange, S., Wölfel, R., Hoelscher, M., 2020.  Transmission of 2019-nCoV infection from an asymptomatic contact in Germany.  New England Journal of Medicine 382, 970–971.  doi:10.1056/NEJMc2001468.
  * Seymour et al. [2000] Seymour, M.J., Alani, A., Manning, A., Jiang, J., 2000\.  Airflow modelling to investigate the effectiveness of control methods intended to prevent the transmission of airborne organisms, in: Awbi, H.B. (Ed.), Air Distribution in Rooms, (ROOMVENT 2000), pp. 77–82.
  * Stadnytskyi et al. [2020] Stadnytskyi, V., Bax, C.E., Bax, A., Anfinrud, P., 2020\.  The airborne lifetime of small speech droplets and their potential importance in SARS-CoV-2 transmission.  Proceedings of the National Academy of Sciences doi:10.1073/pnas.2006874117.
  * Tellier et al. [2019] Tellier, R., Li, Y., Cowling, B.J., Tang, J.W., 2019\.  Recognition of aerosol transmission of infectious agents: a commentary.  BMC infectious diseases 19, 101\.  doi:10.1186/s12879-019-3707-y.
  * Thomas [2012] Thomas, M.K., 2012.  Airborne Disease Transmission via Bioaerosols: Formation Mechanisms and the Influence of Viscoelasticity.  Ph.D. thesis. Harvard University.  URL: http://nrs.harvard.edu/urn-3:HUL.InstRepos:10436309.
  * Tian et al. [2007] Tian, Z., Tu, J., Yeoh, G., Yuen, R., 2007.  Numerical studies of indoor airflow and particle dispersion by large eddy simulation.  Building and Environment 42, 3483 – 3492.  doi:10.1016/j.buildenv.2006.10.047.
  * To et al. [2009] To, G.N.S., Wan, M.P., Chao, C.Y.H., Fang, L., Melikov, A., 2009.  Experimental study of dispersion and deposition of expiratory aerosols in aircraft cabins and impact on infectious disease transmission.  Aerosol Science and Technology 43, 466–485.  doi:10.1080/02786820902736658.
  * Vasudevan and Lange [2007] Vasudevan, M., Lange, C.F., 2007\.  Surface tension effects on instability in viscoelastic respiratory fluids.  Mathematical Biosciences 205, 180 – 194.  doi:10.1016/j.mbs.2006.08.009.
  * Vejerano and Marr [2018] Vejerano, E.P., Marr, L.C., 2018\.  Physico-chemical characteristics of evaporating respiratory fluid droplets.  Journal of The Royal Society Interface 15, 20170939.  doi:10.1098/rsif.2017.0939.
  * Vuorinen and Keskinen [2016] Vuorinen, V., Keskinen, K., 2016\.  Dnslab: A gateway to turbulent flow simulation in matlab.  Computer Physics Communications 203, 278 – 289.  doi:10.1016/j.cpc.2016.02.023.
  * Wan et al. [2009] Wan, M.P., To, G.N.S., Chao, C.Y.H., Fang, L., Melikov, A., 2009.  Modeling the fate of expiratory aerosols and the associated infection risk in an aircraft cabin environment.  Aerosol Science and Technology 43, 322–343.  doi:10.1080/02786820802641461.
  * Wang et al. [2020] Wang, Y., Liu, Y., Liu, L., Wang, X., Luo, N., Ling, L., 2020.  Clinical outcome of 55 asymptomatic cases at the time of hospital admission infected with sars-coronavirus-2 in shenzhen, china.  The Journal of infectious diseases doi:10.1093/infdis/jiaa119.
  * Weller et al. [1998] Weller, H.G., Tabor, G., Jasak, H., Fureby, C., 1998\.  A tensorial approach to computational continuum mechanics using object-oriented techniques.  Computers in Physics 12, 620–631.  doi:10.1063/1.168744.
  * WHO [2009] WHO, 2009.  Natural ventilation for infection control in health-care settings.  World Health Organization.  URL: https://www.who.int/water_sanitation_health/publications/natural_ventilation/en/.
  * WHO [2020a] WHO, 2020a.  Advice for public – maintain at least 1 metre (3 feet) distance between yourself and anyone who is coughing or sneezing. World Health Organization.  Available at https://www.who.int/emergencies/diseases/novel-coronavirus-2019/advice-for-public.  Accessed 11.5.2020.
  * WHO [2020b] WHO, 2020b.  Modes of transmission of virus causing COVID-19: implications for IPC precaution recommendations.  Scientific brief. World Health Organization.  Ref.No. WHO/2019-nCoV/Sci_Brief/Transmission_modes/2020.2.
  * Wicker and Skamarock [2002] Wicker, L.J., Skamarock, W.C., 2002\.  Time-splitting methods for elastic models using forward time schemes.  Monthly Weather Review 130, 2088–2097.  doi:10.1175/1520-0493(2002)130<2088:TSMFEM>2.0.CO;2.
  * Williamson [1980] Williamson, J., 1980.  Low-storage runge-kutta schemes.  Journal of Computational Physics 35, 48 – 56.  doi:10.1016/0021-9991(80)90033-9.
  * Wölfel et al. [2020] Wölfel, R., Corman, V.M., Guggemos, W., Seilmaier, M., Zange, S., Müller, M.A., Niemeyer, D., Jones, T.C., Vollmar, P., Rothe, C., Hoelscher, M., Bleicker, T., Brünink, S., Schneider, J., Ehmann, R., Zwirglmaier, K., Drosten, C., Wendtner, C., 2020\.  Virological assessment of hospitalized patients with covid-2019.  Nature , 1–5doi:10.1038/s41586-020-2196-x.
  * Woo et al. [2009] Woo, P.C.Y., Lau, S.K.P., Huang, Y., Yuen, K.Y., 2009\.  Coronavirus diversity, phylogeny and interspecies jumping.  Experimental Biology and Medicine 234, 1117–1127.  doi:10.3181/0903-MR-94.
  * Xie et al. [2007] Xie, X., Li, Y., Chwang, A.T.Y., Ho, P., Seto, W., 2007\.  How far droplets can move in indoor environments–revisiting the wells evaporation-falling curve.  Indoor air 17, 211—225.  doi:10.1111/j.1600-0668.2007.00469.x.
  * Yang et al. [2007] Yang, S., Lee, G.W., Chen, C.M., Wu, C.C., Yu, K.P., 2007\.  The size and concentration of droplets generated by coughing in human subjects.  Journal of Aerosol Medicine 20, 484–494.  doi:10.1089/jam.2007.0610.
  * Yen et al. [2011] Yen, H.L., Liang, C.H., Wu, C.Y., Forrest, H.L., Ferguson, A., Choy, K.T., Jones, J., Wong, D.D.Y., Cheung, P.P.H., Hsu, C.H., Li, O.T., Yuen, K.M., Chan, R.W.Y., Poon, L.L.M., Chan, M.C.W., Nicholls, J.M., Krauss, S., Wong, C.H., Guan, Y., Webster, R.G., Webby, R.J., Peiris, M., 2011\.  Hemagglutinin–neuraminidase balance confers respiratory-droplet transmissibility of the pandemic h1n1 influenza virus in ferrets.  Proceedings of the National Academy of Sciences 108, 14264–14269.  doi:10.1073/pnas.1111000108.
  * Yu et al. [2004] Yu, I.T., Li, Y., Wong, T.W., Tam, W., Chan, A.T., Lee, J.H., Leung, D.Y., Ho, T., 2004.  Evidence of airborne transmission of the severe acute respiratory syndrome virus.  New England Journal of Medicine 350, 1731–1739.  doi:10.1056/NEJMoa032867.
  * Yu et al. [2005] Yu, I.T.S., Wong, T.W., Chiu, Y.L., Lee, N., Li, Y., 2005.  Temporal-Spatial Analysis of Severe Acute Respiratory Syndrome among Hospital Inpatients.  Clinical Infectious Diseases 40, 1237–1243.  doi:10.1086/428735.
  * Yu et al. [2016] Yu, K., Yang, J., Zuo, Y.Y., 2016.  Automated droplet manipulation using closed-loop axisymmetric drop shape analysis.  Langmuir 32, 4820–4826.  doi:10.1021/acs.langmuir.6b01215.
  * Zhang and Chen [2006] Zhang, Z., Chen, Q., 2006.  Experimental measurements and numerical simulations of particle transport and distribution in ventilated rooms.  Atmospheric Environment 40, 3396 – 3408.  doi:10.1016/j.atmosenv.2006.01.014.
  * Zheng et al. [2020] Zheng, S., Fan, J., Yu, F., Feng, B., Lou, B., Zou, Q., Xie, G., Lin, S., Wang, R., Yang, X., Chen, W., Wang, Q., Zhang, D., Liu, Y., Gong, R., Ma, Z., Lu, S., Xiao, Y., Gu, Y., Zhang, J., Yao, H., Xu, K., Lu, X., Wei, G., Zhou, J., Fang, Q., Cai, H., Qiu, Y., Sheng, J., Chen, Y., Liang, T., 2020\.  Viral load dynamics and disease severity in patients infected with sars-cov-2 in zhejiang province, china, january-march 2020: retrospective cohort study.  BMJ 369.  doi:10.1136/bmj.m1443.
  * Zhou et al. [2018] Zhou, J., Wei, J., Choy, K.T., Sia, S.F., Rowlands, D.K., Yu, D., Wu, C.Y., Lindsley, W.G., Cowling, B.J., McDevitt, J., Peiris, M., Li, Y., Yen, H.L., 2018.  Defining the sizes of airborne particles that mediate influenza transmission in ferrets.  Proceedings of the National Academy of Sciences 115, E2386–E2392.  doi:10.1073/pnas.1716771115.
  * Zhu et al. [2020] Zhu, N., Zhang, D., Wang, W., Li, X., Yang, B., Song, J., Zhao, X., Huang, B., Shi, W., Lu, R., Niu, P., Zhan, F., Ma, X., Wang, D., Xu, W., Wu, G., Gao, G.F., Tan, W., 2020.  A novel coronavirus from patients with pneumonia in china, 2019.  New England Journal of Medicine 382, 727–733.  doi:10.1056/NEJMoa2001017.
  * Zou et al. [2020] Zou, L., Ruan, F., Huang, M., Liang, L., Huang, H., Hong, Z., Yu, J., Kang, M., Song, Y., Xia, J., Guo, Q., Song, T., He, J., Yen, H.L., Peiris, M., Wu, J., 2020.  SARS-CoV-2 viral load in upper respiratory specimens of infected patients.  New England Journal of Medicine 382, 1177–1179.  doi:10.1056/NEJMc2001737.
  * Zuo et al. [2006] Zuo, Y.Y., Acosta, E., Policova, Z., Cox, P.N., Hair, M.L., Neumann, A.W., 2006\.  Effect of humidity on the stability of lung surfactant films adsorbed at air–water interfaces.  Biochimica et Biophysica Acta (BBA) - Biomembranes 1758, 1609 – 1620.  doi:10.1016/j.bbamem.2006.07.004.