Abstract. We study conditions under which an edge-colored hypergraph has a particular substructure that contains more than the trivially guaranteed number of monochromatic edges. Our main result solves this problem for perfect matchings under minimum degree conditions. This answers recent questions of Gishboliner, Glock, and Sgueglia and of Balogh, Treglown, and Zárate-Guerén.

We investigate the emergence of spanning structures in sparse pseudo-random k-uniform hypergraphs, using the following comparatively weak notion of pseudorandomness. A k-uniform hypergraph H on n vertices is called (p, α, ε)-pseudo-random if for all not necessarily disjoint sets A1, …, Ak ⊂ V (H) with |A1|···|Ak| > αnk we have e(A1, …, Ak) = (1 ± ε)p|A1|···|Ak|. For any linear k-uniform F we provide a bound on α = α(n) in terms of p = p(n) and F, such that (under natural divisibility assumptions on n) any (p, α, o(1))-pseudo-random n-vertex H with a mild minimum degree condition contains an F-factor. The approach also enables us to establish the existence of loose Hamilton cycles in sufficiently pseudo-random hypergraphs and all results imply corresponding bounds for stronger notions of hypergraph pseudo-randomness such as jumbledness or large spectral gap. As a consequence of our results, perfect matchings appear at α = o(pk) while loose Hamilton cycles appear at α = o(pk–1). This extends the works of Lenz–Mubayi, and Lenz–Mubayi–Mycroft who studied the analogous problems in the dense setting.

Given integers $r, k \geq2$ let $\kappa_{r,k+1}(G)$ denote the number of distinct edge colorings of $G$ with $r$ colors, which are $K_{k+1}$-free, i.e., which contain no monochromatic clique on $k+1$ vertices. Alon et al. [ J. Lond. Math. Soc. (2), 70 (2004), pp. 273--288] show that for $r\in\{2,3\}$ and all $k\geq 2$ the maximum of $\kappa_{r,k+1}(G)$ over all $G$ on $n$ vertices is achieved only by the Turán graph, provided $n>n_0(k)$ is sufficiently large. The proof uses Szemerédi's regularity lemma and yields an $n_0(k)$ which is tower type with height exponential in $k$. As a lower bound the authors observed that $n_0(k)$ must be at least exponential in $k$. In this paper we essentially close the gap between the upper and the lower bound for $n_0(k)$. Answering the question posed by Alon et al. we show that the lower bound is of correct order and that it suffices to choose $n_0(k)=\exp(Ck^4)$ for some absolute constant $C$.

We investigate the smallest possible minimum degree of $r$-color minimal Ramsey graphs for the $k$-clique. In particular, we obtain a bound of the form $O(k^2\log^2 k\big)$, which is tight up to a $(\log^2 k)$-factor whenever the number $r\geq2$ of colors is fixed. This extends the work of Burr, Erdös, and Lovász, who determined this extremal value for two colors and any clique size, and complements that of Fox, Grinshpun, Liebenau, Person, and Szabó, who gave essentially tight bounds when the order $k$ of the clique is fixed. As a side product our result also yields an improved upper bound on the vertex Folkman number $F(r,k, k+1)$ of the $k$-clique. The proof relies on a reformulation of the corresponding extremal function by Fox et al. and combines and refines methods used by Dudek, Eaton, and Rödl.

We deal with two intimately related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to express how much a given graph “resembles” a random one. Moreover, a regular partition approximates a given graph by a bounded number of quasi-random graphs. Regarding quasi-randomness, we present a new spectral characterization of low discrepancy, which extends to sparse graphs. Concerning regular partitions, we introduce a concept of regularity that takes into account vertex weights, and show that if $G=(V,E)$ satisfies a certain boundedness condition, then G admits a regular partition. In addition, building on the work of Alon and Naor [Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, IL, ACM, New York, 2004, pp. 72–80], we provide an algorithm that computes a regular partition of a given (possibly sparse) graph G in polynomial time. As an application, we present a polynomial time approximation scheme for MAX CUT on (sparse) graphs without “dense spots.”

We study sufficient $\ell$-degree ($1\leq\ell