# Network location and clustering of genetic mutations determine chronicity in
a stylized model of genetic diseases

Piotr Nyczka  Faculty of Management, Wrocław University of Science and
Technology  Department of Life Sciences and Chemistry, Jacobs University,
D-28759 Bremen, Germany  Johannes Falk  Department of Life Sciences and
Chemistry, Jacobs University, D-28759 Bremen, Germany  j.falk@jacobs-
university.de  Marc-Thorsten Hütt  Department of Life Sciences and Chemistry,
Jacobs University, D-28759 Bremen, Germany

###### Abstract

In a highly simplified view, a disease can be seen as the phenotype emerging
from the interplay of genetic predisposition and fluctuating environmental
stimuli. We formalize this situation in a minimal model, where a network
(representing cellular regulation) serves as an interface between an input
layer (representing environment) and an output layer (representing functional
phenotype). Genetic predisposition for a disease is represented as a loss of
function of some network nodes. Reduced, but non-zero, output indicates
disease. The simplicity of this genetic disease model and its deep
relationship to percolation theory allows us to understand the interplay
between disease, network topology and the location and clusters of affected
network nodes. We find that our model generates two different characteristics
of diseases, which can be interpreted as chronic and acute diseases. In its
stylized form, our model provides a new view on the relationship between
genetic mutations and the type and severity of a disease.

## Introduction

The debate on how to define disease is shaped by the necessity of balancing
formal definitions motivated by physiology and correspondence with societal
norms and expectations [1, 2, 3]. At the core of early definitions of diseases
is a dysfunction of an organismal subsystem (often on the systemic level of
organs), which affects the evolutionary goals of the organism as a whole [4,
5]. The challenge of defining disease is also reflected in the multitude of
disease ontologies [6] and the limited ability to create mappings among them
[7].

On a theoretical level, the multi-stage model of carcinogenesis [8, 9] is an
early example of formalizing diseases using a high-level abstraction in terms
of a mathematical framework by writing down an explicit equation for the
incidence as a function of age, based on the assumption of carcinogenesis as a
multi-stage process [9]. The model has been extended by Rozhok and DeGregori
[10] including environmental factors and in [11] incorporating additional
levels of detail, leading to insight into disease mechanisms and in
particular, providing an explanation of the nearly universal age-dependent
incidence patterns observed across many cancers. This evolutionary model of
cancer considers oncogenic mutations as well as tumour microenvironment and
tissue architecture. The question of, how in the case of cancer the
environment contributes to risk has been addressed in [12], where the
necessity of adopting an ecological perspective on diseases has also been
pointed out.

A recent review [13] summarizing the application of network biology to human
diseases illustrates how disease mutations can be thought of in a network and
emphasizes the importance of considering biological networks embedded in an
environmental context.

As an illustration of this avenue of research to one specific non-cancer
disease, in [14] the authors have created a modular graph model to describe
incidence curves for Crohn’s disease, a disease currently in the focus of
interest of Systems Medicine [15, 16, 17, 18].

Most approaches in Systems Medicine fall into two categories, (1) employing
mathematical or computational concepts to analyze medical data and (2)
employing mathematical or computational concepts to model a specific disease
or class of diseases. In contrast to these data-driven or single-disease
approaches, we here strive for a model-driven understanding of some generic
relationships between environment, genotype and disease phenotype. To this
end, we distill the diverse concepts into a highly stylized model of an
abstract genetic disease. A suitable framework is a complex system ${\cal C}$
receiving at each moment in time $t$ an input vector ${\cal I}(t)$
(representing environmental stimuli) and generating an output vector ${\cal
O}(t)$ indicating systemic function.

Our model allows us to simulate the interaction of the disease (represented as
a loss of function of some network nodes) and a fluctuating environment
(represented by inputs to the network). The simplicity of the model enables us
to investigate in detail how the observed features (disease severity,
incidence curves, etc.) depend on the topology of the network and on the
characteristic of the disease.

An important component of the model is that it operates using Boolean logic:
Binary inputs are processed via Boolean ANDs (representing complete
dependence) and ORs (representing the possibility of choice) and yield a
binary output vector. Due to its minimal character and design, we are able to
map the concept of directed percolation [19] onto our disease model. Our
model, therefore, allows harnessing the extensive knowledge of statistical
physics about percolation phenomena [20, 21] for the analysis of diseases.

Detailed analysis of our model suggests the following core properties: Chronic
diseases occur predominantly, when clusters of affected nodes are proximal to
the output layer (representing network function or phenotype) and are enhanced
by network connectivity (higher branching). Acute diseases tend to be
independent of the position of affected nodes in the network. Higher branching
transforms acute diseases into chronic diseases, but also in general reduces
the likelihood of disease.

We further find that for a high number of OR nodes high connectivity between
pathways mitigates the severity of a disease. In contrast, for a high number
of AND nodes, low connectivity mitigates the severity. Additionally, we find
that the impact of the position of the disease-affected nodes increases with
the connectivity and decreases with the fraction of AND nodes.

## Methods

Our disease model is motivated in parts by genome-scale metabolic models [22,
23] and flux-balance analysis [24, 25], where nutrient availability and the
choice of the cellular objective function (e.g., maximization of growth or
energy output) determine the steady-state pattern of metabolic fluxes. It also
bears similarity to random Boolean networks as minimal models of gene-
regulatory systems, where discrete time and the reduced state space allow for
an analysis of attractors and their robustness [26, 27]. As such, our model is
in the tradition of minimal models (or ’toy models’, ’stylized models’) in
statistical physics [28, 29].

Figure 1 summarizes the general scheme of our investigation (Fig. 1a), the
formal definition of node states (Fig. 1b), the notion and dynamical effect of
branching (Fig. 1c) and the layer structure of the model (Fig. 1d). In
addition to obvious size parameters (number of input nodes, number of layers),
our model depends on two parameters, the branching probability $b$ and the
ratio $a$ that defines the fraction of nodes that act as AND or OR gates.

### Disordered lattice model

Figure 1:  (a): Flow chart of our investigation: The outputs of a healthy and
a defect (disease) network (receiving the same input vector) are compared.
Depending on their difference they are assigned to a specific class: Class A,
if both outputs are equal (no disease), class B, if the disease network has a
lower but non-zero output (symptomatic disease), class C, if the disease
network has zero output, while the healthy network has a non-zero output
(lethal disease), class D, if both the healthy and the disease network have
zero output.
(b): Definition of node states and visual representation of the effect of a
non-functional node. (c): Illustration of branching and visual representation
of compensating a defect via interacting pathways. (d): Schematic
representation of the full model and illustration of the layer structure.

Motivated by biological network maps [30, 31] we write the generic biological
network representing genotype and interfacing environment (input layer) and
phenotype (output layer) as a set of $H$ parallel pathways (as depicted in
Fig. 1d). Each idealized pathway is represented as a directed line graph with
$L$ nodes, where each node represents a functional unit of the network that
can either be active or inactive. We characterize each node by its pathway
index $k\in\\{1\dots H\\}$ and its position $j\in\\{1\dots L\\}$ in the
pathway (number of steps from input towards output). Following the definition
of a line graph, each node $(k,j)$ is hence connected to the following node
within the same pathway $(k,j+1)$ via a directed edge. To incorporate generic
dependencies between different pathways (e.g. regulatory and discriminating
mechanisms or regulatory overlap of metabolic pathways) with a probability
given by the branching parameter $b$, a node $(k,j)$ is connected to the
following node of a neighboring pathway $(k-1,j+1)$ or $(k+1,j+1)$,
respectively. We do not employ any type of periodic boundary conditions.
Hence, connections outside the obvious boundaries are omitted. Due to this
branching, each node can have up to three inputs. For simplicity, we assume
that the processing performed at each node is represented by one of two
possible Boolean functions (logical AND or logical OR) determining the local
input-output relation of this node. The parameter $a$ determines the ratio
between the number of nodes that act as ANDs (and consequently $1-a$ is the
percentage of ORs).

The environment is represented by presences and absences of input components
(’stimuli’, ’nutrients’) and hence by a binary vector. This input vector,
together with the processing capabilities of each node, then creates a flux
pattern of active nodes and links which finally results in an output vector.

This model of interdependent pathways is, of course, only a stylized
approximation of a real-life biological network. In order to keep the
interactions as simple as possible, the model is based on several
idealizations: (1) Due to the enforced lattice structure, our model assumes
that within the network only neighbouring pathways can be connected. This does
not reflect the topology of real networks. However, for the sake of
phenomenological insight into the local correlations between pathways, we
decided to concentrate on this lattice structure. (2) As an acyclic graph our
model does not allow for loops. This is at odds with the fact that regulatory
elements heavily rely on direct or indirect feedback mechanisms. Feedback
loops are often associated with rapid systemic responses to perturbations [32,
33]. In this sense, our simplifying assumption is comparable to a steady-state
approximation (e.g. employed in flux-balance analysis in metabolic
investigations [25, 34]). Also, note that the nodes in our network represent
functional units that might internally rely on different feedback structures.

These idealizations do not allow for a one-to-one mapping onto real biological
systems. Our disordered lattice functions as an effective network summarizing
the joint action of a multitude of biological networks – from signalling
pathways [35, 36] and protein interactions [37, 38] to metabolic networks [39,
40].

For biological systems, where the knowledge about interactions of biological
entities is more complete than for human cells, e.g., bacteria, it has been
shown that the precise interplay of genetic regulation and metabolism installs
a balance between robustness to environmental fluctuations and sensitivity to
genetic changes [41, 42, 43]. By adjusting the ratio between AND and OR gates
we can continuously tune our model to such a robust or sensitive behaviour.
For example, in the limit of only AND nodes ($a=1$), a single deactivated
input will cause the deactivation of any connected downstream node. Likewise,
in the limit of only OR nodes ($a=0$), a single activated input activates all
connected downstream nodes. The first row of Fig. 2 illustrates this effect.

Figure 2:  Schematic summaries of various aspects of the model. Red indicates
non-functional nodes (i.e. the genetic predisposition for a disease, ‘disease
nodes’). Green nodes and links indicate activity (‘flux’). Inactive components
are indicated in yellow. All rows (except for the first one) use the same
(intermediate) value of $a$. The first row shows how $a$ affects the impact of
non-functional nodes. The second row illustrates the effect of different
clustering $p$ for the same number of non-functional nodes $D$. The third row
shows how the position of the non-functional nodes can affect the phenotype.
The fourth row is an example of synergistic effects between network and
environment. The fifth row shows an example of a genetic disease being masked
by environmental factors.

### Disease generation

As with many other examples of minimal models or ’toy models’ in biology (see
[44, 45, 28]), the stylized nature of our model allows us to formally
represent many features of a real-life system. In the following, we seek to
study basic disease characteristics.

Within our model, a genetic disease – a genetic predisposition for a disease
phenotype – manifests as a loss of function of one or several network nodes as
shown in Fig. 1b. We characterize such a disease by a set of properties: the
number $D$ of disease-associated (defect) nodes and their distribution,
determined by the clustering parameter $p$ and the resulting average location
$\lambda$. To define which nodes are affected, the first node is chosen
randomly. Then, the selection of the $D-1$ remaining nodes relies on the Eden
growth model [46, 47, 48] with teleportation and proceeds as follows:

  * •

With probability $p$ a node connected to the current cluster of disease-
affected nodes gets deactivated (growth of the current cluster)

  * •

Otherwise (with probability $1-p$) a randomly selected node gets deactivated
and serves as a nucleus for a new cluster.

The parameter $p$ can hence be used to tune the model between a state, where
the disease-associated nodes are either distributed randomly ($p=0$) or
concentrated in one connected cluster ($p=1$) as illustrated in the second row
of Fig. 2.

## Results

### Incidence curves

