We investigate bounds in Ramsey’s theorem for relations definable in NIP structures. Applying model-theoretic methods to finitary combinatorics, we generalize a theorem of Bukh and Matousek (Duke Mathematical Journal163(12) (2014), 2243–2270) from the semialgebraic case to arbitrary polynomially bounded $o$-minimal expansions of $\mathbb{R}$, and show that it does not hold in $\mathbb{R}_{\exp }$. This provides a new combinatorial characterization of polynomial boundedness for $o$-minimal structures. We also prove an analog for relations definable in $P$-minimal structures, in particular for the field of the $p$-adics. Generalizing Conlon et al. (Transactions of the American Mathematical Society366(9) (2014), 5043–5065), we show that in distal structures the upper bound for $k$-ary definable relations is given by the exponential tower of height $k-1$.

Let $n,r,k\in \mathbb{N}$. An $r$-colouring of the vertices of a regular $n$-gon is any mapping $\unicode[STIX]{x1D712}:\mathbb{Z}_{n}\rightarrow \{1,2,\ldots ,r\}$. Two colourings are equivalent if one of them can be obtained from another by a rotation of the polygon. An $r$-ary necklace of length $n$ is an equivalence class of $r$-colourings of $\mathbb{Z}_{n}$. We say that a colouring is $k$-alternating if all $k$ consecutive vertices have pairwise distinct colours. We compute the smallest number $r$ for which there exists a $k$-alternating $r$-colouring of $\mathbb{Z}_{n}$ and we count, for any $r$, 2-alternating $r$-colourings of $\mathbb{Z}_{n}$ and 2-alternating $r$-ary necklaces of length $n$.

An embedding of a metric graph $(G,d)$ on a closed hyperbolic surface is essential if each complementary region has a negative Euler characteristic. We show, by construction, that given any metric graph, its metric can be rescaled so that it admits an essential and isometric embedding on a closed hyperbolic surface. The essential genus $g_{e}(G)$ of $(G,d)$ is the lowest genus of a surface on which such an embedding is possible. We establish a formula to compute $g_{e}(G)$ and show that, for every integer $g\geq g_{e}(G)$, there is an embedding of $(G,d)$ (possibly after a rescaling of $d$) on a surface of genus $g$. Next, we study minimal embeddings where each complementary region has Euler characteristic $-1$. The maximum essential genus $g_{e}^{\max }(G)$ of $(G,d)$ is the largest genus of a surface on which the graph is minimally embedded. We describe a method for an essential embedding of $(G,d)$, where $g_{e}(G)$ and $g_{e}^{\max }(G)$ are realised.

The exact crossing number is only known for a small number of families of graphs. Many of the families for which crossing numbers have been determined correspond to cartesian products of two graphs. Here, the cartesian product of the sunlet graph, denoted ${\mathcal{S}}_{n}$, and the star graph, denoted $K_{1,m}$, is considered for the first time. It is proved that the crossing number of ${\mathcal{S}}_{n}\Box K_{1,2}$ is $n$, and the crossing number of ${\mathcal{S}}_{n}\Box K_{1,3}$ is $3n$. An upper bound for the crossing number of ${\mathcal{S}}_{n}\Box K_{1,m}$ is also given.

As a strengthening of Hadwiger’s conjecture, Gerards and Seymour conjectured that every graph with no odd Kt minor is (t − 1)-colourable. We prove two weaker variants of this conjecture. Firstly, we show that for each t ⩾ 2, every graph with no odd Kt minor has a partition of its vertex set into 6t − 9 sets V1, …, V6t−9 such that each Vi induces a subgraph of bounded maximum degree. Secondly, we prove that for each t ⩾ 2, every graph with no odd Kt minor has a partition of its vertex set into 10t −13 sets V1,…, V10t−13 such that each Vi induces a subgraph with components of bounded size. The second theorem improves a result of Kawarabayashi (2008), which states that the vertex set can be partitioned into 496t such sets.

We prove a generalmulti-dimensional central limit theorem for the expected number of vertices of a given degree in the family of planar maps whose vertex degrees are restricted to an arbitrary (finite or infinite) set of positive integers D. Our results rely on a classical bijection with mobiles (objects exhibiting a tree structure), combined with refined analytic tools to deal with the systems of equations on infinite variables that arise. We also discuss possible extensions to maps of higher genus and to weighted maps.

In this paper, we extend the strong laws of large numbers and entropy ergodic theorem for partial sums for tree-indexed nonhomogeneous Markov chains fields to delayed versions of nonhomogeneous Markov chains fields indexed by a homogeneous tree. At first we study a generalized strong limit theorem for nonhomogeneous Markov chains indexed by a homogeneous tree. Then we prove the generalized strong laws of large numbers and the generalized asymptotic equipartition property for delayed sums of finite nonhomogeneous Markov chains indexed by a homogeneous tree. As corollaries, we can get the similar results of some current literatures. In this paper, the problem settings may not allow to use Doob's martingale convergence theorem, and we overcome this difficulty by using Borel–Cantelli Lemma so that our proof technique also has some new elements compared with the reference Yang and Ye (2007).

