
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)$.

For a prime number $p$ and a sequence of integers $a_0,\dots,a_k\in
\{0,1,\dots,p\}$, let $s(a_0,\dots,a_k)$ be the minimum number of
$(k+1)$tuples $(x_0,\dots,x_k)\in A_0\times\dots\times A_k$ with
$x_0=x_1+\dots + x_k$, over subsets $A_0,\dots,A_k\subseteq\mathbb{Z}_p$ of
sizes $a_0,\dots,a_k$ respectively. An elegant argument of Lev (independently
rediscovered by Samotij and Sudakov) shows that there exists an extremal
configuration with all sets $A_i$ being intervals of appropriate length, and
that the same conclusion also holds for the related problem, reposed by Bajnok,
when $a_0=\dots=a_k=:a$ and $A_0=\dots=A_k$, provided $k$ is not equal 1 modulo
$p$. By applying basic Fourier analysis, we show for Bajnok's problem that if
$p\ge 13$ and $a\in\{3,\dots,p3\}$ are fixed while $k\equiv 1\pmod p$ tends to
infinity, then the extremal configuration alternates between at least two
affine nonequivalent sets.

For a sequence $(H_i)_{i=1}^k$ of graphs, let $\textrm{nim}(n;H_1,\ldots,
H_k)$ denote the maximum number of edges not contained in any monochromatic
copy of $H_i$ in colour $i$, for any colour $i$, over all $k$edgecolourings
of~$K_n$.
When each $H_i$ is connected and nonbipartite, we introduce a variant of
Ramsey number that determines the limit of $\textrm{nim}(n;H_1,\ldots,
H_k)/{n\choose 2}$ as $n\to\infty$ and prove the corresponding stability
result. Furthermore, if each $H_i$ is what we call \emph{homomorphismcritical}
(in particular if each $H_i$ is a clique), then we determine
$\textrm{nim}(n;H_1,\ldots, H_k)$ exactly for all sufficiently large~$n$. The
special case $\textrm{nim}(n;K_3,K_3,K_3)$ of our result answers a question of
Ma.
For bipartite graphs, we mainly concentrate on the twocolour symmetric case
(i.e., when $k=2$ and $H_1=H_2$). It is trivial to see that
$\textrm{nim}(n;H,H)$ is at least $\textrm{ex}(n,H)$, the maximum size of an
$H$free graph on $n$ vertices. Keevash and Sudakov showed that equality holds
if $H$ is the $4$cycle and $n$ is large; recently Ma extended their result to
an infinite family of bipartite graphs. We provide a larger family of bipartite
graphs for which $\textrm{nim}(n;H,H)=\textrm{ex}(n,H)$. For a general
bipartite graph $H$, we show that $\textrm{nim}(n;H,H)$ is always within a
constant additive error from $\textrm{ex}(n,H)$, i.e.,~$\textrm{nim}(n;H,H)=
\textrm{ex}(n,H)+O_H(1)$.

Let $u_k(G,p)$ be the maximum over all $k$vertex graphs $F$ of by how much
the number of induced copies of $F$ in $G$ differs from its expectation in the
binomial random graph with the same number of vertices as $G$ and with edge
probability $p$. This may be viewed as a measure of how close $G$ is to being
$p$quasirandom. For a positive integer $n$ and $0<p<1$, let $D(n,p)$ be the
distance from $p\binom{n}{2}$ to the nearest integer. Our main result is that,
for fixed $k\ge 4$ and for $n$ large, the minimum of $u_k(G,p)$ over $n$vertex
graphs has order of magnitude $\Theta\big(\max\{D(n,p), p(1p)\} n^{k2}\big)$
provided that $p(1p)n^{1/2} \to \infty$.

Given a hereditary family $\mathcal{G}$ of admissible graphs and a function
$\lambda(G)$ that linearly depends on the statistics of order$\kappa$
subgraphs in a graph $G$, we consider the extremal problem of determining
$\lambda(n,\mathcal{G})$, the maximum of $\lambda(G)$ over all admissible
graphs $G$ of order $n$. We call the problem perfectly $B$stable for a graph
$B$ if there is a constant $C$ such that every admissible graph $G$ of order
$n\ge C$ can be made into a blowup of $B$ by changing at most
$C(\lambda(n,\mathcal{G})\lambda(G)){n\choose2}$ adjacencies. As special
cases, this property describes all almost extremal graphs of order $n$ within
$o(n^2)$ edges and shows that every extremal graph of order $n\ge n_0$ is a
blowup of $B$.
We develop general methods for establishing stabilitytype results from flag
algebra computations and apply them to concrete examples. In fact, one of our
sufficient conditions for perfect stability is stated in a way that allows
automatic verification by a computer. This gives a unifying way to obtain
computerassisted proofs of many new results.