We are now in a position to analyze how fluctuations of the environment affect
an unperturbed (’healthy’) network in contrast to a network with non-
functional nodes representing a disease genotype.

Due to the focus on only AND or OR gates, a node can only become active, if at
least one input was active. Now, since a disease appears as a deactivated
node, for the same input a defect network has always the same or fewer active
outputs than a healthy network: The active outputs of the disease affected
network are always a proper subset of the active outputs of the healthy
network.

For our quantitative analysis, we first generate a random environmental
condition (characterized by the probability $I$ of active inputs). For every
time step we then proceed as follows (compare Fig. 1a):

  * •

For the given environment we analyze the output vector of the healthy network.
If the vector is zero, the environment is already lethal for a healthy and
hence also for the defect network (case D in Fig. 1).

  * •

If the output of the healthy system is non-zero we compare its output to the
output of a defect network (receiving the same input vector). There are three
possible outcomes: (1) Both vectors are equal. This can be interpreted as no
disease symptoms: Both networks display a healthy phenotype (case A in Fig.
1). (2) The vector of the defect network is non-zero but has fewer non-zero
components than the healthy network. This case represents a disease phenotype
(case B in Fig. 1). (3). The output vector of the defect network is zero. This
indicates lethality due to the disease (case C in Fig. 1).

  * •

To simulate fluctuations in the environment at each time step each element of
the input vector is preselected for change with a fixed probability of 20%.
Then, each element within this preselected group is set to $1$ with
probability $I$ and to $0$ otherwise.

Figure 3:  Top panel: time series of the number of active inputs (grey
background) and the output strength for the healthy (green) and the disease
(red) network. A difference between the red and the green curve (red below
green) indicates visible symptoms. The type of the observed disease is
indicated by the colour bar (colour code as defined in Fig. 1a). Further time
series for different sets of parameters can be found in Figs. S1 and S2.
Bottom panel: histograms of disease incidences for different values of $p$.

As a result, we obtain time series as shown in Figures 3 (top). Here, the
green and red curves represent the output strength of the healthy and the
disease network, respectively. Every difference between the green and the red
curves thus indicates a disease phenotype for the respective environment. The
corresponding case of the four possible (no detectable disease, disease
phenotype, death due to disease, death due to environmental conditions) is
indicated by the respective colour in the bars in the lower segment. For all
time series without death, it is possible to analyze the distribution of time
spans with and without symptoms, which results in incidence curves as e.g.
shown in Fig. 3 (bottom). Further time series are shown in Figs. S1 and S2.

One should note that the environment characteristic can in principle be used
to scale the incidence curve in time for comparison with a specific disease,
e.g. by decreasing the frequency of the fluctuations. However, as we are
interested in the universal features of the model we do not pursue this line
of investigation here. We have shown that our model, despite its simplicity,
is capable of producing realistic incidence curves (Fig. 3 (bottom)). In the
following, we will now investigate how the different parameters influence the
behaviour of the system.

Whether and how often the time series show a specific case depends on the
choice of parameters. In Fig. 4 we vary the fraction of active inputs $I$ and
analyze for 1000 steps how often a specific case was reached. The same plots
for other parameter combinations are presented in Figs. S3 and S4. For a high
fraction of AND gates ($a>0.5$) the healthy network is already very sensitive
and often shows zero output if only a few input elements are deactivated
(frequent occurrence of case D). These sensitive systems become more robust,
if the connectivity between the pathways is decreased. This dependence stems
from the fact that low connectivity is likely to isolate the consequences of a
genetic defect, by restricting it to very few pathways, or even a single one.
In the special case of $b=0$, the system is just a collection of independent
single pathways. In such a case the parameter $a$ does not have an effect and
the output is always the same as the input. In contrast, for a large number of
OR gates ($a<0.5$), there is a high chance that the healthy, as well as the
defect system, have non-zero output. Within this regime, for high branching
$b>0.5$ the outputs of both systems are likely to be equal because a
deactivated pathway gets healed by neighbouring pathways as depicted in Fig.
1c. For low branching $b<0.5$ the defect network often shows symptoms.
Depending on the proportion of AND and OR gates the disease network hence has
an advantage if either the branching is high or low. The figures also allow
for another observation: For a high number of active inputs there are –
depending on the disease – mainly two possibilities: Either the system stays
in case A (the healthy and the disease network show the same output), or it
stays in case B (the disease network shows lower output). If the fraction of
active inputs is decreased, it is also possible (as e.g. observed in Fig. 3
(top)) that the time series switches between cases A and B. We can identify
these outcomes with two different disease conditions: If the system stays in
case B this corresponds to a chronic disease where a lower output persists.
Contrarily, if we observe a switching between A and B, this corresponds to
diseases observed as acute.

Figure 4:  Dependence of the observed cases on the fraction of active inputs
$I$. For each parameter combination, the system was simulated 100 times for
1000 time steps. The colour code (as defined in Fig. 1a) indicates, which
cases occurred in the time line. Here, Cx and Dx denote that the time line
also contained the cases (A, B) or (A, B, C), respectively. Curves for other
sets of parameters are provided in Figs. S3 and S4.

Besides the general dependence on the choice of parameters, it is particularly
interesting to analyze, how the position of the disease nodes (within the
network) affects the visibility of the disease. Fig 5 compares the possible
outcomes of the network depending on the average location $\lambda$ of the
disease-associated nodes as well on the fraction of ANDs $a$ and the branching
parameter $b$ (Further results for different sets of parameters are presented
in Figs. S5 and S6).

For small $a$ we observe a strong dependence on the average location of the
disease: If the average location is close to the input, the symptoms are often
not visible and the output of the healthy and disease-affected network are
equal (green, case A). Contrarily, if the average location is close to the
output, the defect network has often less activity than the healthy network
(the disease is visible; yellow, case B). For large $a$ the model shows
different behaviour. Here, in most cases, both the healthy and the defect
network have zero output (both are dead; black, case D). Additionally, the
behaviour is mostly independent of the position of the non-functional nodes.
We can explain this behaviour with some simple arguments: Let us assume a
single non-functional node at location $k$ in the $j$th pathways. Without any
crosstalk between the pathways, this defect affects all subsequent sites on
position $k+1$, $k+2$, … $L$. Now, if we allow for branching, two mechanisms
need to be taken into account: (1) A signal from a neighbouring pathway ($j-1$
or $j+1$) can arrive and restart one of those affected nodes, which require a
logical OR. (2) Since the transmission and distribution of 1s coming from the
now deactivated pathway disappear, the single deactivated node can deactivate
neighbouring pathways in case of a logical AND. Depending on the fraction of
ANDs (determined by the parameter $a$) a disease affected node can hence
create longer “shadows” of deactivated pathways or it can be circumvented. The
branching determines the speed of these two mechanisms.

Figure 5:  Dependence of the observed cases on the average position $\lambda$
of inactive nodes. The colour code (as defined in Fig. 1 a) indicates, which
cases occurred in the time line. For the upper figure, the clustering
parameter was set to $p=1$ which means that all defective nodes form one
cluster. Contrarily, in the lower figure, the parameter was set to $p=0$,
leading to a random distribution of the defective nodes. Results for other
sets of parameters are provided in Figs. S5 and S6.

### State-space dynamics

The stylized nature of our model also allows for a more stringent and more
comprehensive analysis, which is less based on numerical simulations, but on
formalisms of discrete systems. This direction is pursued in the present
section.

We consider the middle (bulk) segment of the network as an operator
transforming the input vector (environment) into the output vector
(phenotype). As the bulk is a set of consecutive layers, it is possible to
trace the evolution of the input vector, step by step, all the way to the
output. Using a state-space representation then allows us to analyze the
evolution on the scale of the whole state space. With $N$ input nodes (or
parallel pathways) we formally have $2^{N}$ distinct input states. The
corresponding $N$-digit binary numbers are then processed layer by layer. As
this processing is deterministic, a single state at layer $k$ cannot give rise
to multiple states at layer $k+1$. However, multiple states at layer $k$ can
lead to the same state at layer $k+1$. Hence, as already described before, the
diversity of states can only decrease across layers. This ’funnelling’ of
states along the network is instrumental for the functionality of our model.

Figure 6: Detailed view of the state space evolution. Input states (left;
sorted according to the binary number they represent) are converted into
output states (phenotypes; right) by the network. The number of phenotypes is
usually much smaller than the number of possible input states. Green indicates
a trajectory in the healthy network, while orange indicates a trajectory in
the disease network.

The funnelling of binary states is illustrated in Fig. 6, where all possible
initial states are arranged along the y-axis and layers are shown along the
x-axis, thus allowing us to follow all possible input states through the
network. As soon as two lines meet they merge, which decreases the number of
possible states after this time point by one. Formally, in the limit of
infinite time (infinite length of the network) this always leads to a system
where all outputs are either on or off.

### Relation to percolation theory

Biological regulatory networks can be classified as complex dynamical systems,
the analysis of which has a long tradition in statistical physics [49]. The
design of our model allows a specific class of models from physics – directed
percolation(DP) [20, 19] – to be transferred to our system. More specifically,
our model is similar to a subgroup of DP, namely Compact Directed
Percolation[50, 51, 52]. Percolation models are simple models from statistical
physics to analyze signal propagation through heterogeneous systems e.g. cells
or neurons [53, 54]. In most of these models, a single parameter $p$
determines the probability that a signal is locally transmitted. If $p$ is too
small, no signal can reach the output. In this (inactive) phase, the
probability that the signal reaches a specific layer decays exponentially with
the number of layers. Contrarily, if $p$ is large, there is almost always a
connected path through the system and hence a finite probability that the
signal reaches the output. The transition point between these two phases
$p=p_{c}$ is, mathematically speaking, a critical point. At the critical
point, the probability that the signal can traverse the medium decays
algebraically with the number of layers. We can use these results from
statistical physics to understand and interpret the results observed in our
model. An example is Fig. 5 where, from left to right, the fraction of ANDs
was increased. At $a\approx 0.5$, we observe a sudden change in the general
behaviour of the system: For $a\leq 0.5$ most systems show either case A or
case B. However, for $a>0.5$ most systems belong to case D where both systems
show zero output. This transition can be identified as a phase transition
within the genetic disease model.

Another central topic in the analysis of percolation models is their
dependence on small perturbations. The analysis of how a single perturbation
(often also called damage) evolves over time is known as damage spreading
[55]. If one introduces damage and compares the difference to the unmodified
network there are two possible results: The damage can spread, which
ultimately leads to a system that evolves very differently from the original
network, or the damage might disappear. We envision that the analysis of
damage spreading transitions can be an interesting direction for further
research within our disease model.

## Discussion and Conclusion

We presented a minimal model to study the interplay between network topology
and disease nodes. Our model can be used to analyze, how incidence curves and
disease visibility depend on parameters like the clustering of disease genes
or the cross-talk between pathways. The situation considered here is generic
(i.e., not tailored to any specific set of biological processes). The model is
motivated by the general properties of metabolic networks, where the most
obvious type of environmental fluctuation is a change in nutrient
availability. The output vector can be thought of as some type of cellular
objective function (for example growth or energy production) as typically
employed in genome-scale metabolic models, for example for flux-balance
analysis [25]. A design concept of our model is that genetic predisposition
manifests as a loss of function, which is a suitable model, if the signal
processing does not include a logical NOT. Following this choice, we only
employ logical ORs and ANDs. However, if one relaxes these constraints, there
are obviously other possible choices for logical gates e.g. the functionally
complete sets {AND, NOT} or {NOR}.

The conceptual foundation of our model is the basic fact that human diseases
are rarely the consequence of a single defective gene, but the result of
complex interactions within the cellular-molecular network [56]. The disease
phenotype is hence a result of different and mutually dependent interactions.