First, we prove a theorem on dynamics of actions of monoids by endomorphisms of semigroups. Second, we introduce algebraic structures suitable for formalizing infinitary Ramsey statements and prove a theorem that such statements are implied by the existence of appropriate homomorphisms between the algebraic structures. We make a connection between the two themes above, which allows us to prove some general Ramsey theorems for sequences. We give a new proof of the Furstenberg–Katznelson Ramsey theorem; in fact, we obtain a version of this theorem that is stronger than the original one. We answer in the negative a question of Lupini on possible extensions of Gowers’ Ramsey theorem.

For a group $G$, let $\unicode[STIX]{x1D6E4}(G)$ denote the graph defined on the elements of $G$ in such a way that two distinct vertices are connected by an edge if and only if they generate $G$. Let $\unicode[STIX]{x1D6E4}^{\ast }(G)$ be the subgraph of $\unicode[STIX]{x1D6E4}(G)$ that is induced by all the vertices of $\unicode[STIX]{x1D6E4}(G)$ that are not isolated. We prove that if $G$ is a 2-generated noncyclic abelian group, then $\unicode[STIX]{x1D6E4}^{\ast }(G)$ is connected. Moreover, $\text{diam}(\unicode[STIX]{x1D6E4}^{\ast }(G))=2$ if the torsion subgroup of $G$ is nontrivial and $\text{diam}(\unicode[STIX]{x1D6E4}^{\ast }(G))=\infty$ otherwise. If $F$ is the free group of rank 2, then $\unicode[STIX]{x1D6E4}^{\ast }(F)$ is connected and we deduce from $\text{diam}(\unicode[STIX]{x1D6E4}^{\ast }(\mathbb{Z}\times \mathbb{Z}))=\infty$ that $\text{diam}(\unicode[STIX]{x1D6E4}^{\ast }(F))=\infty$.

We discuss a rich family of directed series–parallel (SP) graphs grown by the simultaneous random series or parallel development of multiple edges. The family portrays a spectrum that spans a wide range of SP graphs: from simple models, where only as few as one edge is chosen for evolution at each discrete point in time, to complex hierarchical lattice networks grown by a take-all strategy, where all the edges in the existing network are developed.

The family of SP graphs we discuss is grown from an initial seed graph with τ0 edges under an arbitrary building sequence, $\{k_{n}\}_{n=1}^{\infty}$, of nonnegative integers (with $k_n \le \tau _0 + \sum\nolimits_{i = 1}^n {k_i} $, for arbitrary τ0 ≥ 1), that specifies the number of edges subjected to evolution at time n. We study the average north polar degree and show that we can go beyond averages to strong laws. We also find the exact average number of critical edges. The asymptotics of the critical edges are facilitated under the regularity condition that $k_n/\sum\nolimits_{i = 1}^n {k_i} $ converges to a constant (as n → ∞), a natural condition easily met by practical strategies, such as single-edge evolution and take-all choice, and much in between.

In the framework of coupled cell systems, a coupled cell network describes graphically the dynamical dependencies between individual dynamical systems, the cells. The fundamental network of a network reveals the hidden symmetries of that network. Subspaces defined by equalities of coordinates which are flow-invariant for any coupled cell system consistent with a network structure are called the network synchrony subspaces. Moreover, for every synchrony subspace, each network admissible system restricted to that subspace is a dynamical system consistent with a smaller network called a quotient network. We characterize networks such that: the network is a subnetwork of its fundamental network, and the network is a fundamental network. Moreover, we prove that the fundamental network construction preserves the quotient relation and it transforms the subnetwork relation into the quotient relation. The size of cycles in a network and the distance of a cell to a cycle are two important properties concerning the description of the network architecture. In this paper, we relate these two architectural properties in a network and its fundamental network.

Free binary systems are shown not to admit idempotent means. This refutes a conjecture of the author. It is also shown that the extension of Hindman’s theorem to nonassociative binary systems formulated and conjectured by the author is false.

Is there some absolute $\unicode[STIX]{x1D700}>0$ such that for any claw-free graph $G$, the chromatic number of the square of $G$ satisfies $\unicode[STIX]{x1D712}(G^{2})\leqslant (2-\unicode[STIX]{x1D700})\unicode[STIX]{x1D714}(G)^{2}$, where $\unicode[STIX]{x1D714}(G)$ is the clique number of $G$? Erdős and Nešetřil asked this question for the specific case where $G$ is the line graph of a simple graph, and this was answered in the affirmative by Molloy and Reed. We show that the answer to the more general question is also yes, and, moreover, that it essentially reduces to the original question of Erdős and Nešetřil.