For every $n\in\mathbb N$ we construct a finite graph $G$ such that every
orientation $\vec G$ of $G$ contains an isometric copy of any oriented tree on
$n$ vertices, and evaluate the smallest possible cardinality of $G$. On the
other hand, we prove that every graph $G$ admits an orientation containing no
directed $\omega$paths of infinite diameter.

Let $\mathbf{k} := (k_1,\dots,k_s)$ be a sequence of natural numbers. For a
graph $G$, let $F(G;\mathbf{k})$ denote the number of colourings of the edges
of $G$ with colours $1,\dots,s$ such that, for every $c \in \{1,\dots,s\}$, the
edges of colour $c$ contain no clique of order $k_c$. Write $F(n;\mathbf{k})$
to denote the maximum of $F(G;\mathbf{k})$ over all graphs $G$ on $n$ vertices.
This problem was first considered by Erd\H{o}s and Rothschild in 1974, but it
has been solved only for a very small number of nontrivial cases.
We prove that, for every $\mathbf{k}$ and $n$, there is a complete
multipartite graph $G$ on $n$ vertices with $F(G;\mathbf{k}) =
F(n;\mathbf{k})$. Also, for every $\mathbf{k}$ we construct a finite
optimisation problem whose maximum is equal to the limit of $\log_2
F(n;\mathbf{k})/{n\choose 2}$ as $n$ tends to infinity. Our final result is a
stability theorem for complete multipartite graphs $G$, describing the
asymptotic structure of such $G$ with $F(G;\mathbf{k}) = F(n;\mathbf{k}) \cdot
2^{o(n^2)}$ in terms of solutions to the optimisation problem.