Although there are successful attempts to identify disease genes, due to the
complexity of medical situations, the typically low signal strength, as well
as the small sizes and high intrinsic diversity of disease cohorts, these
approaches so far often provide limited functional insight. We believe that
minimal, generative models of typical data types, as well as stylized
representations of typical medical scenarios, are necessary to organize the
analysis of the intricate relationship between genetic risk factors,
environmental stimuli and observed disease phenotype. Our model allows
building such an understanding from a general point of view: By the variation
of a few parameters, it is possible to compare the interplay of different
network topologies and disease characteristics. We also show that the specific
pattern of a genetic predisposition of a biological network can have a direct
and systematic impact on the disease phenotype. Such relationships between
genetic defect patterns and phenotype patterns are a direct consequence of the
architecture of the underlying network.

Our model stratifies diseases according to four main model properties: (1)
high or low clustering of affected nodes (representing genetic
predisposition), (2) strong or weak network connectivity (branching), (3) high
or low numbers of ORs (regulatory alternatives) vs. ANDs (regulatory
interactions), and (4) the clustering of affected nodes either proximal to
input layer (representing environment) or proximal to the output layer
(representing network function or phenotype) and thus the average position of
affected nodes.

Based on the detailed analysis of our model, we arrive at the following
picture: High average position, high clustering and high branching facilitate
chronic diseases. The average position of affected nodes does not strongly
affect the probability of acute disease, in contrast to the clustering of
these nodes, which disfavors acute diseases.

Employing mathematical modelling to leverage biological networks – and
signalling networks in particular – for the purpose of understanding human
diseases is a cornerstone of the emerging field of precision medicine [57,
58]. Due to the simple structure of the network, our model allows for an in-
depth and node-by-node analysis of the observed results. The model can hence
be used to assess the robustness and vulnerability – common topics in Systems
Biology [59, 60] – of phenotypic states from a functional point of view.

## Appendix: Evaluation of the parameter $a$

In order to provide some intuition on the range of values for the percentage
$a$ of logical ANDs – which is one of the key parameters of our model – we
resort to genome-scale metabolic models. Here we employ two strategies to
estimate the value of $a$ from such metabolic reconstructions.

The first method counts the Boolean operations in the gene-to-reaction
mappings within genome-scale metabolic models and computes the ratio

$a=\textrm{AND}/(\textrm{AND}+\textrm{OR}).$ (1)

This yields – depending on the model – $a$ between $0.105$ and $0.15$ (see
Table 1). The analysis was performed with the COBRA package for Python (Cobra
version 0.19.0; Python version 3.6).

Table 1:  Estimation results for the parameter $a$ for three genome-scale
metabolic models of human cells, Recon 1 [61], Recon 2 [62] and Recon 3D [63].
Estimation of $a$
---
Method |  Recon 1 |  Recon 2.3 |  Recon 3D
1 (gene-reaction associations) |  0.15 |  0.129 |  0.105
2 (complex reactions) |  0.24 |  0.08 |  0.21

The second method evaluates each (reaction) node together with its next-to-
nearest neighbours. In this sense, the method is closer to the nature of nodes
in our model, which do not represent individual reactions, but rather more
complex regulatory entities, summarizing metabolic flow and genetic control.
Such subgraph objects may behave like AND or OR gate depending on the mutual
proportions of the alternative sources and the number of reactants.

This method utilizes information about reaction network including their
directionality. Each reaction has a form of $R_{1}+R_{2}+...\rightarrow
P_{1}+P_{2}+...$, where $R_{i}$ are reactants and $P_{j}$ products. Our
quantification focuses on reactants alone. Each reactant may have one or more
possible sources, where the number of these sources for each reactant is
$k_{i}$. Hence, the reaction itself corresponds to a Boolean AND, but
alternative sourcing is an analogue of a Boolean OR. Such a subgraph has the
structure of multiple logical ORs fed to an single logical AND:
$(R_{1,1}|R_{1,2}|...)+(R_{2,1}|R_{2,2}|...)+...\rightarrow P_{1}+P_{2}+...$.
In order to estimate the parameter $a$, we need to convert this whole entity
to just a single AND or OR.

All fluxes are regarded to be discrete, hence inputs can be characterized by a
probability $c_{in}$ of having reactant $i$ from the source $j$, $R_{i,j}$.
With this quantity, the probability of reaction taking place, $c_{out}$, can
be computed. For a logical AND $c_{out}<c_{in}$ whereas for a logical OR
$c_{out}>c_{in}$, there are also special cases of $c_{in}=0$ and $c_{in}=1$.
The same classification can be done for more complicated structures, like the
one discussed above. For simple gates, there is always (for each $c_{in}$)
either $c_{out}<c_{in}$ or $c_{out}<c_{in}$ depending on the gate. However,
for more complicated entities this inequality may change sign upon change of
$c_{in}$. Way to overcome this difficulty is to compare whole range of
$c_{in}\in[0,1]$ by taking integral and then comparing:

$\displaystyle c_{out}$ $\displaystyle=$
$\displaystyle\prod_{i}(1-(1-c_{in})^{k_{i}})$ (2) $\displaystyle\Delta_{c}$
$\displaystyle=$ $\displaystyle c_{out}-c_{in}$ (3) $\displaystyle\alpha$
$\displaystyle=$
$\displaystyle\int_{0}^{1}\Delta_{c}dc_{in}=\int_{0}^{1}\left(\prod_{i}(1-(1-c_{in})^{k_{i}})-c_{in}\right)dc_{in},$
(4)

where $i$ is the metabolite index and $k_{i}$ is the number of alternative
sources for this metabolite. Reactions with empty sets of sources were removed
from the analysis.

Then if $\alpha>0$ node is regarded as OR, in the case of $\alpha<0$ node is
AND. The value of $a$ obtained with this method is between 0.08 and 0.24 for
human metabolic models (see Table 1). These values are clearly located in the
subcritical regime. This is in line with our model results, which show that
only the subcritical regime is viable and resilient to defect and
perturbations.

We also checked metabolic models for other living organisms and we found
substantial agreement between the values of $a$. This is a suitable starting
point for further investigation. Also, the precise determination of this
parameter deserves a more detailed study.

## Author contributions

MH and PN conceived this study. PN and JF performed numerical investigations.
MH, PN and JF wrote the manuscript.

## References

  * [1] Merskey, H.  Variable meanings for the definition of disease.  _The Journal of Medicine and Philosophy_ 11, 215–232 (1986).
  * [2] Margolis, J.  Thoughts on definitions of disease.  _The Journal of Medicine and Philosophy_ 11, 233–236 (1986).
  * [3] Cooper, R.  Disease.  _Studies in History and Philosophy of Science Part C_ 33, 263–282 (2002).
  * [4] Ereshefsky, M.  Defining ‘health’ and ‘disease’.  _Studies in History and Philosophy of Science Part C_ 40, 221–227 (2009).
  * [5] Pearce, J.  Disease, diagnosis or syndrome?  _Practical Neurology_ 11, 91–97 (2011).
  * [6] Haendel, M. A. _et al._ A census of disease ontologies.  _Annual Review of Biomedical Data Science_ 1, 305–331 (2018).
  * [7] Harrow, I. _et al._ Matching disease and phenotype ontologies in the ontology alignment evaluation initiative.  _Journal of Biomedical Semantics_ 8, 1–13 (2017).
  * [8] Nordling, C.  A new theory on the cancer-inducing mechanism.  _British Journal of Cancer_ 7, 68 (1953).
  * [9] Armitage, P., Doll, R. _et al._ The age distribution of cancer and a multi-stage theory of carcinogenesis.  _British Journal of Cancer_ 8, 1–12 (1954).
  * [10] Rozhok, A. I. & DeGregori, J.  Toward an evolutionary model of cancer: Considering the mechanisms that govern the fate of somatic mutations.  _PNAS_ 112, 8914–8921 (2015).
  * [11] Rozhok, A. & DeGregori, J.  A generalized theory of age-dependent carcinogenesis.  _Elife_ 8, e39950 (2019).
  * [12] Hochberg, M. E. & Noble, R. J.  A framework for how environment contributes to cancer risk.  _Ecology Letters_ 20, 117–134 (2017).
  * [13] Liu, C. _et al._ Computational network biology: data, models, and applications.  _Physics Reports_ 846, 1–66 (2020).
  * [14] Victor, J.-M. _et al._ Network modeling of Crohn’s disease incidence.  _PloS One_ 11, e0156138 (2016).
  * [15] Knecht, C., Fretter, C., Rosenstiel, P., Krawczak, M. & Hütt, M.-T.  Distinct metabolic network states manifest in the gene expression profiles of pediatric inflammatory bowel disease patients and controls.  _Scientific Reports_ 6, 1–11 (2016).
  * [16] Bauer, C. R. _et al._ Interdisciplinary approach towards a systems medicine toolbox using the example of inflammatory diseases.  _Briefings in Bioinformatics_ 18, 479–487 (2017).
  * [17] Häsler, R. _et al._ Uncoupling of mucosal gene regulation, mRNA splicing and adherent microbiota signatures in inflammatory bowel disease.  _Gut_ 66, 2087–2097 (2017).
  * [18] Fiocchi, C. & Iliopoulos, D.  IBD Systems Biology Is Here to Stay.  _Inflammatory Bowel Diseases_ 27, 760–770 (2021).
  * [19] Broadbent, S. R. & Hammersley, J. M.  Percolation processes: I. Crystals and mazes.  _Mathematical Proceedings of the Cambridge Philosophical Society_ 53, 629–641 (1957).
  * [20] Hinrichsen, H.  Nonequilibrium Critical Phenomena and Phase Transitions into Absorbing States.  _Advances in Physics_ 49, 815–958 (2000).
  * [21] Hinrichsen, H.  On possible experimental realizations of directed percolation.  _Brazilian Journal of Physics_ 30, 69–82 (2000).
  * [22] Terzer, M., Maynard, N. D., Covert, M. W. & Stelling, J.  Genome-scale metabolic networks.  _Wiley Interdisciplinary Reviews: Systems Biology and Medicine_ 1, 285–297 (2009).
  * [23] O’Brien, E. J., Monk, J. M. & Palsson, B. O.  Using genome-scale models to predict biological capabilities.  _Cell_ 161, 971–987 (2015).
  * [24] Kauffman, K. J., Prakash, P. & Edwards, J. S.  Advances in flux balance analysis.  _Current Opinion in Biotechnology_ 14, 491–496 (2003).
  * [25] Orth, J. D., Thiele, I. & Palsson, B. Ø.  What is flux balance analysis?  _Nature Biotechnology_ 28, 245–248 (2010).
  * [26] Kauffman, S. A.  Metabolic stability and epigenesis in randomly constructed genetic nets.  _Journal of Theoretical Biology_ 22, 437–467 (1969).
  * [27] Bornholdt, S.  Less is more in modeling large genetic networks.  _Science_ 310, 449–451 (2005).
  * [28] Radde, N. E. & Hütt, M.-T.  The physics behind systems biology.  _EPJ Nonlinear Biomedical Physics_ 4, 7 (2016).
  * [29] Sneppen, K.  Models of life: epigenetics, diversity and cycles.  _Reports on Progress in Physics_ 80, 042601 (2017).
  * [30] Barabási, A.-L., Gulbahce, N. & Loscalzo, J.  Network Medicine: A Network-based Approach to Human Disease.  _Nature Reviews Genetics_ 12, 56–68 (2011).
  * [31] Goh, K.-I. _et al._ The human disease network.  _PNAS_ 104, 8685–8690 (2007).
  * [32] Alon, U.  Network motifs: Theory and experimental approaches.  _Nature Reviews Genetics_ 8, 450–461 (2007).
  * [33] Doncic, A. & Skotheim, J. M.  Feedforward Regulation Ensures Stability and Rapid Reversibility of a Cellular State.  _Molecular Cell_ 50, 856–868 (2013).
  * [34] Varma, A. & Palsson, B. O.  Metabolic Flux Balancing: Basic Concepts, Scientific and Practical Use.  _Bio/Technology_ 12, 994–998 (1994).
  * [35] Katoh, M. & Katoh, M.  WNT Signaling Pathway and Stem Cell Signaling Network: Fig. 1.  _Clinical Cancer Research_ 13, 4042–4045 (2007).
  * [36] Gupta, S., Bisht, S. S., Kukreti, R., Jain, S. & Brahmachari, S. K.  Boolean network analysis of a neurotransmitter signaling pathway.  _Journal of Theoretical Biology_ 244, 463–469 (2007).
  * [37] Vazquez, A., Flammini, A., Maritan, A. & Vespignani, A.  Global protein function prediction from protein-protein interaction networks.  _Nature Biotechnology_ 21, 697–700 (2003).
  * [38] Vázquez, A., Flammini, A., Maritan, A. & Vespignani, A.  Modeling of Protein Interaction Networks.  _Complexus_ 1, 38–44 (2003).
  * [39] Christensen, B. & Nielsen, J.  Metabolic Network Analysis.  _Bioanalysis and Biosensors for Bioprocess Monitoring_ 209–231 (1999).
  * [40] Sung, J. _et al._ Global metabolic interaction network of the human gut microbiota for context-specific community-scale analysis.  _Nature Communications_ 8, 15393 (2017).
  * [41] Grimbs, A., Klosik, D. F., Bornholdt, S. & Hütt, M.-T.  A system-wide network reconstruction of gene regulation and metabolism in Escherichia coli.  _PLOS Computational Biology_ 15, e1006962 (2019).
  * [42] Klosik, D. F., Grimbs, A., Bornholdt, S. & Hütt, M.-T.  The interdependent network of gene regulation and metabolism is robust where it needs to be.  _Nature Communications_ 8, 534 (2017).
  * [43] Sonnenschein, N., Geertz, M., Muskhelishvili, G. & Hütt, M.-T.  Analog regulation of metabolic demand.  _BMC Systems Biology_ 5, 40 (2011).
  * [44] Falk, J., Mendler, M. & Drossel, B.  A minimal model of burst-noise induced bistability.  _PLoS One_ 12, e0176410 (2017).
  * [45] Kosmidis, K. & Hütt, M.-T.  A minimal model for gene expression dynamics of bacterial type II toxin–antitoxin systems.  _Scientific Reports_ 11, 19516 (2021).
  * [46] Eden, M.  A Two-dimensional Growth Process.  _Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 4: Contributions to Biology and Problems of Medicine_ 4.4, 223–240 (1961).
  * [47] Lambiotte, R. & Rosvall, M.  Ranking and clustering of nodes in networks with smart teleportation.  _Physical Review E_ 85, 056107 (2012).
  * [48] Nyczka, P., Hütt, M.-T. & Lesne, A.  Inferring pattern generators on networks.  _Physica A: Statistical Mechanics and its Applications_ 566, 125631 (2021).
  * [49] Ladyman, J., Lambert, J. & Wiesner, K.  What is a complex system?  _European Journal for Philosophy of Science_ 3, 33–67 (2013).
  * [50] Essam, J. W.  Directed compact percolation: Cluster size and hyperscaling.  _Journal of Physics A: Mathematical and General_ 22, 4927–4937 (1989).
  * [51] Domany, E. & Kinzel, W.  Equivalence of Cellular Automata to Ising Models and Directed Percolation.  _Physical Review Letters_ 53, 311–314 (1984).
  * [52] Duarte, J. A. M. S.  Series and Monte Carlo studies of 2 and 3 dimensions for axial hyperscaling in directed percolation.  _Physica A: Statistical Mechanics and its Applications_ 189, 43–59 (1992).
  * [53] Larkin, J. W. _et al._ Signal Percolation within a Bacterial Community.  _Cell Systems_ 7, 137–145.e3 (2018).
  * [54] Zhou, D. W., Mowrey, D. D., Tang, P. & Xu, Y.  Percolation Model of Sensory Transmission and Loss of Consciousness Under General Anesthesia.  _Physical Review Letters_ 115, 108103 (2015).
  * [55] Herrmann, H. J.  Damage spreading.  _Physica A: Statistical Mechanics and its Applications_ 168, 516–528 (1990).
  * [56] Barabási, A.-L., Gulbahce, N. & Loscalzo, J.  Network Medicine: A Network-based Approach to Human Disease.  _Nature reviews. Genetics_ 12, 56–68 (2011).
  * [57] Yadav, A., Vidal, M. & Luck, K.  Precision medicine - networks to the rescue.  _Current Opinion in Biotechnology_ 63, 177–189 (2020).
  * [58] Hastings, J. F., O’Donnell, Y. E., Fey, D. & Croucher, D. R.  Applications of personalised signalling network models in precision oncology.  _Pharmacology & Therapeutics_ 212, 107555 (2020).
  * [59] Kitano, H.  Computational systems biology.  _Nature_ 420, 206–210 (2002).
  * [60] Kitano, H.  Systems Biology: A Brief Overview.  _Science_ 295, 1662–1664 (2002).
  * [61] Duarte, N. C. _et al._ Global reconstruction of the human metabolic network based on genomic and bibliomic data.  _PNAS_ 104, 1777–1782 (2007).
  * [62] Thiele, I. _et al._ A community-driven global reconstruction of human metabolism.  _Nature Biotechnology_ 31, 419–425 (2013).
  * [63] Brunk, E. _et al._ Recon3D enables a three-dimensional view of gene variation in human metabolism.  _Nature Biotechnology_ 36, 272–281 (2018).

