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.

Let Sk(n) be the maximum number of orientations of an n-vertex graph G in which no copy of Kk is strongly connected. For all integers n, k ≥ 4 where n ≥ 5 or k ≥ 5, we prove that Sk(n) = 2tk - 1(n), where tk-1(n) is the number of edges of the n-vertex (k - 1)-partite Turán graph Tk-1(n). Moreover, we prove that Tk-1(n) is the only graph having 2tk-1(n) orientations with no strongly connected copies of Kk.

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

Let M = (m_{ij}) be a symmetric matrix of order n and let G be the graph with vertex set {1,…,n} such that distinct vertices i and j are adjacent if and only if m_{ij} ≠ 0. We introduce a dynamic programming algorithm that finds a diagonal matrix that is congruent to M. If G is given with a tree decomposition 𝒯 of width k, then this can be done in time O(k|𝒯| + k² n), where |𝒯| denotes the number of nodes in 𝒯.

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.

There has been great interest in deciding whether a combinatorial structure satisfies some property, or in estimating the value of some numerical function associated with this combinatorial structure, by considering only a randomly chosen substructure of sufficiently large, but constant size. These problems are called property testing and parameter testing, where a property or parameter is said to be testable if it can be estimated accurately in this way. The algorithmic appeal is evident, as, conditional on sampling, this leads to reliable constant-time randomized estimators. Our paper addresses property testing and parameter testing for permutations in a subpermutation perspective; more precisely, we investigate permutation properties and parameters that can be well-approximated based on randomly chosen subpermutations of much smaller size. In this context, we give a permutation counterpart of a famous result by Alon and Shapira [6] stating that every hereditary graph property is testable. Moreover, we develop a theory of convergence of permutation sequences, which is used to characterize testable permutation parameters along the lines of the work of Borgs et al. [12] in the case of graphs. This theory is interesting for its own sake, as it describes the closure of the set of all permutations as a special class of Lebesgue measurable functions in [0, 1]2, which in turn may be used to define a new model of random permutations.