Abstract. Hindman proved in 1979 that no matter how natural numbers are colored in [Formula: see text] colors, for a fixed positive integer [Formula: see text], there is an infinite subset [Formula: see text] of numbers and a color [Formula: see text] such that for any finite nonempty subset [Formula: see text] of [Formula: see text], the color of the sum of elements from [Formula: see text] is [Formula: see text]. Later, Taylor extended this result to colorings with an unrestricted number of colors and five unavoidable color patterns on finite sums. This result is referred to as a canonization of Hindman’s theorem and parallels the canonical Ramsey theorem of Erdős and Rado. We extend Taylor’s result from sums, that are linear combinations with coefficients 1, to several linear combinations with coefficients 1 and [Formula: see text]. These results in turn could be interpreted as canonical-type theorems for solutions to infinite systems.

We consider a natural, yet seemingly not much studied, extremal problem in bipartite graphs. A bi-hole of size $t$ in a bipartite graph $G$ with a fixed bipartition is an independent set with exactly $t$ vertices in each part; in other words, it is a copy of $K_{t, t}$ in the bipartite complement of $G$. Let $f(n, \Delta)$ be the largest $k$ for which every $n \times n$ bipartite graph with maximum degree $\Delta$ in one of the parts has a bi-hole of size $k$. Determining $f(n, \Delta)$ is thus the bipartite analogue of finding the largest independent set in graphs with a given number of vertices and bounded maximum degree. It has connections to the bipartite version of the Erdös--Hajnal conjecture, bipartite Ramsey numbers, and the Zarankiewicz problem. Our main result determines the asymptotic behavior of $f(n, \Delta)$. More precisely, we show that for large but fixed $\Delta$ and $n$ sufficiently large, $f(n, \Delta) = \Theta(\frac{\log \Delta}{\Delta} n)$. We further address more specific regimes of $\Delta$, especially when $\Delta$ is a small fixed constant. In particular, we determine $f(n, 2)$ exactly and obtain bounds for $f(n, 3)$, though determining the precise value of $f(n, 3)$ is still open.

A k-bar visibility representation of a digraph $G$ assigns each vertex at most $k$ horizontal segments in the plane so that $G$ has an arc $uv$ if and only if some segment for $u$ “sees” some segment for $v$ above it by a vertical line of sight. The (bar) visibility number $b(G)$ of a digraph $G$ is the least $k$ permitting such a representation. Among other results, we show that $b(G) \leq 4$ when $G$ is a planar digraph (reducing to 3 when the underlying graph has no triangles), $b(G) \leq 2$ when $G$ is outerplanar, and $b(G) \leq (n+10)/3$ when $G$ has $n$ vertices. When $G$ is the $n$-vertex transitive tournament, $b(G) \leq 7n/24 + 2\sqrt{n \log n}$, improving to $b(G) < 3n/14 + 42$ when $n$ is sufficiently large. Our tools include arboricity, interval number, and Steiner systems.

Let $\ell$ be any positive integer, let n be a sufficiently large number, and let G be a graph on n vertices. Define, for any k, $\nu_k(G)= | \{ |E(H)| : H$ is an induced subgraph of G on k vertices$\} |$. We show that if there exists a k, $2\ell \leq k \leq n-2\ell$, such that $\nu_k(G) \le \ell$, then G has a complete or an empty subgraph on at least $n-\ell+1$ vertices and a homogeneous set of size at least $n-2\ell+2$. These results are sharp.

Let ${\cal A}=\{A_1,\ldots, A_r\}$ be a partition of a set $\{1,\ldots,m\}\times\{1,\ldots, n\}$ into r nonempty subsets, and let $A=(a_{ij})$ be an $m\times n$ matrix. We say that A has a pattern ${\cal A}$ provided that $a_{ij}=a_{i'j'}$ if and only if $(i,j),(i',j')\in A_t$ for some $t\in\{1,\ldots,r\}$. In this note we study the following function f defined on the set of all $m\times n$ matrices M with s distinct entries: $f(M; {\cal A})$ is the smallest number of positions where the entries of M need to be changed such that the resulting matrix does not have any submatrix with pattern ${\cal A}$. We give an asymptotically tight value for $$ f(m,n; s, {\cal A}) = \max \{f(M; {\cal A}): M \mbox{ is an } m\times n\mbox{ matrix with at most } s \mbox{ distinct entries}\}. $$

The strong chromatic number, $\chi_S(G)$, of an n‐vertex graph G is the smallest number k such that after adding $k\lceil n/k\rceil - n$ isolated vertices to G and considering any partition of the vertices of the resulting graph into disjoint subsets $V_1, \ldots, V_{\lceil n/k\rceil}$ of size k each, one can find a proper k‐vertex‐coloring of the graph such that each part $V_i$, $i=1, \ldots, \lceil n/k\rceil$, contains exactly one vertex of each color. For any graph G with maximum degree Δ, it is easy to see that $\chi_S(G) \geq \Delta + 1$. Recently, Haxell proved that $\chi_S(G) \leq 3\Delta - 1$. In this paper, we improve this bound for graphs with large maximum degree. We show that $\chi_S(G) \leq 2\Delta$ if $\Delta \geq n/6$ and prove that this bound is sharp.