## Supplementary information

Figure S1:  Three examples of possible time trajectories. From top to bottom:
A, AB and B (colour code as defined in Fig.1). Note, that the model parameters
are equal. Hence, the differences in the observed disease depend only on the
particular realization. Other parameters: $L=10,H=20$.

Figure S2:  Three examples of possible time trajectories. From top to bottom:
AD, ABD, ABCD (colour code as defined in Fig.1). Other parameters: $L=20$,
$H=20$.

Figure S3:  Dependence of the observed cases on the fraction of active inputs
$I$. For each parameter combination, the system was simulated 100 times for
1000 time steps. The colour code (as defined in Fig. 1 a) indicates which
cases occurred in the time line.

Figure S4:  Dependence of the observed cases on the fraction of active inputs
$I$. For each parameter combination, the system was simulated 100 times for
1000 time steps. The colour code (as defined in Fig. 1 a) indicates which
cases occurred in the time line.

Figure S5:  Dependence of the observed cases on the average position $\lambda$
of inactive nodes. The colour code (as defined in Fig. 1 a) indicates which
cases occurred in the time line.

Figure S6:  Dependence of the observed cases on the average position $\lambda$
of inactive nodes. The colour code (as defined in Fig. 1 a) indicates which
cases occurred in the time line.


# Incidences with Pfaffian Curves and Functions

Alex Balsera Newark Academy, NJ, USA<EMAIL_ADDRESS>
###### Abstract

We introduce a new approach for studying incidences with non-algebraic curves
in the plane. This approach is based on the concepts of Pfaffian curves and
Pfaffian functions, as defined by Khovanskiĭ. We derive incidence bounds for
curves that are defined with exponentials, logarithms, trigonometric
functions, integration, and more. Our bound for incidences with Pfaffian
curves matches a classical bound of Pach and Sharir for incidences with
algebraic curves, up to polylogarithmic factors.

##  1 Introduction

Over the past 25 years, researchers discovered a surprising number of
applications for point-curve incidence bounds in $\mathbb{R}^{2}$. Beyond
being highly useful in combinatorial proofs, such incidence bounds are also
used in number theory, harmonic analysis, theoretical computer science, and
more. For a few examples, see [3, 4, 6, 9].

Traditionally, research of incidence bounds focused on algebraic curves —
curves defined by a polynomial in the plane coordinates $x,y$. For example,
circles are defined by equations of the form $(x-p)^{2}+(y-q)^{2}=r^{2}$. In
the past decade, the rising popularity of incidence bounds led to the study of
more incidence variants. Model theorists now study incidences in more general
models such as Distal and $o$-minimal structures. For example, see [1, 2, 5].

In the current work, we introduce a new approach for incidence bounds with
non-algebraic curves. We study _Pfaffian curves_ and _Pfaffian functions_ , as
introduced and studied by Khovanskiĭ [10]. Pfaffian curves include all
algebraic curves, while also allowing some use of trigonometric functions,
exponents, logarithms, inverse trigonometric functions, and more. For example,
the curves defined by $y=\tan x$ and $y=e^{x^{2}-5x+3}$ are Pfaffian.

Confusingly, curves that are defined by Pfaffian functions are not the same as
Pfaffian curves. Pfaffian functions are more general than Pfaffian curves,
allowing any combination of elementary mathematical functions, and beyond.
(Sines and cosines are limited to an open region of $\mathbb{R}^{2}$ where
they have a bounded number of periods.) For example, the function
$e^{\tan^{3/2}x}\cdot\log y=x^{\arctan xy}$ is Pfaffian. Pfaffian functions
also allow some use of integration. For example, we may consider functions
such as $y-\int_{0}^{x}\frac{dt}{\ln t}$ and
$y-\int_{-\infty}^{x}\frac{e^{t}}{t}dt$. For rigorous definitions, more
examples, and intuition, see Section 2.

Background. Consider a point set $\mathcal{P}$ and a set of curves111For
rigorous definitions of curves and other concepts, see Section 2. $\Gamma$,
both in $\mathbb{R}^{2}$. An _incidence_ is a pair
$(p,\gamma)\in\mathcal{P}\times\Gamma$ where the point $p$ is on the curve
$\gamma$. For example, the left part of Figure 1 contains four points, five
curves, and 13 incidences. The _incidence graph_ is a bipartite graph with
vertex sets $\mathcal{P}$ and $\Gamma$. There is an edge between the vertex of
a point $p\in\mathcal{P}$ and the vertex of a curve $\gamma\in\Gamma$ if
$p\in\gamma$. Figure 1 includes an incidence graph on the right.

Figure 1: Left: Four points, five curves, and 13 incidences. Right: The
incidence graph.

We denote the number of incidences in $\mathcal{P}\times\Gamma$ as
$I(\mathcal{P},\Gamma)$. The following theorem is a classic incidence result
of Pach and Sharir [12]. For a more recent variant, see Sharir and Zahl [13].
The degree of an algebraic curve is the minimum degree of a polynomial that
defines it.

######  Theorem 1.1.

Consider a set $\mathcal{P}$ of $m$ points and a set $\Gamma$ of $n$ algebraic
curves of degree at most $k$, both in $\mathbb{R}^{2}$. If the incidence graph
of $\mathcal{P}$ and $\Gamma$ contains no copy of $K_{s,t}$ then222In
$O_{k,s,t}$, the constant hidden by the $O(\cdot)$-notation may depend on
$k,s,t$.

$I(\mathcal{P},\Gamma)=O_{k,s,t}(m^{\frac{s}{2s-1}}n^{\frac{2s-2}{2s-1}}+n+m).$

Since two lines share at most one point, the incidence graph of points and
lines contains no $K_{2,2}$. Thus, Theorem 1.1 implies that the number of
incidences between $m$ points and $n$ lines is $O(m^{2/3}n^{2/3}+m+n)$. The
same bound holds when replacing the lines with circles of radius 1, since in
that case the incidence graph contains no $K_{2,3}$. For general circles, the
number of circles that contain two given points may be arbitrarily large, but
the incidence graph contain no $K_{3,2}$.

The bound of Theorem 1.1 consists of three terms. The term $m$ dominates the
bound when the number of points is significantly larger than the number of
lines, and symmetrically for the term $n$. For example, in the case of lines
the term $m$ dominates when the number of points is more than the square of
the number of lines. These are considered less interesting cases. Thus, the
main term of the bound is $m^{\frac{s}{2s-1}}n^{\frac{2s-2}{2s-1}}$.

