
We prove that squaretiled surfaces having fixed combinatorics of horizontal
cylinder decomposition and tiled with smaller and smaller squares become
asymptotically equidistributed in any ambient linear $GL(\mathbb R)$invariant
suborbifold defined over $\mathbb Q$ in the moduli space of Abelian
differentials. Moreover, we prove that the combinatorics of the horizontal and
of the vertical decompositions are asymptotically uncorrelated. As a
consequence, we prove the existence of an asymptotic distribution for the
combinatorics of a "random" interval exchange transformation with integer
lengths.
We compute explicitly the absolute contribution of squaretiled surfaces
having a single horizontal cylinder to the MasurVeech volume of any ambient
stratum of Abelian differentials. The resulting count is particularly simple
and efficient in the large genus asymptotics. We conjecture that the
corresponding relative contribution is asymptotically of the order $1/d$, where
$d$ is the dimension of the stratum, and prove that this conjecture is
equivalent to the longstanding conjecture on the large genus asymptotics of
the MasurVeech volumes. We prove, in particular, that the recent results of
Chen, M\"oller and Zagier imply that the conjecture holds for the principal
stratum of Abelian differentials as the genus tends to infinity.
Our result on random interval exchanges with integer lengths allows to make
empirical computation of the probability to get a $1$cylinder pillowcase cover
taking a "random" one in a given stratum. We use this technique to derive the
approximate values of the MasurVeech volumes of strata of quadratic
differentials of all small dimensions.

The Tur\'an function $ex(n,F)$ denotes the maximal number of edges in an
$F$free graph on $n$ vertices. We consider the function $h_F(n,q)$, the
minimal number of copies of $F$ in a graph on $n$ vertices with $ex(n,F)+q$
edges. The value of $h_F(n,q)$ has been extensively studied when $F$ is
bipartite or colourcritical. In this paper we investigate the simplest
remaining graph $F$, namely, two triangles sharing a vertex, and establish the
asymptotic value of $h_F(n,q)$ for $q=o(n^2)$.

This article proves that an irreducible subfactor planar algebra with a
distributive biprojection lattice admits a minimal 2box projection generating
the identity biprojection. It is a generalization (conjectured in 2013) of a
theorem of Oystein Ore on distributive intervals of finite groups (1938), and a
corollary of a natural subfactor extension of a conjecture of Kenneth S. Brown
in algebraic combinatorics (2000). We deduce a link between combinatorics and
representations in finite group theory.