The \emph{Tur\'an function} $\ex(n,F)$ of a graph $F$ is the maximum number
of edges in an $F$free graph with $n$ vertices. The classical results of
Tur\'an and Rademacher from 1941 led to the study of supersaturated graphs
where the key question is to determine $h_F(n,q)$, the minimum number of copies
of $F$ that a graph with $n$ vertices and $\ex(n,F)+q$ edges can have.
We determine $h_F(n,q)$ asymptotically when $F$ is \emph{colorcritical}
(that is, $F$ contains an edge whose deletion reduces its chromatic number) and
$q=o(n^2)$.
Determining the exact value of $h_F(n,q)$ seems rather difficult. For
example, let $c_1$ be the limit superior of $q/n$ for which the extremal
structures are obtained by adding some $q$ edges to a maximum $F$free graph.
The problem of determining $c_1$ for cliques was a wellknown question of Erd\H
os that was solved only decades later by Lov\'asz and Simonovits. Here we prove
that $c_1>0$ for every {colorcritical}~$F$. Our approach also allows us to
determine $c_1$ for a number of graphs, including odd cycles, cliques with one
edge removed, and complete bipartite graphs plus an edge.

Laczkovich proved that if bounded subsets $A$ and $B$ of $R^k$ have the same
nonzero Lebesgue measure and the box dimension of the boundary of each set is
less than $k$, then there is a partition of $A$ into finitely many parts that
can be translated to form a partition of $B$. Here we show that it can be
additionally required that each part is both Baire and Lebesgue measurable. As
special cases, this gives measurable and translationonly versions of Tarski's
circle squaring and Hilbert's third problem.

The classical theorem of Vizing states that every graph of maximum degree $d$
admits an edgecoloring with at most $d+1$ colors. Furthermore, as it was
earlier shown by K\H{o}nig, $d$ colors suffice if the graph is bipartite.
We investigate the existence of measurable edgecolorings for graphings. A
graphing is an analytic generalization of a boundeddegree graph that appears
in various areas, such as sparse graph limits, orbit equivalence theory and
measurable group theory. We show that every graphing of maximum degree $d$
admits a measurable edgecoloring with $d + O(\sqrt{d})$ colors; furthermore,
if the graphing has no odd cycles, then $d+1$ colors suffice. In fact, if a
certain conjecture about finite graphs that strengthens Vizing's theorem is
true, then our method will show that $d+1$ colors are always enough.

We prove a Borel version of the local lemma, i.e. we show that, under
suitable assumptions, if the set of variables in the local lemma has a
structure of a Borel space, then there exists a satisfying assignment which is
a Borel function. The main tool which we develop for the proof, which is of
independent interest, is a parallel version of the MoserTardos algorithm which
uses the same random bits to resample clauses that are far enough in the
dependency graph.

Given an action of a group $\Gamma$ on a measure space $\Omega$, we provide a
sufficient criterion under which two sets $A, B\subseteq \Omega$ are measurably
equidecomposable, i.e., $A$ can be partitioned into finitely many measurable
pieces which can be rearranged using the elements of $\Gamma$ to form a
partition of $B$. In particular, we prove that every bounded measurable subset
of $R^n$, $n\ge 3$, with nonempty interior is measurably equidecomposable to a
ball via isometries. The analogous result also holds for some other spaces,
such as the sphere or the hyperbolic space of dimension $n\ge 2$.

Given a family of 3graphs $F$, we define its codegree threshold
$\mathrm{coex}(n, F)$ to be the largest number $d=d(n)$ such that there exists
an $n$vertex 3graph in which every pair of vertices is contained in at least
$d$ 3edges but which contains no member of $F$ as a subgraph. Let $F_{3,2}$ be
the 3graph on $\{a,b,c,d,e\}$ with 3edges $\{abc,abd,abe,cde\}$.
In this paper, we give two proofs that $\mathrm{coex}(n, F_{3,2})= n/3
+o(n)$, the first by a direct combinatorial argument and the second via a flag
algebra computation. Information extracted from the latter proof is then used
to obtain a stability result, from which in turn we derive the exact codegree
threshold for all sufficiently large $n$: $\mathrm{coex}(n, F_{3,2})= \lfloor
n/3 \rfloor 1$ if $n$ is congruent to $1$ modulo $3$, and $\lfloor n/3
\rfloor$ otherwise.
In addition we determine the set of codegreeextremal configurations.

The Tur\'an density $\pi(\cal F)$ of a family $\cal F$ of $r$graphs is the
limit as $n\to\infty$ of the maximum edge density of an $\cal F$free $r$graph
on $n$ vertices. Erdos [Israel J. Math 2 (1964) 183190] proved that no
Tur\'an density can lie in the open interval $(0,r!/r^r)$. Here we show that
any other open subinterval of $[0,1]$ avoiding Tur\'an densities has strictly
smaller length. In particular, this implies a conjecture of Grosu [Eprint
arXiv:1403.4653v1, 2014].

Let $X$ be any subset of the interval $[1,1]$. A subset $I$ of the unit
sphere in $R^n$ will be called \emph{$X$avoiding} if $<u,v >\notin X$ for any
$u,v \in I$. The problem of determining the maximum surface measure of a $\{ 0
\}$avoiding set was first stated in a 1974 note by Witsenhausen; there the
upper bound of $1/n$ times the surface measure of the sphere is derived from a
simple averaging argument. A consequence of the FranklWilson theorem is that
this fraction decreases exponentially, but until now the $1/3$ upper bound for
the case $n=3$ has not moved. We improve this bound to $0.313$ using an
approach inspired by Delsarte's linear programming bounds for codes, combined
with some combinatorial reasoning. In the second part of the paper, we use
harmonic analysis to show that for $n\geq 3$ there always exists an
$X$avoiding set of maximum measure. We also show with an example that a
maximiser need not exist when $n=2$.

Let $G$ be a graph whose edges are coloured with $k$ colours, and $\mathcal
H=(H_1,\dots , H_k)$ be a $k$tuple of graphs. A monochromatic $\mathcal
H$decomposition of $G$ is a partition of the edge set of $G$ such that each
part is either a single edge or forms a monochromatic copy of $H_i$ in colour
$i$, for some $1\le i\le k$. Let $\phi_{k}(n,\mathcal H)$ be the smallest
number $\phi$, such that, for every order$n$ graph and every
$k$edgecolouring, there is a monochromatic $\mathcal H$decomposition with at
most $\phi$ elements. Extending the previous results of Liu and Sousa
["Monochromatic $K_r$decompositions of graphs", Journal of Graph Theory},
76:89100, 2014], we solve this problem when each graph in $\mathcal H$ is a
clique and $n\ge n_0(\mathcal H)$ is sufficiently large.