Our results. For incidences with Pfaffian curves, we obtain an upper bound
that matches Theorem 1.1, up to additional polylogarithmic factors.

######  Theorem 1.2.

Let $\mathcal{P}$ be a set of $m$ points and let $\Gamma$ be a set of $n$
Pfaffian curves of degree at most $k$, both in $\mathbb{R}^{2}$. If the
incidence graph of $\mathcal{P}$ and $\Gamma$ contains no copy of $K_{s,t}$
then

$I(\mathcal{P},\Gamma)=O_{k,s,t}\left(m^{\frac{s}{2s-1}}n^{\frac{2s-2}{2s-1}}\log^{\frac{2s-2}{2s-1}}n+n\log^{2}n+m\right).$

Recent incidence results are commonly proved by using the _polynomial
partitioning_ technique (for example, see [14, Chapter 3]). So far, we were
not able to use this technique with Pfaffian curves. Instead, we rely on the
older _cutting_ technique. The additional polylogarimthic factors appear
because we use a simplified variant of a cutting.

Our incidence bound for curves that are defined by Pfaffian functions is
weaker than the bound for Pfaffian curves. This is not surprising, since such
curves are significantly more general. Recall that the _elementary functions_
are the functions obtained by taking sums, products, roots, and compositions
of finitely many polynomial, rational, trigonometric, hyperbolic, and
exponential functions, including their inverses, such as arcsines and
logarithms. Similarly, _Liouvillian functions_ are the univariate elementary
functions and their repeated integrals. Bivariate Pfaffian functions subsume
all bivariate elementary functions and all functions of the form $y=f(x)$ with
a Liouvillian $f$. Section 2 includes the rigorous definitions and more
intuition.

We define a _Pfaffian family_ $F$ using an open subset
$U\subseteq\mathbb{R}^{2}$ and a Pfaffian function of the form

$f(x,y)=a_{1}\cdot m_{1}(x,y)+a_{2}\cdot m_{2}(x,y)+\cdots+a_{d}\cdot
m_{d}(x,y).$

Here, each $a_{i}$ is a real parameter and each $m_{i}(x,y)$ is a Pfaffian
function that is a single term (such as a monomial). The family $F$ consists
of all curves in $U$ that are defined by $f(x,y)=0$ with some choice of values
for $a_{1},\ldots,a_{d}\in\mathbb{R}$. That is, a Pfaffian family is a set of
infinitely many curves. For example, when $U=\mathbb{R}^{2}$ and
$f(x,y)=a_{1}\sqrt{e^{x-y^{2}}}+a_{2}\tan\ln(x^{y})+a_{3}\int_{-\infty}^{x}\frac{e^{t}}{t}dt$,
the family includes the curves defined by $\tan\ln(x^{y})=0$, by
$100\sqrt{e^{x-y^{2}}}-\tan\ln(x^{y})-\frac{1}{100}\int_{-\infty}^{x}\frac{e^{t}}{t}dt=0$,
and by $10^{100}\sqrt{e^{x-y^{2}}}+10^{-100}\tan\ln(x^{y})=0$.

The _dimension_ of a Pfaffian family is the number of parameters $d$. We are
now ready to describe our incidence bound for curves defined by Pfaffian
functions.

######  Theorem 1.3.

Let $F$ be a Pfaffian family of dimension $d$. Let $\mathcal{P}$ be a set of
$m$ points in $\mathbb{R}^{2}$. Let $\Gamma$ be a set of $n$ curves from $F$,
such that no two share a common component. Then, for any ${\varepsilon}>0$, we
have that

$I(\mathcal{P},\Gamma)=O_{d,{\varepsilon}}\left(n^{\frac{2d-4}{2d-3}+{\varepsilon}}m^{\frac{d-1}{2d-3}}+m+n\right).$

The constant hidden by the $O(\cdot)$-notation in the bound of Theorem 1.3
also depends on the degree and order of the Pfaffian function that defines
$F$. Since these values do not affect the dependency of the bound in $m$ and
$n$, we do not explicitly refer to them, to keep the statement of the theorem
simple.

Pfaffian curves include all algebraic curves with no singular points, and
Pfaffian functions define all algebraic curves. Thus, every lower bound
construction for algebraic curves also holds in our case. We can also use an
algebraic configuration with many incidences to obtain many incidences with
non-algebraic curves. For example, we can start with a point–line
configuration with $\Theta(m^{2/3}n^{2/3})$ incidences and apply the
transformation $(x,y)\to(e^{x},y)$. This leads to a configuration of points
and exponential functions with $\Theta(m^{2/3}n^{2/3})$ incidences. So far, we
did not find constructions with a larger number of incidences than currently
known for algebraic curves. (Ignoring trivial cases, such as curves that
intersect infinitely many times.) It would be interesting to know if such
configurations exist.

Section 2 is an introduction to Pfaffian curves and functions. In Section 3 we
prove our incidence result for Pfaffian curves. In Section 4 we prove our
incidence result for curves defined by Pfaffian functions.

Future work. The current work can be seen as a modest first step of an
algebraic approach to studying incidences with non-algebraic curves. It leads
to many questions. A few of those:

  * •

Can we improve the bounds of Theorem 1.1 or Theorem 1.3?

  * •

Are there constructions with Pfaffian curves or functions with more incidences
than the known constructions of algebraic curves?

  * •

Can we revise the concept of a Pfaffian family to obtain more general
incidence bounds with curves defined by Pfaffian functions? That is, can we
use parameters in a more general way than for the coefficients of a fixed set
of terms?

  * •

Are there other useful incidence models similar to Pfaffian curves and
Pfaffian functions?

Acknowledgements. We thank Moaaz AlQady for inspiring this work. We are
grateful to Saugata Basu and Aaron Anderson for discussions about Khovanskiĭ’s
work and incidences under more general models.

##  2 Pfaffian Curves and Pfaffian functions

In this section, we describe the basic technical definitions that are used in
this paper. For more information, see Khovanskiĭ [10].

Pfaffian Curves. We rely on the topological definition of a _curve_. That is,
a curve consists of a finite number of connected components, and for each
component $C$ there exists a continuous function from a real interval to $C$.

Consider a curve $\gamma\subset\mathbb{R}^{2}$ and an open
$U\subset\mathbb{R}^{2}$, such that $\gamma\cap U$ can be parameterized as
$(f^{(x)}(t),f^{(y)}(t))$. Here, $t\in T$ for an open interval
$T\subset\mathbb{R}$ and $f^{(x)}(t),f^{(y)}$ are differentiable. By the
implicit function theorem, for any curve $\gamma$ that can be expressed using
a continuously differentiable function and any point $p\in\gamma$, there
exists an open set $U$ that contains $p$, such that $\gamma\cap U$ can be
parameterized as above. For a point $p=(f^{(x)}(t_{p}),f^{(x)}(t_{p}))\in U$,
the _directional vector_ of $\gamma$ at $p$ is
$\left(\frac{df^{(x)}}{dt}(t_{p}),\frac{df^{(y)}}{dt}(t_{p})\right)$. For
example, let $\gamma$ be the parabola defined by $y=x^{2}$ and let
$U=\mathbb{R}$. We may set $f_{x}=t$ and $f_{y}=t^{2}$, with $T=\mathbb{R}$.
The directional vector at a point $(f^{(x)}(t_{p}),f^{(y)}(t_{p}))$ is
$(1,2t)$.

Consider an open $U\subset\mathbb{R}^{2}$. A _vector field_
$V:U\to\mathbb{R}^{2}$ assigns a vector to each point in $U$. For a point
$p=(p_{x},p_{y})\in\mathbb{R}^{2}$, we write $V(p)=(V_{x}(p),V_{y}(p))$. For
example, we may consider the vector field $V(p)=(1,2x)$. Note that, with
respect to the parabola from the preceding paragraph, the direction vector at
any $p\in\gamma$ is $V(p)$. See Figure 2(a).

Figure 2: (a) The parabola $y=x^{2}$ and the corresponding vector field
$V(p)=(1,2x)$. (b) An example that does not satisfy the third condition of a
separating solution. When traveling along the upper component, the middle cell
is to our right. When traveling along the bottom component, the middle cell is
to our left. (c) The issue from part (b) is resolved.

A vector field $V$ is _polynomial_ if both $V_{x}(p)$ and $V_{y}(p)$ are
polynomials in the coordinates of $p$. The degree of a polynomial vector field
is the larger of the degrees of $V_{x}(p)$ and $V_{y}(p)$.

Consider an open $U\subset\mathbb{R}^{2}$ and a vector field
$V:U\to\mathbb{R}^{2}$. A curve $\gamma\subset U$ is a _separating solution_
of $V$ if it satisfies:

  1. (i)

There exists a parameterization of $\gamma$ such that, at every point
$p\in\gamma$, the directional vector of $\gamma$ at $p$ is $V(p)$.

  2. (ii)

Every $p\in\gamma$ satisfies that $V(p)\neq(0,0)$.

  3. (iii)

For every connected component $\gamma_{i}$ of $\gamma$, the set
$U\setminus\gamma_{i}$ is not connected. For each connected component $C$ of
$U\setminus\gamma$, when traveling along $\gamma$ in the direction of $V$,
either $C$ is always to the right, or always to the left. See Figure 2(b) and
Figure 2(c).

We say that a curve $\gamma$ is _Pfaffian_ if it is a separating solution of a
polynomial vector field. The _Pfaffian degree_ of $\gamma$ is the minimum
degree of a polynomial vector field that corresponds to $\gamma$. For an
algebraic curve, the Pfaffian degree may not equal the standard algebraic
degree. By definition, the directional vector of $\gamma$ also consists of
polynomials.

Every algebraic curve with no singular points is a Pfaffian curve. An open
continuous subset of an algebraic curve with no singular points is a Pfaffian
curve in an appropriate open subset of $\mathbb{R}^{2}$. A few other examples
of Pfaffian curves:

  * •

The curve $y=\tan x$ corresponds to the parameterization $(t,\tan t)$ and
vector field $(1,1+y^{2})$. Indeed, the derivative of $\tan t$ is
$\sec^{2}t=1+\tan^{2}t$. The open interval $T$ depends on the period of
$y=\tan x$ that we are interested in.

  * •

The curve $y=\arctan x$ corresponds to the parameterization $(\tan t,t)$ and
vector field $(1+x^{2},1)$.

  * •

The curve $y=e^{x}$ corresponds to the parameterization $(t,e^{t})$ and vector
field $(1,y)$.

  * •

The curve $y=\ln(x)$ corresponds to the parameterization $(e^{t},t)$ and
vector field $(x,1)$. In this case, $T=(0,\infty)$.

  * •

The curve $y=1/x$ corresponds to the parameterization $(t,1/t)$ and vector
field $(1,-y^{2})$. In this case, $T=(0,\infty)$ or $T=(-\infty,0)$.

  * •

The curve $y=1/x^{1/k}$ with $k\in\mathbb{N}$ is Pfaffian, but it is difficult
to show that with the straightforward parameterization $(t,t^{-1/k})$.
Instead, we can use the parameterization $(e^{t},e^{-t/k})$ and vector field
$(x,-y/k)$.

  * •

All above examples are of the form $y=f(x)$, since these are the simplest
cases. For a different example, consider the circle $(\cos t,\sin t)$ with
$T=(0,2\pi)$. This corresponds to the vector field $(-y,x)$. (This
parameterization is missing one point of the circle. To be a separating
solution, we need to remove that point from $\mathbb{R}^{2}$.)

The following lemma provides a few examples for building infinite families of
Pfaffian curves.

######  Lemma 2.1.