Let $G$ be a claw-free graph on $n$ vertices with clique number $\unicode[STIX]{x1D714}$, and consider the chromatic number $\unicode[STIX]{x1D712}(G^{2})$ of the square $G^{2}$ of $G$. Writing $\unicode[STIX]{x1D712}_{s}^{\prime }(d)$ for the supremum of $\unicode[STIX]{x1D712}(L^{2})$ over the line graphs $L$ of simple graphs of maximum degree at most $d$, we prove that $\unicode[STIX]{x1D712}(G^{2})\leqslant \unicode[STIX]{x1D712}_{s}^{\prime }(\unicode[STIX]{x1D714})$ for $\unicode[STIX]{x1D714}\in \{3,4\}$. For $\unicode[STIX]{x1D714}=3$, this implies the sharp bound $\unicode[STIX]{x1D712}(G^{2})\leqslant 10$. For $\unicode[STIX]{x1D714}=4$, this implies $\unicode[STIX]{x1D712}(G^{2})\leqslant 22$, which is within 2 of the conjectured best bound. This work is motivated by a strengthened form of a conjecture of Erdős and Nešetřil.

We consider a problem introduced by Mossel and Ross (‘Shotgun assembly of labeled graphs’, arXiv:1504.07682). Suppose a random n × n jigsaw puzzle is constructed by independently and uniformly choosing the shape of each ‘jig’ from q possibilities. We are given the shuffled pieces. Then, depending on q, what is the probability that we can reassemble the puzzle uniquely? We say that two solutions of a puzzle are similar if they only differ by a global rotation of the puzzle, permutation of duplicate pieces, and rotation of rotationally symmetric pieces. In this paper, we show that, with high probability, such a puzzle has at least two non-similar solutions when 2 ⩽ q ⩽ 2e−1/2n, all solutions are similar when q ⩾ (2+ϵ)n, and the solution is unique when q = ω(n).

We study the geometry of the component of the origin in the uniform spanning forest of $\mathbb{Z}^{d}$ and give bounds on the size of balls in the intrinsic metric.

A result of Haglund implies that the $(q,t)$-bigraded Hilbert series of the space of diagonal harmonics is a $(q,t)$-Ehrhart function of the flow polytope of a complete graph with netflow vector $(-n,1,\ldots ,1)$. We study the $(q,t)$-Ehrhart functions of flow polytopes of threshold graphs with arbitrary netflow vectors. Our results generalize previously known specializations of the mentioned bigraded Hilbert series at $t=1$, $0$, and $q^{-1}$. As a corollary to our results, we obtain a proof of a conjecture of Armstrong, Garsia, Haglund, Rhoades, and Sagan about the $(q,q^{-1})$-Ehrhart function of the flow polytope of a complete graph with an arbitrary netflow vector.

We study local properties of the Bakry–Émery curvature function ${\mathcal{K}}_{G,x}:(0,\infty ]\rightarrow \mathbb{R}$ at a vertex $x$ of a graph $G$ systematically. Here ${\mathcal{K}}_{G,x}({\mathcal{N}})$ is defined as the optimal curvature lower bound ${\mathcal{K}}$ in the Bakry–Émery curvature-dimension inequality $CD({\mathcal{K}},{\mathcal{N}})$ that $x$ satisfies. We provide upper and lower bounds for the curvature functions, introduce fundamental concepts like curvature sharpness and $S^{1}$-out regularity, and relate the curvature functions of $G$ with various spectral properties of (weighted) graphs constructed from local structures of $G$. We prove that the curvature functions of the Cartesian product of two graphs $G_{1},G_{2}$ are equal to an abstract product of curvature functions of $G_{1},G_{2}$. We explore the curvature functions of Cayley graphs and many particular (families of) examples. We present various conjectures and construct an infinite increasing family of 6-regular graphs which satisfy $CD(0,\infty )$ but are not Cayley graphs.

We discuss 1-factorizations of complete graphs that “match” a given Hadamard matrix. We prove the existence of these factorizations for two families of Hadamard matrices: Walsh matrices and certain Paley matrices.

For a graph $G$, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$, as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. Alon et al. [‘Maximum cuts and judicious partitions in graphs without short cycles’, J. Combin. Theory Ser. B 88 (2003), 329–346] conjectured that, for any fixed graph $H$, there exists an $\unicode[STIX]{x1D716}(H)>0$ such that $f(m,H)\geq m/2+\unicode[STIX]{x1D6FA}(m^{3/4+\unicode[STIX]{x1D716}})$. We show that, for any wheel graph $W_{2k}$ of $2k$ spokes, there exists $c(k)>0$ such that $f(m,W_{2k})\geq m/2+c(k)m^{(2k-1)/(3k-1)}\log m$. In particular, we confirm the conjecture asymptotically for $W_{4}$ and give general lower bounds for $W_{2k+1}$.