This paper extends the scenario of the Four Color Theorem in the following
way. Let H(d,k) be the set of all kuniform hypergraphs that can be (linearly)
embedded into R^d. We investigate lower and upper bounds on the maximum (weak
and strong) chromatic number of hypergraphs in H(d,k). For example, we can
prove that for d>2 there are hypergraphs in H(2d3,d) on n vertices whose weak
chromatic number is Omega(log n/log log n), whereas the weak chromatic number
for nvertex hypergraphs in H(d,d) is bounded by O(n^((d2)/(d1))) for d>2.

We show that for every sufficiently large $n$, the number of monotone
subsequences of length four in a permutation on $n$ points is at least
$\binom{\lfloor n/3 \rfloor}{4} + \binom{\lfloor(n+1)/3\rfloor}{4} +
\binom{\lfloor (n+2)/3\rfloor}{4}$. Furthermore, we characterize all
permutations on $[n]$ that attain this lower bound. The proof uses the flag
algebra framework together with some additional stability arguments. This
problem is equivalent to some specific type of edge colorings of complete
graphs with two colors, where the number of monochromatic $K_4$'s is minimized.
We show that all the extremal colorings must contain monochromatic $K_4$'s only
in one of the two colors. This translates back to permutations, where all the
monotone subsequences of length four are all either increasing, or decreasing
only.

We consider the problem of minimizing the number of triangles in a graph of
given order and size and describe the asymptotic structure of extremal graphs.
This is achieved by characterizing the set of flag algebra homomorphisms that
minimize the triangle density.

We give a sketch of proof that any two (Lebesgue) measurable subsets of the
unit sphere in $R^n$, for $n\ge 3$, with nonempty interiors and of the same
measure are equidecomposable using pieces that are measurable.

In Martin Gardner's October, 1976 Mathematical Games column in Scientific
American, he posed the following problem: "What is the smallest number of
[queens] you can put on a board of side n such that no [queen] can be added
without creating three in a row, a column, or a diagonal?" We use the
Combinatorial Nullstellensatz to prove that this number is at least n, except
in the case when n is congruent to 3 modulo 4, in which case one less may
suffice. A second, more elementary proof is also offered in the case that n is
even.

S.Janson [Poset limits and exchangeable random posets, Combinatorica 31
(2011), 529563] defined limits of finite posets in parallel to the emerging
theory of limits of dense graphs.
We prove that each poset limit can be represented as a kernel on the unit
interval with the standard order, thus answering an open question of Janson. We
provide two proofs: realanalytic and combinatorial. The combinatorial proof is
based on a Szemereditype Regularity Lemma for posets which may be of
independent interest.
Also, as a byproduct of the analytic proof, we show that every atomless
ordered probability space admits a measurepreserving and almost
orderpreserving map to the unit interval.

We discuss the definability of finite graphs in firstorder logic with two
relation symbols for adjacency and equality of vertices. The logical depth
$D(G)$ of a graph $G$ is equal to the minimum quantifier depth of a sentence
defining $G$ up to isomorphism. The logical width $W(G)$ is the minimum number
of variables occurring in such a sentence. The logical length $L(G)$ is the
length of a shortest defining sentence. We survey known estimates for these
graph parameters and discuss their relations to other topics (such as the
efficiency of the WeisfeilerLehman algorithm in isomorphism testing, the
evolution of a random graph, quantitative characteristics of the zeroone law,
or the contribution of Frank Ramsey to the research on Hilbert's
Entscheidungsproblem). Also, we trace the behavior of the descriptive
complexity of a graph as the logic becomes more restrictive (for example, only
definitions with a bounded number of variables or quantifier alternations are
allowed) or more expressible (after powering with counting quantifiers).

Erdos asked in 1962 about the value of f(n,k,l), the minimum number of
kcliques in a graph of order n and independence number less than l. The case
(k,l)=(3,3) was solved by Lorden. Here we solve the problem (for all large n)
when (k,l) is (3,4), (3,5), (3,6), (3,7), (4,3), (5,3), (6,3), and (7,3).
Independently, Das, Huang, Ma, Naves, and Sudakov did the cases (k,l)=(3,4) and
(4,3).

The Tur\'an density \pi(H) of a family H of kgraphs is the limit as n tends
to infinity of the maximum edge density of an Hfree kgraph on n vertices. Let
I^k consist of all possible Tur\'an densities and let F^k be the set of Tur\'an
densities of finite kgraph families.
Here we prove that F^k contains every density obtained from an arbitrary
finite construction by optimally blowing it up and using recursion inside the
specified set of parts. As an application, we show that F^k contains an
irrational number for each k\ge 3.
Also, we show that I^k has cardinality of the continuum. In particular, I^k
is not equal to F^k.