Consider a Pfaffian curve $\gamma$ that is parameterized as
$(f^{(x)}(t),f^{(y)}(t))$ and with vector field $V(p)=(V_{x}(p),V_{y}(p))$.
(a) Applying an invertible linear transformation on $\gamma$ leads to a
Pfaffian curve.
(b) Assume that $f^{(x)}(t)=t$ and that
$\frac{df^{(y)}}{dt}\in\mathbb{R}[f^{(y)}]$ (the derivative can be expressed
as a polynomial in $f^{(y)}$). Then, for any $p\in\mathbb{R}[x]$, the curve
defined by $y=f^{(y)}\circ p$ is Pfaffian.

For any polynomial $p\in\mathbb{R}[t]$, Lemma 2.1(b) implies that $y=e^{p(x)}$
and $y=1/p(t)$ are Pfaffian. These are only a few examples of methods for
creating Pfaffian curves. It is not difficult to come up with variants and
generalizations of Lemma 2.1.333For example, the condition
$\frac{df^{(y)}}{dt}\in\mathbb{R}[f^{(y)}]$ in part (b) can be replaced by
$\frac{df^{(y)}}{dt}=f^{(y)}\cdot q$ with $q\in\mathbb{R}[t]$.

###### Proof of Lemma 2.1..

Consider an invertible linear transformation that is defined by the matrix

$A=\begin{bmatrix}a_{1},a_{2}\\\ a_{3},a_{4}\end{bmatrix},\quad\text{ with
}a_{1},a_{2},a_{3},a_{4}\in\mathbb{R}.$

Applying the transformation $A$ on $\gamma$ leads to the curve

$A\cdot(f^{(x)}(t),f^{(y)}(t))=\begin{bmatrix}a_{1}\cdot f^{(x)}(t)+a_{2}\cdot
f^{(y)}(t)\\\ a_{3}\cdot f^{(x)}(t)+a_{4}\cdot f^{(y)}(t)\end{bmatrix}.$

The corresponding directional vector is $\big{(}d(a_{1}\cdot
f^{(x)}(t)+a_{2}\cdot f^{(y)}(t))/dt,d(a_{3}\cdot f^{(x)}(t)+a_{4}\cdot
f^{(y)}(t))/dt\big{)}$. Thus, $A\cdot\gamma$ has a polynomial vector field. It
is not difficult to verify that $A\cdot\gamma$ satisfies properties (ii) and
(iii) of a separating solution (possibly in a smaller open set $U$).

(b) We denote the curve defined by $y=f^{(y)}\circ p$ as $\gamma^{\prime}$. We
observe that $\gamma$ is piece of a graph (intersecting every vertical line
once, in some interval of $x$-coordinates). This implies that
$\gamma^{\prime}$ is also a graph, possibly in a smaller interval. Thus,
$\gamma^{\prime}$ is a separating solution, possibly in a smaller open subset
than the one corresponding to $\gamma$.

We note that

$\frac{df^{(y)}\circ p}{dt}=\left(\frac{df^{(y)}}{dt}\circ
p\right)\cdot\frac{dp}{dt}.$

Since $p\in\mathbb{R}[t]$ and $\frac{df^{(y)}}{dt}\in\mathbb{R}[f^{(y)}]$, the
above derivative is in $\mathbb{R}[t,f^{(y)}\circ p]$, as required. ∎

We now recall Bezout’s theorem (for example, see [8, Section 14.4]).

######  Theorem 2.2.

Let $f$ and $g$ be nonzero polynomials in $R[x,y]$ of degrees $k_{f}$ and
$k_{g}$, respectively. If $f$ and $g$ do not have common factors, then these
two curves intersect in at most $k_{f}\cdot k_{g}$ points.

Khovanskiĭ proved an analogue of Bezout’s Theorem for Pfaffian curves.

######  Theorem 2.3.

Let $\gamma_{1},\gamma_{2}\subset\mathbb{R}^{2}$ be Pfaffian curves of
Pfaffian degrees $k_{1}$ and $k_{2}$, respectively. If $\gamma_{1}$ and
$\gamma_{2}$ do not have a common component, then they intersect in at most
$(k_{1}+k_{2})(2k_{1}+k_{2})+k_{1}+1$ points.

We also require the following property of Pfaffian curves.

######  Lemma 2.4.

Let $\gamma$ be a Pfaffian curve of Pfaffian degree $k$ that is not a segment
of a vertical line. Then the directional vector of $\gamma$ is vertical in
$O(k^{2})$ points.

###### Proof.

Let $\gamma$ be parameterized as $(f^{(x)}(t),f^{(y)}(t))$ and with vector
field $V(p)=(V_{x}(p),V_{y}(p))$. We note that $\gamma$ has a vertical tangent
at a point $p\in\mathbb{R}^{2}$ if $V_{x}(p)=0$. By definition, $V_{x}$ is a
polynomial of degree at most $k$. Since $\gamma$ is not a segment of a
vertical line, $\gamma$ and the curve defined by $V_{x}(p)=0$ do not share
common components. By Theorem 2.3, these two curves intersect in $O(k^{2})$
points. ∎

Finally, we mention a main weakness of the definition of Pfaffian curves. When
two functions $f_{1}(x,y)$ and $f_{2}(x,y)$ define Pfaffian curves, it is not
always true that $f_{1}+f_{2}$ defines a Pfaffian curve.

Pfaffian functions. Consider an open set $U\subset\mathbb{R}^{2}$ and let
$f_{1},f_{2},\ldots,f_{r}$ be analytic functions from $U$ to $\mathbb{R}$. We
say that $f_{1},f_{2},\ldots,f_{r}$ form a _Pfaffian chain_ if, for every
$1\leq i\leq r$, there exist polynomials
$g_{i,x},g_{i,y}\in\mathbb{R}[x,y,z_{1},\ldots,z_{i}]$ that satisfy

$\displaystyle\frac{\partial f_{i}}{\partial x}$
$\displaystyle=g_{i,x}(x,y,f_{1},f_{2},\ldots,f_{i}),$
$\displaystyle\frac{\partial f_{i}}{\partial y}$
$\displaystyle=g_{i,y}(x,y,f_{1},f_{2},\ldots,f_{i}).$

The _order_ of the chain is $r$. The _degree_ of the chain is $\max_{1\leq
i\leq r}\max\\{\deg g_{i,x},\deg g_{i,y}\\}$.

A function $f$ from $U$ to $\mathbb{R}$ is _Pfaffian_ if there exists a
Pfaffian chain $f_{1},f_{2},\ldots,f_{r}$ and a polynomial
$g\in\mathbb{R}[x,y,z_{1},\ldots,z_{r}]$ such that

$f(x,y)=g(x,y,f_{1},\ldots,f_{r}).$

The _order_ of the Pfaffian function $f$ is the order of the corresponding
Pfaffian chain. The _degree_ of the Pfaffian function $f$ is the pair $(k,\deg
g)$, where $k$ is the degree of the Pfaffian chain.

As our first example of a Pfaffian function, consider $f(x,y)=x\cdot
y^{5}-e^{x^{2}+3x}$. We set $f_{1}(x,y)=e^{x^{2}+3x}$. Then

$\displaystyle\frac{\partial f_{1}}{\partial x}$ $\displaystyle=(2x+3)\cdot
e^{x^{2}+3x},$ $\displaystyle\frac{\partial f_{1}}{\partial y}$
$\displaystyle=0,$ $\displaystyle f(x,y)$ $\displaystyle=x\cdot
y^{5}-f_{1}(x,y).$

Setting $g_{1,x}(x,y,z_{1})=(2x+3)\cdot z_{1}$ and $g_{1,y}(x,y,z_{1})=0$,
implies that $f_{1}$ is a Pfaffian chain of order 1 and degree 2. Setting
$g(x,y,z_{1})=x\cdot y^{5}-z_{1}$ implies that $f(x,y)$ is a Pfaffian function
of order 1 and degree $(2,6)$.

Every polynomial $f\in\mathbb{R}[x,y]$ is a Pfaffian function of order 0 and
degree $(0,\deg f)$. Indeed, we can take an empty Pfaffian chain and set
$g=f$. The following claim considers the more complicated example of the curve
$y=\cos x$.

######  Claim 2.5.

The function $f(x,y)=y-\cos x$ is Pfaffian in the open set
$U=\\{(x,y)\in\mathbb{R}^{2}\ :\ -\pi<x<\pi\\}$.

###### Proof.

In this case, we use a Pfaffian chain of order 2. We set
$f_{1}(x,y)=\tan(x/2)$ and $f_{2}(x,y)=\cos^{2}(x/2)$. We have that

$\displaystyle\frac{\partial f_{1}}{\partial x}$
$\displaystyle=\frac{1}{2\cos^{2}x}=\frac{1}{2}\left(1+\frac{1}{\cos^{2}x}-1\right)=\frac{1}{2}\left(1+\tan^{2}x\right),$
$\displaystyle\frac{\partial f_{2}}{\partial x}$
$\displaystyle=-\sin(x/2)\cos(x/2),$ $\displaystyle\frac{\partial
f_{1}}{\partial y}$ $\displaystyle=\frac{\partial f_{2}}{\partial y}=0.$

By setting $g_{1,x}(x,y,z_{1})=(1+z_{1})/2$,
$g_{2,x}(x,y,z_{1},z_{2})=-z_{1}z_{2}$, and $g_{1,y}=g_{2,y}=0$, we get that
We $f_{1},f_{2}$ is a Pfaffian chain.

We set $g(x,y,z_{1},z_{2})=2z_{2}-1$. By a half-angle trigonometric identity,
we have that $f(x,y)=g(x,y,f_{1},f_{2})$, so $f$ is indeed Pfaffian. The
restriction on $U$ is needed only for $f_{1}$ to be well-defined in $U$. ∎

Claim 2.5 cannot be generalized to $U=\mathbb{R}^{2}$. Indeed, one can create
a set of $m$ points and a set of $n$ scalings of the curve $y=\cos x$, where
each point is incident to each curve. Such a configuration has $mn$
incidences, which contradicts Theorem 1.3.

Pfaffian functions also include logarithms, exponential functions, roots,
inverse trigonometric functions, and more. Adding, multiplying, and composing
Pfaffian functions yields Pfaffian functions.

For an example that includes integration, consider a Pfaffian function
$h(x,y)=y-h_{1}(x)$ and let $f(x,y)=y-\int_{c}^{x}h_{1}(t)dt$. (Proving this
case covers all Liouvillian functions, as defined in the introduction.) Since
$h$ is Pfaffian, there exists a Pfaffian chain $f_{1},\ldots,f_{r}$ such that
$h$ is a polynomial in $x,y,f_{1},\ldots,f_{r}$. We claim that
$f_{1},\ldots,f_{r},f$ is also a Pfaffian chain. Indeed, the derivative of
$\int_{c}^{x}h(t)dt$ by $x$ is a polynomial in $x,y,f_{1},\ldots,f_{r}$. The
derivative of $\int_{c}^{x}h(t)dt$ by $y$ is zero. This longer Pfaffian chain
implies that $f$ is a Pfaffian function.

As usual, we require an upper bound on the number of intersection points of
two curves defined by Pfaffian functions. Khovanskiĭ [10] contains a variety
of such results. We chose to rely on Theorem 2 of Section 4.6 of that work,
since it does not require introducing additional technical concepts. The
following is a special case of that theorem.

######  Theorem 2.6.

For an open $U\subset\mathbb{R}^{2}$, let $f_{1},f_{2}$ be pfaffian functions
of the form $U\to\mathbb{R}$. Then the number of connected components of the
point set satisfying $f_{1}=f_{2}=0$ is at most a finite expression that
depends only on the orders and degrees of the Pfaffian functions.

We do not state an explicit upper bound on the number of connected components
in Theorem 2.6, since it is rather complicated and requires additional
technical definitions. This theorem implies the following.