Let $H$ be a Krull monoid with class group $G$ such that every class contains
a prime divisor. Then every nonunit $a \in H$ can be written as a finite
product of irreducible elements. If $a=u\_1 \cdot \ldots \cdot u\_k$, with
irreducibles $u\_1, \ldots u\_k \in H$, then $k$ is called the length of the
factorization and the set $\mathsf L (a)$ of all possible $k$ is called the set
of lengths of $a$. It is wellknown that the system $\mathcal L (H) = \{\mathsf
L (a) \mid a \in H \}$ depends only on the class group $G$. In the present
paper we study the inverse question asking whether or not the system $\mathcal
L (H)$ is characteristic for the class group. Consider a further Krull monoid
$H'$ with class group $G'$ such that every class contains a prime divisor and
suppose that $\mathcal L (H) = \mathcal L (H')$. We show that, if one of the
groups $G$ and $G'$ is finite and has rank at most two, then $G$ and $G'$ are
isomorphic (apart from two wellknown pairings).

A meander is a topological configuration of a line and a simple closed curve
in the plane (or a pair of simple closed curves on the 2sphere) intersecting
transversally. Meanders can be traced back to H. Poincar\'e and naturally
appear in various areas of mathematics, theoretical physics and computational
biology (in particular, they provide a model of polymer folding). Enumeration
of meanders is an important open problem. The number of meanders with 2N
crossings grows exponentially when N grows, but the longstanding problem on the
precise asymptotics is still out of reach. We show that the situation becomes
more tractable if one additionally fixes the topological type (or the total
number of minimal arcs) of a meander. Then we are able to derive simple
asymptotic formulas for the numbers of meanders as N tends to infinity. We also
compute the asymptotic probability of getting a simple closed curve on a sphere
by identifying the endpoints of two arc systems (one on each of the two
hemispheres) along the common equator. The new tools we bring to bear are based
on interpretation of meanders as squaretiled surfaces with one horizontal and
one vertical cylinders. The proofs combine recent results on MasurVeech
volumes of the moduli spaces of meromorphic quadratic differentials in genus
zero with our new observation that horizontal and vertical separatrix diagrams
of integer quadratic differentials are asymptotically uncorrelated. The
additional combinatorial constraints we impose in this article yield explicit
polynomial asymptotics.

We show that if a graph $G$ with $n \geq 3$ vertices can be drawn in the
plane such that each of its edges is involved in at most four crossings, then
$G$ has at most $6n12$ edges. This settles a conjecture of Pach,
Radoi\v{c}i\'{c}, Tardos, and T\'oth, and yields a better bound for the famous
Crossing Lemma: The crossing number, $\mbox{cr}(G)$, of a (not too sparse)
graph $G$ with $n$ vertices and $m$ edges is at least $c\frac{m^3}{n^2}$, where
$c > 1/29$. This bound is known to be tight, apart from the constant $c$ for
which the previous best lower bound was $1/31.1$. As another corollary we
obtain some progress on the Albertson conjecture: Albertson conjectured that if
the chromatic number of a graph $G$ is $r$, then $\mbox{cr}(G) \geq
\mbox{cr}(K_r)$. This was verified by Albertson, Cranston, and Fox for $r \leq
12$, and for $r \leq 16$ by Bar\'at and T\'oth. Our results imply that
Albertson conjecture holds for $r \leq 18$.

We prove Union Closed sets conjecture.

We show that there is a binary subspace code of constant dimension 3 in
ambient dimension 7, having minimum distance 4 and cardinality 333, i.e., $333
\le A_2(7,4;3)$, which improves the previous best known lower bound of 329.
Moreover, if a code with these parameters has at least 333 elements, its
automorphism group is in one of $31$ conjugacy classes. This is achieved by a
more general technique for an exhaustive search in a finite group that does not
depend on the enumeration of all subgroups.

A simple method for transmitting quantum states within a quantum computer is
via a quantum spin chainthat is, a path on $n$ vertices. Unweighted paths
are of limited use, and so a natural generalization is to consider weighted
paths; this has been further generalized to allow for loops (\emph{potentials}
in the physics literature). We study the particularly important situation of
perfect state transfer with respect to the corresponding adjacency matrix or
Laplacian through the use of orthogonal polynomials. Lowdimensional examples
are given in detail. Our main result is that PST with respect to the Laplacian
matrix cannot occur for weighted paths on $n\geq 3$ vertices nor can it occur
for certain symmetric weighted trees. The methods used lead us to a conjecture
directly linking the rationality of the weights of weighted paths on $n>3$
vertices, with or without loops, with the capacity for PST between the end
vertices with respect to the adjacency matrix.

A decomposition of a nonempty simple graph $G$ is a pair $[G,P]$, such that
$P$ is a set of nonempty induced subgraphs of $G$, and every edge of $G$
belongs to exactly one subgraph in $P$. The chromatic index $\chi'([G,P])$ of a
decomposition $[G,P]$ is the smallest number $k$ for which there exists a
$k$coloring of the elements of $P$ in such a way that: for every element of
$P$ all of its edges have the same color, and if two members of $P$ share at
least one vertex, then they have different colors. A long standing conjecture
of Erd\H{o}sFaberLov\'asz states that every decomposition $[K_n,P]$ of the
complete graph $K_n$ satisfies $\chi'([K_n,P])\leq n$. In this paper we work
with geometric graphs, and inspired by this formulation of the conjecture, we
introduce the concept of chromatic index of a decomposition of the complete
geometric graph. We present bounds for the chromatic index of several types of
decompositions when the vertices of the graph are in general position. We also
consider the particular case in which the vertices are in convex position and
present bounds for the chromatic index of a few types of decompositions.

In this paper we introduce and study discrete analogues of Lebesgue and
Hausdorff dimensions for graphs. It turned out that they are closely related to
wellknown graph characteristics such as rank dimension and Prague (or
Ne\v{s}et\v{r}ilR\"odl) dimension. It allows us to formally define fractal
graphs and establish fractality of some graph classes. We show, how Hausdorff
dimension of graphs is related to their Kolmogorov complexity. We also
demonstrate fruitfulness of this interdisciplinary approach by discovering a
novel property of general compact metric spaces using ideas from hypergraphs
theory and by proving an estimation for Prague dimension of almost all graphs
using methods from algorithmic information theory.

This paper proposes a method to reduce noise in acyclic sensor networks
enumerating targets using the integral theory with respect to Euler
characteristic. For an acyclic network (a partially ordered set) equipped with
sensors detecting targets, we find reducible points for enumerating targets, as
a generalization of weak beat points (homotopically reducible points). This
theory is useful for improving the reliability and optimization of acyclic
sensor networks.

This paper presents a combinatorial analog of topological complexity for
finite spaces. We demonstrate that this coincides with the genuine topological
complexity of the original finite space, and constitutes an upper bound for the
topological complexity of its order complex.

Let $\mathcal{P}({\bf N})$ be the power set of ${\bf N}$. We say that a
function $\mu^\ast: \mathcal{P}({\bf N}) \to \bf R$ is an upper density if, for
all $X,Y\subseteq{\bf N}$ and $h, k\in{\bf N}^+$, the following hold: (F1)
$\mu^\ast({\bf N}) = 1$; (F2) $\mu^\ast(X) \le \mu^\ast(Y)$ if $X \subseteq Y$;
(F3) $\mu^\ast(X \cup Y) \le \mu^\ast(X) + \mu^\ast(Y)$; (F4) $\mu^\ast(k\cdot
X) = \frac{1}{k} \mu^\ast(X)$, where $k \cdot X:=\{kx: x \in X\}$; (F5)
$\mu^\ast(X + h) = \mu^\ast(X)$.
We show that the upper asymptotic, upper logarithmic, upper Banach, upper
Buck, upper Polya, and upper analytic densities, together with all upper
$\alpha$densities (with $\alpha$ a real parameter $\ge 1$), are upper
densities in the sense of our definition. Moreover, we establish the mutual
independence of axioms (F1)(F5), and we investigate various properties of
upper densities (and related functions) under the assumption that (F2) is
replaced by the weaker condition that $\mu^\ast(X)\le 1$ for every
$X\subseteq{\bf N}$.
Overall, this allows us to extend and generalize results so far independently
derived for some of the classical upper densities mentioned above, thus
introducing a certain amount of unification into the theory.

We use group schemes to construct optimal packings of lines through the
origin. In this setting, optimal line packings are naturally characterized
using representation theory, which in turn leads to a necessary integrality
condition for the existence of equiangular central group frames. We conclude
with an infinite family of optimal line packings using the group schemes
associated with certain Suzuki 2groups, specifically, extensions of Heisenberg
groups. Notably, this is the first known infinite family of equiangular tight
frames generated by representations of nonabelian groups.

This article investigates emergence and complexity in complex systems that
can share information on a network. To this end, we use a theoretical approach
from information theory, computability theory, and complex networks. One key
studied question is how much emergent complexity (or information) arises when a
population of computable systems is networked compared with when this
population is isolated. First, we define a general model for networked
theoretical machines, which we call algorithmic networks. Then, we narrow our
scope to investigate algorithmic networks that optimize the average fitnesses
of nodes in a scenario in which each node imitates the fittest neighbor and the
randomly generated population is networked by a timevarying graph. We show
that there are graphtopological conditions that cause these algorithmic
networks to have the property of expected emergent openendedness for large
enough populations. In other words, the expected emergent algorithmic
complexity of a node tends to infinity as the population size tends to
infinity. Given a dynamic network, we show that these conditions imply the
existence of a central time to trigger expected emergent openendedness.
Moreover, we show that networks with small diameter compared to the network
size meet these conditions. We also discuss future research based on how our
results are related to some problems in network science, information theory,
computability theory, distributed computing, game theory, evolutionary biology,
and synergy in complex systems.

We investigate extremal graphs related to the game of Cops and Robbers. We
focus on graphs where a single cop can catch the robber; such graphs are called
copwin. The capture time of a copwin graph is the minimum number of moves the
cop needs to capture the robber. We consider graphs that are extremal with
respect to capture time, i.e. their capture time is as large as possible given
their order. We give a new characterization of the set of extremal graphs. For
our alternative approach we assign a rank to each vertex of a graph, and then
study which configurations of ranks are possible. We partially determine which
configurations are possible, enough to prove some further extremal results. We
leave a full classification as an open question.

A sorting network is a geodesic path from $12 \cdots n$ to $n \cdots 21$ in
the Cayley graph of $S_n$ generated by adjacent transpositions. For a uniformly
random sorting network, we establish the existence of a local limit of the
process of spacetime locations of transpositions in a neighbourhood of $an$
for $a\in[0,1]$ as $n\to\infty$. Here time is scaled by a factor of $1/n$ and
space is not scaled. The limit is a swap process $U$ on $\mathbb{Z}$. We show
that $U$ is stationary and mixing with respect to the spatial shift and has
timestationary increments. Moreover, the only dependence on $a$ is through
time scaling by a factor of $\sqrt{a(1a)}$. To establish the existence of $U$,
we find a local limit for staircaseshaped Young tableaux. These Young tableaux
are related to sorting networks through a bijection of Edelman and Greene.

The blowup lemma states that a system of superregular pairs contains all
bounded degree spanning graphs as subgraphs that embed into a corresponding
system of complete pairs. This lemma has farreaching applications in extremal
combinatorics.
We prove sparse analogues of the blowup lemma for subgraphs of random and of
pseudorandom graphs. Our main results are the following three sparse versions
of the blowup lemma: one for embedding spanning graphs with maximum degree
$\Delta$ in subgraphs of $G(n,p)$ with $p=C(\log n/n)^{1/\Delta}$; one for
embedding spanning graphs with maximum degree $\Delta$ and degeneracy $D$ in
subgraphs of $G(n,p)$ with $p=C_\Delta\big(\log n/n\big)^{1/(2D+1)}$; and one
for embedding spanning graphs with maximum degree $\Delta$ in
$(p,cp^{\max(4,(3\Delta+1)/2)}n)$bijumbled graphs.
We also consider various applications of these lemmas.

A graph $G$ is almost hypohamiltonian (a.h.) if $G$ is nonhamiltonian, there
exists a vertex $w$ in $G$ such that $G  w$ is nonhamiltonian, and $G  v$ is
hamiltonian for every vertex $v \ne w$ in $G$. The second author asked in [J.
Graph Theory 79 (2015) 6381] for all orders for which a.h. graphs exist. Here
we solve this problem. To this end, we present a specialised algorithm which
generates complete sets of a.h. graphs for various orders. Furthermore, we show
that the smallest cubic a.h. graphs have order 26. We provide a lower bound for
the order of the smallest planar a.h. graph and improve the upper bound for the
order of the smallest planar a.h. graph containing a cubic vertex. We also
determine the smallest planar a.h. graphs of girth 5, both in the general and
cubic case. Finally, we extend a result of Steffen on snarks and improve two
bounds on longest paths and longest cycles in polyhedral graphs due to
Jooyandeh, McKay, {\"O}sterg{\aa}rd, Pettersson, and the second author.

Recalling each edge of a graph $H$ has 2 oppositely oriented arcs, each
vertex $v$ of $H$ is identified with the set of arcs, denoted $(v,e)$,
departing from $v$ along the edges $e$ of $H$ incident to $v$. Let $H$ be a
$(\lambda,\mu)$biregular graph with vertex parts $Y$ and $X$, where $Y$,
resp. $X$, is a multiple of the positive integer $\mu$, resp. $\lambda$
($\ne\mu$). We consider the problem, for each edge $e=yx$ in $H$, of assigning,
a {\it color} (given by an element) of $\Z_\lambda$, resp. $\Z_\mu$, to the arc
$(y,e)$, resp. $(x,e)$, so that each such color is assigned exactly once in the
set of arcs departing from each vertex of $H$. Furthermore, we set such
assignment to fulfill a specific bicolor weight function over a monotonic
subset of $\Z_\lambda\times \Z_\mu$. This problem applies to the Design of
Experiments for Industrial Chemistry, Molecular Biology, Cellular Neuroscience,
etc. Four constructions of such arc colorings are presented: an algorithmic one
based on pairs of cyclic groups, and 3 essentially different ones based on the
vertices and 5cycles of the Petersen graph. Each of these 3 constructions
applies to assembling the Great Circle Challenge Puzzle.

Graphons are analytic objects associated with convergent sequences of graphs.
Problems from extremal combinatorics and theoretical computer science led to a
study of graphons determined by finitely many subgraph densities, which are
referred to as finitely forcible. Following the intuition that such graphons
should have finitary structure, Lovasz and Szegedy conjectured that the
topological space of typical vertices of a finitely forcible graphon is always
compact. We disprove the conjecture by constructing a finitely forcible graphon
such that the associated space is not compact. The construction method gives a
general framework for constructing finitely forcible graphons with nontrivial
properties.

We prove a general normal approximation theorem for local graph statistics in
the configuration model, together with an explicit bound on the error in the
approximation with respect to the Wasserstein metric. Such statistics take the
form $T := \sum_{v \in V} H_v$, where $V$ is the vertex set, and $H_v$ depends
on a neighbourhood in the graph around $v$ of size at most $\ell$. The error
bound is expressed in terms of $\ell$, $V$, an almost sure bound on $H_v$,
the maximum vertex degree $d_{\max}$ and the variance of $T$. Under suitable
assumptions on the convergence of the empirical degree distributions to a
limiting distribution, we deduce that the size of the giant component in the
configuration model has asymptotically Gaussian fluctuations.

Let $G$ be an edgecolored graph. We use $e(G)$ and $c(G)$ to denote the
number of edges of $G$ and the number of colors appearing on $E(G)$,
respectively. For a vertex $v\in V(G)$, the \emph{color neighborhood} of $v$ is
defined as the set of colors assigned to the edges incident to $v$. A subgraph
of $G$ is \emph{rainbow} if all of its edges are assigned with distinct colors.
The wellknown Mantel's theorem states that a graph $G$ on $n$ vertices
contains a triangle if $e(G)\geq\lfloor\frac{n^2}{4}\rfloor+1$. Rademacher
(1941) showed that $G$ contains at least $\lfloor\frac{n}{2}\rfloor$ triangles
under the same condition. Li, Ning, Xu and Zhang (2014) proved a rainbow
version of Mantel's theorem: An edgecolored graph $G$ has a rainbow triangle
if $e(G)+c(G)\geq n(n+1)/2$. In this paper, we first characterize all graphs
$G$ satisfying $e(G)+c(G)\geq n(n+1)/21$ but containing no rainbow triangles.
Motivated by Rademacher's theorem, we then characterize all graphs $G$ which
satisfy $e(G)+c(G)\geq n(n+1)/2$ but contain only one rainbow triangle. We
further obtain two results on color neighborhood conditions for the existence
of rainbow short cycles. Our results improve a previous theorem due to
Broersma, Li, Woeginger, and Zhang (2005). Moreover, we provide a sufficient
condition in terms of color neighborhood for the existence of a specified
number of vertexdisjoint rainbow cycles.

Let $\chi_l(G)$ denote the list chromatic number of the $r$uniform
hypergraph~$G$. Extending a result of Alon for graphs, Saxton and the second
author used the method of containers to prove that, if $G$ is simple and
$d$regular, then $\chi_l(G)\ge (1/(r1)+o(1))\log_r d$.
To see how close this inequality is to best possible, we examine $\chi_l(G)$
when $G$ is a random $r$partite hypergraph with $n$ vertices in each class.
The value when $r=2$ was determined by Alon and Krivelevich, here we show that
$\chi_l(G)= (g(r,\alpha)+o(1))\log_r d$ almost surely, where $d$ is the
expected average degree of~$G$ and $\alpha=\log_nd$.
The function $g(r,\alpha)$ is defined in terms of "preference orders" and can
be determined fairly explicitly. This is enough to show that the container
method gives an optimal lower bound on $\chi_l(G)$ for $r=2$ and $r=3$, but,
perhaps surprisingly, apparently not for $r\ge4$.