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 version of the Erdős-Rothschild problem for families of graph patterns. For any fixed k ≥ 3, let r0(k) be the largest integer such that the following holds for all 2 ≤ r ≤ r0(k) and all sufficiently large n: The Turán graph Tk-1(n) is the unique n-vertex graph G with the maximum number of r-edge-colorings such that the edge set of any copy of Kk in G is rainbow. We use the regularity lemma of Szemerédi and linear programming to obtain a lower bound on the value of r0(k). For a more general family P of patterns of Kk, we also prove that, in order to show that the Turán graph Tk-1(n) maximizes the number of P-free r-edge-colorings over n-vertex graphs, it suffices to prove a related stability result.

The Fano plane is the unique linear 3-uniform hypergraph on seven vertices and seven hyperedges. It is known that, for all $n \geq 8$, the balanced complete bipartite 3-uniform hypergraph on $n$ vertices, denoted by $B_n$, is the 3-uniform hypergraph on $n$ vertices with the largest number of hyperedges that does not contain a copy of the Fano plane. For sufficiently large $r$ and $n$, we show that $B_n$ admits the largest number of $r$-edge colorings with no rainbow copy of the Fano plane.

Given a family of graphs $\mathcal{F}$, we prove that the normalized edit distance of any given graph $\Gamma$ to being induced $\mathcal{F}$-free is estimable with a query complexity that depends only on the bounds of the Frieze--Kannan regularity lemma and on a removal lemma for $\mathcal{F}$.

Mubayi and Pikhurko established several Turán-type results and stability results for $r$-uniform hypergraphs. In particular, they considered hypergraphs that avoid a copy of an expanded complete 2-graph and a copy of a Fan-hypergraph. Their Turán stability results tell us the following for some fixed families $\mathcal{F}$ of forbidden $r$-uniform subgraphs with Turán number ${ex}(n,\mathcal{F})$: for every $\delta>0$, there exist $\varepsilon>0$ and $n_0$ such that any $\mathcal{F}$-free $r$-uniform hypergraph with $n \geq n_0$ vertices and at least ${ex}(n,\mathcal{F})-\varepsilon n^r$ hyperedges gets the “structure” of an extremal hypergraph by removing at most $\delta n^r$ hyperedges. Here, we obtain sharper stability results. For some graph families $\mathcal{F}$, we find constants $a_\mathcal{F}$ and functions $b_\mathcal{F}=O(n^{r-1})$ and $p_\mathcal{F}=\Omega(n^r)$ such that any $n$-vertex $\mathcal{F}$-free $r$-uniform hypergraph with at least ${ex}(n,\mathcal{F})-p$ hyperedges, where $p

We consider a multicolored version of a question posed by Erdös and Rothschild. For a fixed positive integer $r$ and a fixed graph $F$, we look for $n$-vertex graphs that admit the maximum number of $r$-edge colorings with the property that there is no copy of $F$ for which all edges are assigned different colors. We show that when $F$ is a bipartite graph with at least three edges and $r \geq 3$, the number of $r$-edge colorings of an extremal configuration is close to the number of such edge colorings of the complete graph $K_n$. On the other hand, for the rainbow pattern of $F=K_{k+1}$, the Turán graph $T_k(n)$ is the only extremal configuration for any $r\geq r_0(k)$ and large $n$.

There has been substantial interest in estimating the value of a graph parameter, i.e., of a real function defined on the set of finite graphs, by sampling a randomly chosen substructure whose size is independent of the size of the input. Graph parameters that may be successfully estimated in this way are said to be testable or estimable, and the sample complexity q_z=q_z(epsilon) of an estimable parameter z is the size of the random sample required to ensure that the value of z(G) may be estimated within error epsilon with probability at least 2/3. In this paper, we study the sample complexity of estimating two graph parameters associated with a monotone graph property, improving previously known results. To obtain our results, we prove that the vertex set of any graph that satisfies a monotone property P may be partitioned equitably into a constant number of classes in such a way that the cluster graph induced by the partition is not far from satisfying a natural weighted graph generalization of P}. Properties for which this holds are said to be recoverable, and the study of recoverable properties may be of independent interest.

Heilbronn conjectured that among arbitrary n points in the two-dimensional unit square [0,1] 2 , there must be three points which form a triangle of area O(1/n 2 ). This conjecture was disproved by a nonconstructive argument of Komlós, Pintz, and Szemerédi [J. London Math. Soc., 25 (1982), pp. 13--24], who showed that for every n there exists a configuration of n points in the unit square [0,1] 2 where all triangles have area $\Omega({\log n}/{n^2})$. Here we will consider a three-dimensional analogue of this problem and show how to find deterministically in polynomial time n points in the unit cube [0,1] 3 such that the volume of every tetrahedron among these n points is $\Omega(\log n/n^3)$.

Heilbronn conjectured that given arbitrary n points from the 2-dimensional unit square, there must be three points which form a triangle of area at most O(1/n 2 ). This conjecture was disproved by a nonconstructive argument of Komlós, Pintz, and Szemerédi [ J. London Math. Soc., 25 (1982), pp. 13--24] who showed that for every n there is a configuration of n points in the unit square where all triangles have area at least $\Omega({\log n}/{n^2})$. Considering a discretization of Heilbronn's problem, we give an alternative proof of the result from [J. London Math. Soc., 25 (1982), pp. 13--24]. Our approach has two advantages: First, it yields a polynomial-time algorithm which for every n computes a configuration of n points where all triangles have area $\Omega({\log n}/{n^2})$. Second, it allows us to consider a generalization of Heilbronn's problem to convex hulls of k points where we can show that an algorithmic solution is also available.

We consider the problem of finding deterministically a large independent set of guaranteed size in a hypergraph on n vertices and with m edges. With respect to the Turán bound, the quality of our solutions is better for hypergraphs with not too many small cycles by a logarithmic factor in the input size. The algorithms are fast; they often have a running time of O(m) + o(n 3 ). Indeed, the denser the hypergraphs are the closer the running times are to the linear times. For the first time, this gives for some combinatorial problems algorithmic solutions with state-of-the-art quality, solutions of which only the existence was known to date. In some cases, the corresponding upper bounds match the lower bounds up to constant factors. The involved concepts are uncrowded hypergraphs.

In this paper we give an algorithm which, given a labeled graph on n vertices and a list of all labeled graphs on k vertices, provides for each graph H of this list an approximation to the number of induced copies of H in G with total error small. This algorithm has running time $O(n^{1/ \log \log n} \cdot M(n))$, where $M(n)$ is the time needed to square an n by n matrix with 0, 1-entries over the integers. The main tool in designing this algorithm is a variant of the regularity lemma of Szemerédi.

The regularity lemma of Szemeredi (1978) is a result that asserts that every graph can be partitioned in a certain regular way. This result has numerous applications, but its known proof is not algorithmic. The authors first demonstrate the computational difficulty of finding a regular partition; they show that deciding if a given partition of an input graph satisfies the properties guaranteed by the lemma is co-NP-complete. However, they also prove that despite this difficulty the lemma can be made constructive; they show how to obtain, for any input graph, a partition with the properties guaranteed by the lemma, efficiently. The desired partition, for an n-vertex graph, can be found in time O(M(n)), where M(n)=O(n/sup 2.376/) is the time needed to multiply two n by n matrices with 0,1-entries over the integers. The algorithm can be parallelized and implemented in NC/sup 1/.>

A canonizing Ramsey type theorem for Baire mappings $\Delta : A^w \to \mathcal{Y}$, where $\mathcal{Y}$ is a metric space is established.