######  Corollary 2.7.

Consider two curves in $\mathbb{R}^{2}$ that are defined by Pfaffian functions
and do not share an infinite connect component. Then the number of
intersection points between the two curves is at most a finite expression that
depends only on the orders and degrees of the Pfaffian functions.

##  3 Incidences with Pfaffian Curves

In this section, we derive our incidence bound with Pfaffian curves. That is,
we prove Theorem 1.2. Our approach follows the classical _cutting_ proof
method. For example, see [11, Chapter 4].

We first recall a weaker incidence bound that does not rely on any geometric
properties (for example, see [14, Lemma 3.4]).

######  Lemma 3.1.

Let $\mathcal{P}$ be a set of $m$ points and let $\Gamma$ be a set of $n$
curves, both in $\mathbb{R}^{2}$. If the incidence graph of
$\mathcal{P}\times\mathcal{L}$ contains no $K_{s,t}$, then

$\displaystyle I(\mathcal{P},\Gamma)=$ $\displaystyle
O_{s,t}(mn^{1-1/s}+n),\quad\text{ and }$ $\displaystyle I(\mathcal{P},\Gamma)$
$\displaystyle=O_{s,t}(m^{1-1/t}n+m).$

For example, for any three points $p,q,r\in\mathbb{R}^{2}$, at most one circle
is incident to all three points. Thus, when studying circles the incidence
graph contains no $K_{3,2}$, so Lemma 3.1 leads to
$I(\mathcal{P},\Gamma)=O(mn^{2/3}+n)$ and
$I(\mathcal{P},\Gamma)=O(m^{1/2}n+m)$.

Lemma 3.1 gives a weaker bound since it does not rely on any geometric
properties. It is based only on not having $K_{s,t}$ in the incidence graph.
For that reason, this lemma is not limited to algebraic curves. The exact same
proof also holds for Pfaffian curves (and for any other definition of curves).

Let $\Gamma$ be a set of Pfaffian curves in $\mathbb{R}^{2}$. We define a _pf-
cell_ to be a region in $\mathbb{R}^{2}$ that is bounded by at most two
segments of curves from $\Gamma$ and at most two vertical line segments. A pf-
cell may also be unbounded. For examples of pf-cells, see Figure 3(a–c). A
_cutting_ of $\Gamma$ is a partition of $\mathbb{R}^{2}$ into pf-cells. Every
point of $\mathbb{R}^{2}$ is either in the interior of a pf-cell or on the
boundary of at least two pf-cells. For example, see Figure 3(d).

Figure 3: (a) A pf-cell whose boundary consists of four segments. (b) A pf-
cell whose boundary consists of two segments. (c) A pf-cell whose boundary
consists of one segment. (d) A cutting of the three green curves.

######  Lemma 3.2.

Let $\Gamma$ be a set of $n$ Pfaffian curves of degree at most $k$, none of
which is a segment of a vertical line. For each $1\leq r<n$, there exists a
cutting with $O_{k}(r^{2}\log^{2}n)$ pf-cells, such that the interior of each
cell is intersected by at most $n/r$ curves of $\Gamma$.

###### Proof.

For $s\in(0,1)$ that is set below, we make $s$ random curve choices from
$\Gamma$. Each random choice is made uniformly, and the same curve may be
chosen more than once. Let $S$ be the set of at most $s$ chosen curves. A
curve that is chosen more than once appears only once in $S$.

For any intersection point $p$ of two curves of $S$, we shoot vertical rays up
and down from $p$. These rays end once they hit a curve of $S$. If a ray never
hits a curve of $S$, it continues indefinitely. We also shoot rays up and down
from every point where the tangent of a curve of $S$ is vertical. For example,
see Figure 3(d).

Let $R$ be the set of all vertical rays that were shot as described above. By
Theorem 2.3, every two curves of $\Gamma$ have $O(k^{2})$ intersection points.
By Lemma 2.4, every curve of $S$ has a vertical tangent in $O(k^{2})$ points.
Thus, we get that the number of rays in $R$ is $O_{k}(s^{2})$. It is not
difficult to check that $S\cup R$ is a cutting.

We split every curve of $S$ into arcs at every intersection point with another
curve of $S$ and at every endpoint of a ray of $R$. By Theorem 2.3, every
curve of $\Gamma$ has $O_{k}(s)$ intersection points, leading to a total of
$O_{k}(s^{2})$. By Lemma 2.4, there are $O_{k}(s)$ endpoints of rays. That is,
there are $O_{k}(s^{2})$ arcs. Since the boundary of each pf-cell includes 1–4
arcs and each arc is on the boundary of at most two cells, there are
$O_{k}(s^{2})$ pf-cells.

A probabilistic argument. To complete the proof, we now show that, with
positive probability, every pf-cell is intersected by at most $n/r$ curves of
$\Gamma$. This implies that there exists a choice of $S$ that satisfies this
property, as required.

We recall that the boundary of a pf-cell consists of at most two segments of
curves from $\Gamma$, and at most two vertical rays. Each vertical ray
originates from at most one other curve of $\Gamma$, so a pf-cell is defined
by at most four curves. See Figure 4.

Figure 4: A pf-cell is defined by at most four curves.

We say that a pf-cell is _bad_ if it is intersected by more than $n/r$ curves
$\Gamma$. For a specific bad pf-cell $\tau$ to exist, the 1–4 curves of
$\Gamma$ that define $\tau$ need to be chosen to $S$ and all curves that
intersect $\tau$ need not to be chosen to $S$. When choosing a single curve
from $\Gamma$, the probability of not choosing $n/r$ specific curves is
$(1-1/r)$. When performing $s$ choices, the probability of never choosing
$n/r$ specific curves is $(1-1/r)^{s}$. Recalling the inequality $1+x\leq
e^{x}$, we conclude that the probability of a specific bad pf-cell to exist is
smaller than $e^{-s/r}$.

Since each bad cell is defined by at most four curves of $\Gamma$, there are
fewer than $2n^{4}$ potential bad pf-cells. By the union bound principle, the
chance of at least one of those bad cells existing is smaller than
$2n^{4}e^{-s/r}$. Setting $s=5r\log n$, we obtain that the expected number of
bad cells is smaller than

$2n^{4}e^{-5\log n}=2n^{4}\cdot n^{-5}=2/n.$

As $n$ grows, this expectation becomes arbitrarily small. Thus, with positive
probability, there are no bad cells.

To complete the proof, we recall that there are $O_{k}(s^{2})$ pf-cells. With
$s=5r\log n$, we obtain $O(r^{2}\log^{2}n)$ pf-cells. ∎

We are now ready to prove Theorem 1.2. We first recall the statement of this
result.

Theorem 1.2. _Let $\mathcal{P}$ be a set of $m$ points and let $\Gamma$ be a
set of $n$ Pfaffian curves of degree at most $k$, both in $\mathbb{R}^{2}$. If
the incidence graph of $\mathcal{P}$ and $\Gamma$ contains no copy of
$K_{s,t}$ then_

$I(\mathcal{P},\Gamma)=O_{k,s,t}\left(m^{\frac{s}{2s-1}}n^{\frac{2s-2}{2s-1}}\log^{\frac{2s-2}{2s-1}}n+n\log^{2}n+m\right).$

###### Proof.

We rotate $\mathbb{R}^{2}$ so that no element of $\Gamma$ is a vertical lines.
By Lemma 2.1(a), the curves of $\Gamma$ remain Pfaffian after a rotation.
Similarly, a rotation does not affect $I(\mathcal{P},\Gamma)$ or the incidence
graph. By Lemma 3.1 and the assumption on the incidence graph, for every
$\mathcal{P}^{\prime}\subset\mathcal{P}$ and $\Gamma^{\prime}\subset\Gamma$,
we have that

$I(\mathcal{P}^{\prime},\Gamma^{\prime})=O_{k,s,t}(|\mathcal{P}^{\prime}|\cdot|\Gamma^{\prime}|^{1-1/s}+|\Gamma^{\prime}|).$
(1)

By Lemma 3.2, for every $1\leq r<n$ there exists a cutting with
$O(r^{2}\log^{2}n)$ pf-cells, such that the interior of each pf-cell is
intersected by at most $n/r$ curves of $\Gamma$. We consider such a cutting
with a value of $r$ that is set below. Let the number of pf-cells be
$c=O(r^{2}\log^{2}n)$ and denote the cells as $C_{1},\ldots,C_{c}$. Let
$\mathcal{P}_{i}$ be the set of points from $\mathcal{P}$ in the interior of
$C_{i}$. Let $\Gamma_{i}$ be the set of curves from $\Gamma$ that intersect
the interior of $C_{i}$. Let $\Gamma_{0}\subset\Gamma$ be the set of curves
that form the cutting and let $\mathcal{P}_{0}$ be the set of points from
$\mathcal{P}$ that are on the curves of $\Gamma_{0}$ and the vertical rays.
That is, the curves of $\Gamma_{0}$ do not intersect the interior of any cell
and the points of $\mathcal{P}_{0}$ are not in the interior of any cell.

Three types of incidences. To obtain our upper bound on
$I(\mathcal{P},\Gamma)$, we first split this quantity into three disjoint
parts:

$I\left(\mathcal{P},\Gamma\right)=\sum_{i=1}^{c}I\left(\mathcal{P}_{i},\Gamma_{i}\right)+I\left(\mathcal{P}_{0},\Gamma\setminus\Gamma_{0}\right)+I\left(\mathcal{P}_{0},\Gamma_{0}\right).$

Figure 5: A point that is incident to four curves is a corner of at least
eight pf-cells.

We first consider $I(\mathcal{P}_{0},\Gamma_{0})$. We define a _corner_ of a
pf-cell as a point where two of the boundary segments of that pf-cell meet.
The number of corners in a pf-cell is equivalent to the number of boundary
segments (a pf-cell with one boundary segment has zero corners. See Figure
3(c)). By definition, each pf-cell has at most four corners. If a point of
$\mathcal{P}_{0}$ is on $j$ curves of $\Gamma_{0}$, then it is a corner of at
least $2j$ cells. For example, see Figure 5. Since there are
$O(r^{2}\log^{2}n)$ cells, such corners contribute $O(r^{2}\log^{2}n)$
incidences to $I(\mathcal{P}_{0},\Gamma_{0})$. A point of $\mathcal{P}_{0}$
that is not a corner is incident to exactly one curve of $\Gamma_{0}$. We
conclude that

$I(\mathcal{P}_{0},\Gamma_{0})=O(r^{2}\log^{2}n+|\mathcal{P}_{0}|).$ (2)

Next, we consider $I(\mathcal{P}_{0},\Gamma\setminus\Gamma_{0})$. Every point
that participates in such an incidence is an intersection of a curve from
$\Gamma\setminus\Gamma_{0}$ with a curve of and a boundary segment. By
definition, there are $O(r^{2}\log^{2}n)$ boundary segments and each is
intersected by at most $n/r$ curves from $\Gamma\setminus\Gamma_{0}$. We
conclude that

$I(\mathcal{P}_{0},\Gamma\setminus\Gamma_{0})=O(nr\log^{2}n).$ (3)

It remains to derive an upper bound for
$\sum_{i=1}^{c}I\left(\mathcal{P}_{i},\Gamma_{i}\right)$. By definition,
$|\Gamma_{i}|\leq n/r$ for every $i$. Applying (1) separately in each cell
leads to

$\displaystyle\sum_{i=1}^{c}I\left(\mathcal{P}_{i},\Gamma_{i}\right)=\sum_{i=1}^{c}O_{k,s,t}(|\mathcal{P}_{i}|\cdot|\Gamma_{i}|^{1-1/s}+|\Gamma_{i}|)$
$\displaystyle=O_{k,s,t}\left(\sum_{i=1}^{c}|\mathcal{P}_{i}|\cdot(n/r)^{1-1/s}+\sum_{i=1}^{c}\frac{n}{r}\right)$
$\displaystyle\hskip
19.91692pt=O_{k,s,t}\left(\frac{mn^{1-1/s}}{r^{1-1/s}}+nr\log^{2}n\right).$
(4)

Completing the analysis. Combining (2), (3), and (4) implies that

$I(\mathcal{P},\Gamma)=O_{k,s,t}\left(\frac{mn^{1-1/s}}{r^{1-1/s}}+nr\log^{2}n\right).$

One term in this bound decreases with $r$ and the other increases with $r$.
Thus, to optimize the bound, we choose the value of $r$ that makes both terms
equal. This is the case when

$r=\frac{m^{s/(2s-1)}}{{n^{1/(2s-1)}\log^{2s/(2s-1)}}n}.$ (5)

Plugging the above value of $r$ in the incidence bound leads to

$I(\mathcal{P},\Gamma)=O_{k,s,t}\left(n\cdot\frac{m^{s/(2s-1)}}{{n^{1/(2s-1)}\log^{2s/(2s-1)}}n}\cdot\log^{2}n\right)=O_{k,s,t}\left(m^{\frac{s}{2s-1}}n^{\frac{2s-2}{2s-1}}\log^{\frac{2s-2}{2s-1}}n\right).$

Our choice of $r$ may violate the restriction $1\leq r<n$. Consider the case
where $r<1$. In this case, (5) implies that $m<n^{1/s}\log^{2}n$. Combining
this with (1) leads to $I(\mathcal{P},\Gamma)=O_{k,s,t}(n\log^{2}n)$.

It remains to consider the case where $r\geq n$. In this case, (5) implies
that $n<\sqrt{m}$. By Theorem 2.3, the incidence graph does not contain a
$K_{6k^{2}+k+2,2}$. The second part of Lemma 3.1 implies that

$I(\mathcal{P},\Gamma)=O_{k}(n\sqrt{m}+m)=O_{k}(m).$

∎

##  4 Incidences with Curves Defined by Pfaffian Functions

In this section, we study incidences with curves defined by Pfaffian
functions. That is, we prove Theorem 1.3. This requires the following
incidence result from [7].

######  Theorem 4.1.

Let $\mathcal{P}$ be a set of $m$ points and $H$ be a set of $n$ hyperplanes,
both in $\mathbb{R}^{d}$. For every ${\varepsilon}>0$, if the incidence graph
of $\mathcal{P}$ and $H$ contains no $K_{s,t}$ then

$I(\mathcal{P},H)=O_{s,t,{\varepsilon}}(m^{\frac{sd-s}{sd-1}+{\varepsilon}}n^{\frac{sd-d}{sd-1}}+m+n).$

We are now ready to prove Theorem 1.3. We first recall the statement of this
result.

Theorem 1.3. _Let $F$ be a Pfaffian family of dimension $d$. Let $\mathcal{P}$
be a set of $m$ points in $\mathbb{R}^{2}$. Let $\Gamma$ be a set of $n$
curves from $F$, such that no two share a common component. Then for any
${\varepsilon}>0$, we have that_

$I(\mathcal{P},\Gamma)=O_{d,{\varepsilon}}\left(n^{\frac{2d-4}{2d-3}+{\varepsilon}}m^{\frac{d-1}{2d-3}}+m+n\right).$

###### Proof.

By Theorem 2.6, there exists $t$ such that the incidence graph of
$\mathcal{P}$ and $\Gamma$ contains no $K_{t,2}$. The value of $t$ is upper
bounded by an expression that includes the order and degree of $F$, but does
not depend on $m$ and $n$. We move to a dual space $\mathbb{R}^{d}$, as
follows.

A dual space. Let $f(x,y)=a_{1}\cdot m_{1}(x,y)+\cdots+a_{d}\cdot m_{d}(x,y)$
be the function that defines the Pfaffian family $F$. Each curve
$\gamma\in\Gamma$ corresponds to a specific choice of values for
$a_{1},\ldots,a_{d}\in\mathbb{R}$. The dual of $\gamma$ is the point
$\gamma^{*}=(a_{1},\ldots,a_{d})\in\mathbb{R}^{d}$. We set
$\Gamma^{*}=\\{\gamma^{*}\ :\ \gamma\in\Gamma\\}$. That is, $\Gamma^{*}$ is a
set of $n$ points in $\mathbb{R}^{d}$.

Let the coordinates of $\mathbb{R}^{d}$ be $z_{1},\ldots,z_{d}$. We define the
dual of a point $p=(p_{x},p_{y})\in\mathbb{R}^{2}$ to be the hyperplane
$p^{*}\subset\mathbb{R}^{d}$ that is defined by $z_{1}\cdot
m_{1}(p_{x},p_{y})+\cdots+z_{d}\cdot m_{d}(p_{x},p_{y})=0$. We set
$\mathcal{P}^{*}=\\{p^{*}\ :\ p\in\mathcal{P}\\}$. That is, $\mathcal{P}^{*}$
is a set of $m$ hyperplanes in $\mathbb{R}^{d}$.

A point $p\in\mathcal{P}$ is incident to a curve $\gamma\in\Gamma$ if and only
if the point $\gamma^{*}$ is incident to the hyperplane $p^{*}$. Indeed, both
are equivalent to the equation $a_{1}\cdot
m_{1}(p_{x},p_{y})+\cdots+a_{d}\cdot m_{d}(p_{x},p_{y})=0$. This implies that
$I(\mathcal{P},\Gamma)=I(\Gamma^{*},\mathcal{P}^{*})$ and that the incidence
graphs are identical except that the two sides switched. In particular, the
incidence graph of $\Gamma^{*}$ and $\mathcal{P}^{*}$ contains no $K_{2,t}$.

We note that the origin is not in $\Gamma^{*}$. Indeed, the origin of
$\mathbb{R}^{d}$ corresponds to $a_{1}=\cdots=a_{d}=0$, which does not define
a curve in $\mathbb{R}^{2}$. Assume for contradiction that there exists a line
in $\mathbb{R}^{d}$ that contains the origin and two points from $\Gamma^{*}$.
Then there exists a nonzero $c\in\mathbb{R}$ such that the points can be
written as $(a_{1},\ldots,a_{d})$ and $(c\cdot a_{1},\ldots,c\cdot a_{d})$.
This is impossible, since both points correspond to the same curve in $F$ and
curves of $C$ do not share common components.

Moving one dimension lower. By definition, every hyperplane of
$\mathcal{P}^{*}$ is incident to the origin of $\mathbb{R}^{d}$. We rotate
$\mathbb{R}^{d}$ around the origin so that no hyperplane of $\mathcal{P}^{*}$
is defined by $z_{1}=0$ and no point of $\Gamma^{*}$ has a zero
$z_{1}$-coordinate. We note that after such a rotation the origin is still not
in $\Gamma^{*}$ and no line contains the origin and two points from
$\Gamma^{*}$.

Let $\Pi$ be the hyperplane in $\mathbb{R}^{d}$ that is defined by $z_{1}=1$.
For a point $\gamma^{*}\in\Gamma$, let $\ell_{\gamma^{*}}$ be the line
incident to $\gamma^{*}$ and the origin, and let
$\gamma^{\prime}=\ell_{\gamma^{*}}\cap\Pi$. Intuitively, $\gamma^{\prime}$ is
the projection of $\gamma^{*}$ on $\Pi$, from the origin. We set
$\Gamma^{\prime}=\\{\gamma^{\prime}\ :\ \gamma^{*}\in\Gamma^{*}\\}$. By the
above, $\Gamma^{\prime}$ is a set of $n$ distinct points in $\Pi$.

For a hyperplane $p^{*}\in\mathcal{P}^{*}$, we define
$p^{\prime}=p^{*}\cap\Pi$. This can be seen as the projection of $p^{*}$ on
$\Pi$ from the origin. By the above, when thinking of $\Pi$ as
$\mathbb{R}^{d-1}$, we get that $p^{\prime}$ is a hyperplane. We set
$\mathcal{P}^{\prime}=\\{p^{\prime}\ :\ p^{*}\in\mathcal{P}^{*}\\}$. We claim
that $\mathcal{P}^{\prime}$ is a set of $m$ distinct hyperplanes in
$\mathbb{R}^{d}$. Indeed, given a hyperplane $p^{\prime}$, we can uniquely
reconstruct $p^{*}$ by taking the union of all lines passing through one point
of $p^{\prime}$ and the origin of $\mathbb{R}^{d}$.

It is not difficult to verify that a point $\gamma^{*}$ is incident to the
hyperplane $p^{*}$ if and only if $\gamma^{\prime}$ is incident to
$p^{\prime}$. This implies that
$I(\Gamma^{\prime},\mathcal{P}^{\prime})=I(\Gamma^{*},\mathcal{P}^{*})=I(\mathcal{P},\Gamma)$.
For the same reason, the incidence graph of $\Gamma^{\prime}$ and
$\mathcal{P}^{\prime}$ does not contain a $K_{2,t}$. By thinking of $\Pi$ as
$\mathbb{R}^{d-1}$ and apply Theorem 4.1 in it, we obtain that

$\displaystyle I(\mathcal{P},\Gamma)=I(\Gamma^{\prime},\mathcal{P}^{\prime})$
$\displaystyle=O_{d,{\varepsilon}}\left(n^{\frac{2(d-1)-2}{2(d-1)-1}+{\varepsilon}}m^{\frac{2(d-1)-(d-1)}{2(d-1)-1}}+m+n\right)$
$\displaystyle=O_{d,{\varepsilon}}\left(n^{\frac{2d-4}{2d-3}+{\varepsilon}}m^{\frac{d-1}{2d-3}}+m+n\right).$

∎

## References

  * [1] A. Anderson, Combinatorial bounds in distal structures, arXiv:2104.07769.
  * [2] S. Basu and O. E. Raz, An o-minimal Szemerédi–Trotter theorem, _The Quarterly Journal of Mathematics_ 69 (2018), 223–239.
  * [3] E. Bombieri and J. Bourgain, A problem on sums of two squares, _Int. Math. Res. Not._ , 2015, 3343–3407.
  * [4] J. Bourgain, More on the sum-product phenomenon in prime fields and its applications, _Int. J. Number Theory_ 1 (2005), 1–32.
  * [5] A. Chernikov, D. Galvin, and S. Starchenko, Cutting lemma and Zarankiewicz’s problem in distal structures, _Sel. Math._ 26 (2020), 1–27.
  * [6] C. Demeter, Incidence theory and restriction estimates, arXiv:1401.1873.
  * [7] J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl, A semi-algebraic version of Zarankiewicz’s problem, _Journal of the European Mathematical Society_ 19 (2017), 1785–1810.
  * [8] C. G. Gibson, _Elementary Geometry of Algebraic Curves: An Undergraduate Introduction_ , Cambridge University Press, 1998.
  * [9] N. Katz and J. Zahl, An improved bound on the Hausdorff dimension of Besicovitch sets in $\mathbb{R}^{3}$, _Journal of the American Mathematical Society_ 32 (2019), 195–259.
  * [10] A. G. Khovanskiĭ, _Fewnomials_ , Vol. 88. American Mathematical Soc., 1991.
  * [11] J. Matoušek, _Lectures on discrete geometry_ , Springer Science & Business Media, 2013.
  * [12] J. Pach and M. Sharir, On the number of incidences between points and curves, _Combinatorics, Probability and Computing_ 7 (1998), 121–127.
  * [13] M. Sharir and J. Zahl, Cutting algebraic curves into pseudo-segments and applications, _Journal of Combinatorial Theory, Series A_ 150 (2017), 1–35.
  * [14] A. Sheffer, _Polynomial methods and incidence theory_ , Cambridge University Press, 2022.