Search

A combinatorial object is said to be quasirandom if it exhibits certain properties that are typically seen in a truly random object of the same kind. It is known that a permutation is quasirandom if and only if the pattern density of each of the twenty-four 4-point permutations is close to 1/24, which is its expected value in a random permutation. In other words, the set of all twenty-four 4-point permutations is quasirandom-forcing. Moreover, it is known that there exist sets of eight 4-point permutations that are also quasirandom-forcing. Breaking the barrier of linear dependency of perturbation gradients, we show that every quasirandom-forcing set of 4-point permutations must have cardinality at least five.

In the 1980s, Erd\H{o}s and S\'os initiated the study of Tur\'an problems with a uniformity condition on the distribution of edges: the uniform Tur\'an density of a hypergraph $H$ is the infimum over all $d$ for which any sufficiently large hypergraph with the property that all its linear-size subhypergraphs have density at least $d$ contains $H$. In particular, they asked to determine the uniform Tur\'an densities of $K_4^{(3)-}$ and $K_4^{(3)}$. After more than 30 years, the former was solved in [Israel J. Math. 211 (2016), 349-366] and [J. Eur. Math. Soc. 20 (2018), 1139-1159], while the latter still remains open. Till today, there are known constructions of 3-uniform hypergraphs with uniform Tur\'an density equal to 0, 1/27, 4/27 and 1/4 only. We extend this list by a fifth value: we prove an easy to verify condition for the uniform Tur\'an density to be equal to 8/27 and identify hypergraphs satisfying this condition.

A graph $H$ is common if its Ramsey multiplicity, i.e., the minimum number of monochromatic copies of $H$ contained in any $2$-edge-coloring of $K_n$, is asymptotically the same as the number of monochromatic copies in the random $2$-edge-coloring of $K_n$. Erd\H{o}s conjectured that every complete graph is common, which was disproved by Thomason in the 1980s. Till today, a classification of common graphs remains a widely open challenging problem. Grzesik, Lee, Lidick\'y and Volec [Combin. Prob. Comput. 31 (2022), 907--923] conjectured that every $k$-apex of any connected Sidorenko graph is common. We prove for $k\le 5$ that the $k$-apex of any tree is common.

The notion of branch-depth for matroids was introduced by DeVos, Kwon and Oum as the matroid analogue of the tree-depth of graphs. The contraction-deletion-depth, another tree-depth like parameter of matroids, is the number of recursive steps needed to decompose a matroid by contractions and deletions to single elements. Any matroid with contraction-deletion-depth at most d has branch-depth at most d. However, the two notions are not functionally equivalent as contraction-deletion-depth of matroids with branch-depth two can be arbitrarily large. We show that the two notions are functionally equivalent for representable matroids when minor closures are considered. Namely, an F-representable matroid has small branch-depth if and only if it is a minor of an F-representable matroid with small contraction-deletion-depth. This implies that any class of F-representable matroids has bounded branch-depth if and only if it is a subclass of the minor closure of a class of F-representable matroids with bounded contraction-deletion-depth.

The contraction$^*$-depth is the matroid depth parameter analogous to tree-depth of graphs. We establish the matroid analogue of the classical graph theory result asserting that the tree-depth of a graph $G$ is the minimum height of a rooted forest whose closure contains $G$ by proving the following for every matroid $M$ (except the trivial case when $M$ consists of loops and bridges only): the contraction$^*$-depth of $M$ plus one is equal to the minimum contraction-depth of a matroid containing $M$ as a restriction.

Erd\H os, Lov\'asz and Spencer showed in the late 1970s that the dimension of the region of $k$-vertex graph profiles, i.e., the region of feasible densities of $k$-vertex graphs in large graphs, is equal to the number of non-trivial connected graphs with at most $k$ vertices. We determine the dimension of the region of $k$-vertex tournament profiles. Our result, which explores an interesting connection to Lyndon words, yields that the dimension is much larger than just the number of strongly connected tournaments, which would be the answer expected as the analogy to the setting of graphs.

A classical result of Erd\H{o}s, Lov\'asz and Spencer from the late 1970s asserts that the dimension of the feasible region of densities of graphs with at most k vertices in large graphs is equal to the number of non-trivial connected graphs with at most k vertices. Indecomposable permutations play the role of connected graphs in the realm of permutations, and Glebov et al. showed that pattern densities of indecomposable permutations are independent, i.e., the dimension of the feasible region of densities of permutation patterns of size at most k is at least the number of non-trivial indecomposable permutations of size at most k. However, this lower bound is not tight already for k=3. We prove that the dimension of the feasible region of densities of permutation patterns of size at most k is equal to the number of non-trivial Lyndon permutations of size at most k. The proof exploits an interplay between algebra and combinatorics inherent to the study of Lyndon words.

Twin-width is a width parameter introduced by Bonnet, Kim, Thomass\'e and Watrigant [FOCS'20, JACM'22], which has many structural and algorithmic applications. We prove that the twin-width of every graph embeddable in a surface of Euler genus $g$ is $18\sqrt{47g}+O(1)$, which is asymptotically best possible as it asymptotically differs from the lower bound by a constant multiplicative factor. Our proof also yields a quadratic time algorithm to find a corresponding contraction sequence. To prove the upper bound on twin-width of graphs embeddable in surfaces, we provide a stronger version of the Product Structure Theorem for graphs of Euler genus $g$ that asserts that every such graph is a subgraph of the strong product of a path and a graph with a tree-decomposition with all bags of size at most eight with a single exceptional bag of size $\max\{8,32g-27\}$.

We study generalized quasirandom graphs whose vertex set consists of $q$ parts (of not necessarily the same sizes) with edges within each part and between each pair of parts distributed quasirandomly; such graphs correspond to the stochastic block model studied in statistics and network science. Lov\'asz and S\'os showed that the structure of such graphs is forced by homomorphism densities of graphs with at most $(10q)^q+q$ vertices; subsequently, Lov\'asz refined the argument to show that graphs with $4(2q+3)^8$ vertices suffice. Our results imply that the structure of generalized quasirandom graphs with $q\ge 2$ parts is forced by homomorphism densities of graphs with at most $4q^2-q$ vertices, and, if vertices in distinct parts have distinct degrees, then $2q+1$ vertices suffice. The latter improves the bound of $8q-4$ due to Spencer.

An oriented graph $H$ is quasirandom-forcing if the limit (homomorphism) density of $H$ in a sequence of tournaments is $2^{-\|H\|}$ if and only if the sequence is quasirandom. We study generalizations of the following result: the cyclic orientation of a cycle of length $\ell$ is quasirandom-forcing if and only if $\ell\equiv 2$ mod $4$. We show that no orientation of an odd cycle is quasirandom-forcing. In the case of even cycles, we find sufficient conditions on an orientation to be quasirandom-forcing, which we complement by identifying necessary conditions. Using our general results and spectral techniques used to obtain them, we classify which orientations of cycles of length up to $10$ are quasirandom-forcing.

We construct a planar graph with twin-width equal to seven.

Ramsey's Theorem guarantees for every graph H that any 2-edge-coloring of a sufficiently large complete graph contains a monochromatic copy of H. In 1962, Erdos conjectured that the random 2-edge-coloring minimizes the number of monochromatic copies of K_k, and the conjecture was extended by Burr and Rosta to all graphs. In the late 1980s, the conjectures were disproved by Thomason and Sidorenko, respectively. A classification of graphs whose number of monochromatic copies is minimized by the random 2-edge-coloring, which are referred to as common graphs, remains a challenging open problem. If Sidorenko's Conjecture, one of the most significant open problems in extremal graph theory, is true, then every 2-chromatic graph is common, and in fact, no 2-chromatic common graph unsettled for Sidorenko's Conjecture is known. While examples of 3-chromatic common graphs were known for a long time, the existence of a 4-chromatic common graph was open until 2012, and no common graph with a larger chromatic number is known. We construct connected k-chromatic common graphs for every k. This answers a question posed by Hatami, Hladky, Kral, Norine and Razborov [Combin. Probab. Comput. 21 (2012), 734-742], and a problem listed by Conlon, Fox and Sudakov [London Math. Soc. Lecture Note Ser. 424 (2015), 49-118, Problem 2.28]. This also answers in a stronger form the question raised by Jagger, Stovicek and Thomason [Combinatorica 16, (1996), 123-131] whether there exists a common graph with chromatic number at least four.

An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix $A$ and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of $A$, and when parameterized by the dual tree-depth and the entry complexity of $A$; both these parameterization imply that $A$ is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the $\ell_1$-norm of the Graver basis is bounded by a function of the maximum $\ell_1$-norm of a circuit of $A$. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix $A$ that has small primal/dual tree-depth and entry complexity if such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the $\ell_1$-norm of the Graver basis of the constraint matrix, when parameterized by the $\ell_1$-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix.

In the early 1980s, Erd\H{o}s and S\'os initiated the study of the classical Tur\'an problem with a uniformity condition: the uniform Tur\'an density of a hypergraph $H$ is the infimum over all $d$ for which any sufficiently large hypergraph with the property that all its linear-size subhyperghraphs have density at least $d$ contains $H$. In particular, they raise the questions of determining the uniform Tur\'an densities of $K_4^{(3)-}$ and $K_4^{(3)}$. The former question was solved only recently in [Israel J. Math. 211 (2016), 349-366] and [J. Eur. Math. Soc. 20 (2018), 1139-1159], while the latter still remains open for almost 40 years. In addition to $K_4^{(3)-}$, the only $3$-uniform hypergraphs whose uniform Tur\'an density is known are those with zero uniform Tur\'an density classified by Reiher, R\"odl and Schacht [J. London Math. Soc. 97 (2018), 77-97] and a specific family with uniform Tur\'an density equal to $1/27$. We develop new tools for embedding hypergraphs in host hypergraphs with positive uniform density and apply them to completely determine the uniform Tur\'an density of a fundamental family of $3$-uniform hypergraphs, namely tight cycles $C_\ell^{(3)}$. The uniform Tur\'an density of $C_\ell^{(3)}$, $\ell\ge 5$, is equal to $4/27$ if $\ell$ is not divisible by three, and is equal to zero otherwise. The case $\ell=5$ resolves a problem suggested by Reiher.

A permutation is layered if it contains neither 231 nor 312 as a pattern. It is known that, if $\sigma$ is a layered permutation, then the density of $\sigma$ in a permutation of order $n$ is maximized by a layered permutation. Albert, Atkinson, Handley, Holton and Stromquist [Electron. J. Combin. 9 (2002), R#5] claimed that the density of a layered permutation with layers of sizes $(a,1,b)$ where $a,b\geq2$ is asymptotically maximized by layered permutations with a bounded number of layers, and conjectured that the same holds if a layered permutation has no consecutive layers of size one and its first and last layers are of size at least two. We show that, if $\sigma$ is a layered permutation whose first layer is sufficiently large and second layer is of size one, then the number of layers tends to infinity in every sequence of layered permutations asymptotically maximizing the density of $\sigma$. This disproves the conjecture and the claim of Albert et al. We complement this result by giving sufficient conditions on a layered permutation to have asymptotic or exact maximizers with a bounded number of layers.

Reiher, R\"odl and Schacht [J. London Math. Soc. 97 (2018), 77--97] showed that the uniform Tur\'an density of every $3$-uniform hypergraph is either $0$ or at least $1/27$, and asked whether there exist $3$-uniform hypergraphs with uniform Tur\'an density equal or arbitrarily close to $1/27$. We construct $3$-uniform hypergraphs with uniform Tur\'an density equal to $1/27$., Comment: 22 pages, 9 figures; updated version with several small corrections and an added section with conclusive remarks

The notion of first order convergence of graphs unifies the notions of convergence for sparse and dense graphs. Ne\v{s}et\v{r}il and Ossona de Mendez [J. Symbolic Logic 84 (2019), 452-472] proved that every first order convergent sequence of graphs from a nowhere-dense class of graphs has a modeling limit and conjectured the existence of such modeling limits with an additional property, the strong finitary mass transport principle. The existence of modeling limits satisfying the strong finitary mass transport principle was proved for first order convergent sequences of trees by Ne\v{s}et\v{r}il and Ossona de Mendez [Electron. J. Combin. 23 (2016), P2.52] and for first order sequences of graphs with bounded path-width by Gajarsk\'y et al. [Random Structures Algorithms 50 (2017), 612-635]. We establish the existence of modeling limits satisfying the strong finitary mass transport principle for first order convergent sequences of graphs with bounded tree-width.

We answer three questions posed by Bubeck and Linial on the limit densities of subtrees in trees. We prove there exist positive $\varepsilon_1$ and $\varepsilon_2$ such that every tree that is neither a path nor a star has inducibility at most $1-\varepsilon_1$, where the inducibility of a tree $T$ is defined as the maximum limit density of $T$, and that there are infinitely many trees with inducibility at least $\varepsilon_2$. Finally, we construct a universal sequence of trees; that is, a sequence in which the limit density of any tree is positive., Comment: 31 pages, 8 figures

We prove a conjecture by Garbe et al. [arXiv:2010.07854] by showing that a Latin square is quasirandom if and only if the density of every 2x3 pattern is 1/720+o(1). This result is the best possible in the sense that 2x3 cannot be replaced with 2x2 or 1xN for any N.

A graph H is common if the number of monochromatic copies of H in a 2-edge-coloring of the complete graph is asymptotically minimized by the random coloring. The classification of common graphs is one of the most intriguing problems in extremal graph theory. We study the notion of weakly locally common graphs considered by Cs\'oka, Hubai and Lov\'asz [arXiv:1912.02926], where the graph is required to be the minimizer with respect to perturbations of the random 2-edge-coloring. We give a complete analysis of the 12 initial terms in the Taylor series determining the number of monochromatic copies of H in such perturbations and classify graphs H based on this analysis into three categories: graphs of Class I are weakly locally common, graphs of Class II are not weakly locally common, and graphs of Class III cannot be determined to be weakly locally common or not based on the initial 12 terms. As a corollary, we obtain new necessary conditions on a graph to be common and new sufficient conditions on a graph to be not common.

We study the asymptotic behavior of the maximum number of directed cycles of a given length in a tournament: let $c(\ell)$ be the limit of the ratio of the maximum number of cycles of length $\ell$ in an $n$-vertex tournament and the expected number of cycles of length $\ell$ in the random $n$-vertex tournament, when $n$ tends to infinity. It is well-known that $c(3)=1$ and $c(4)=4/3$. We show that $c(\ell)=1$ if and only if $\ell$ is not divisible by four, which settles a conjecture of Bartley and Day. If $\ell$ is divisible by four, we show that $1+2\cdot\left(2/\pi\right)^{\ell}\le c(\ell)\le 1+\left(2/\pi+o(1)\right)^{\ell}$ and determine the value $c(\ell)$ exactly for $\ell = 8$. We also give a full description of the asymptotic structure of tournaments with the maximum number of cycles of length $\ell$ when $\ell$ is not divisible by four or $\ell\in\{4,8\}$., Comment: One of the programs used to verify the validity of Lemma 17 is available as an ancillary file; its output has also been made available as an ancillary file

A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of K_n is asymptotically minimized by a random coloring. For every k, we construct a connected non-bipartite k-common graph. This resolves a problem raised by Jagger, Stovicek and Thomason [Combinatorica 16 (1996), 123-141]. We also show that a graph H is k-common for every k if and only if H is Sidorenko and that H is locally k-common for every k if and only if H is locally Sidorenko.

We show that every connected $k$-chromatic graph contains at least $k^{k-2}$ spanning trees.

The fractional and circular chromatic numbers are the two most studied non-integral refinements of the chromatic number of a graph. Starting from the definition of a coloring base of a graph, which originated in work related to ergodic theory, we formalize the notion of a gyrocoloring of a graph: the vertices are colored by translates of a single Borel set in the circle group, and neighbouring vertices receive disjoint translates. The corresponding gyrochromatic number of a graph always lies between the fractional chromatic number and the circular chromatic number. We investigate basic properties of gyrocolorings. In particular, we construct examples of graphs whose gyrochromatic number is strictly between the fractional chromatic number and the circular chromatic number. We also establish several equivalent definitions of the gyrochromatic number, including a version involving all finite abelian groups.

The Heusler compound Co$_2$MnSi provides a crystallographic transition from B2 to L2$_1$ structure with increasing annealing temperature $T_a$, being a model system for investigating the influence of crystallographic ordering on structural, magnetic, optic, and magnetooptic (MO) properties. Here, we present quadratic magnetooptic Kerr effect (QMOKE) spectra depending on $M^2$ in addition to the linear magnetooptic Kerr effect (LinMOKE) spectra being proportional to $M$, both in the extended visible spectral range of light from 0.8\,eV to 5.5\,eV. We investigated a set of Co$_2$MnSi thin films deposited on MgO(001) substrates and annealed from 300$^\circ$C to 500$^\circ$C. The amplitude of LinMOKE and QMOKE spectra scales linearly with $T_a$, and this effect is well pronounced at the resonant peaks below 2.0\,eV of the QMOKE spectra. Furthermore, the spectra of the MO parameters, which fully describe the MO response of Co$_2$MnSi up to the second order in $M$, are obtained dependend on $T_a$. Finally, the spectra are compared to ab-initio calculations of a purely L2$_1$ ordered Co$_2$MnSi Heusler compound., Comment: 4 pages, 3 figures, supplemental pdf, supplemental data files

A tournament H is quasirandom-forcing if the following holds for every sequence (G_n) of tournaments of growing orders: if the density of H in G_n converges to the expected density of H in a random tournament, then (G_n) is quasirandom. Every transitive tournament with at least 4 vertices is quasirandom-forcing, and Coregliano et al. [Electron. J. Combin. 26 (2019), P1.44] showed that there is also a non-transitive 5-vertex tournament with the property. We show that no additional tournament has this property. This extends the result of Bucic et al. [Combinatorica 41 (2021), 175-208] that the non-transitive tournaments with seven or more vertices do not have this property.

It is known that a sequence Pi_i of permutations is quasirandom if and only if the pattern density of every 4-point permutation in Pi_i converges to 1/24. We show that there is a set S of 4-point permutations such that the sum of the pattern densities of the permutations from S in the permutations Pi_i converges to |S|/24 if and only if the sequence is quasirandom. Moreover, we are able to completely characterize the sets S with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight., Comment: Appendices 1-5 are contained in the ancillary pdf file available on arXiv for download

A well-known conjecture of Tuza asserts that if a graph has at most $t$ pairwise edge-disjoint triangles, then it can be made triangle-free by removing at most $2t$ edges. If true, the factor 2 would be best possible. In the directed setting, also asked by Tuza, the analogous statement has recently been proven, however, the factor 2 is not optimal. In this paper, we show that if an $n$-vertex directed graph has at most $t$ pairwise arc-disjoint directed triangles, then there exists a set of at most $1.8t+o(n^2)$ arcs that meets all directed triangles. We complement our result by presenting two constructions of large directed graphs with $t\in\Omega(n^2)$ whose smallest such set has $1.5t-o(n^2)$ arcs.

A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with dual tree-depth d and largest entry D are solvable in time g(d,D)poly(n) for some function g. However, the dual tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth, and thus does not reflect its geometric structure. We prove that the minimum dual tree-depth of a row-equivalent matrix is equal to the branch-depth of the matroid defined by the columns of the matrix. We design a fixed parameter algorithm for computing branch-depth of matroids represented over a finite field and a fixed parameter algorithm for computing a row-equivalent matrix with minimum dual tree-depth. Finally, we use these results to obtain an algorithm for integer programming running in time g(d*,D)poly(n) where d* is the branch-depth of the constraint matrix; the branch-depth cannot be replaced by the more permissive notion of branch-width., Comment: Full version. 48 pages, 7 figures

Linial and Morgenstern conjectured that, among all $n$-vertex tournaments with $d\binom{n}{3}$ cycles of length three, the number of cycles of length four is asymptotically minimized by a random blow-up of a transitive tournament with all but one part of equal size and one smaller part. We prove the conjecture for $d\ge 1/36$ by analyzing the possible spectrum of adjacency matrices of tournaments. We also demonstrate that the family of extremal examples is broader than expected and give its full description for $d\ge 1/16$.

Graphons are analytic objects representing convergent sequences of large graphs. A graphon is said to be finitely forcible if it is determined by finitely many subgraph densities, i.e., if the asymptotic structure of graphs represented by such a graphon depends only on finitely many density constraints. Such graphons appear in various scenarios, particularly in extremal combinatorics. Lovasz and Szegedy conjectured that all finitely forcible graphons possess a simple structure. This was disproved in a strong sense by Cooper, Kral and Martins, who showed that any graphon is a subgraphon of a finitely forcible graphon. We strenghten this result by showing for every $\varepsilon>0$ that any graphon spans a $1-\varepsilon$ proportion of a finitely forcible graphon.

We study the uniqueness of optimal solutions to extremal graph theory problems. Lovasz conjectured that every finite feasible set of subgraph density constraints can be extended further by a finite set of density constraints so that the resulting set is satisfied by an asymptotically unique graph. This statement is often referred to as saying that `every extremal graph theory problem has a finitely forcible optimum'. We present a counterexample to the conjecture. Our techniques also extend to a more general setting involving other types of constraints.

Sidorenko's Conjecture asserts that every bipartite graph H has the Sidorenko property, i.e., a quasirandom graph minimizes the density of H among all graphs with the same edge density. We study a stronger property, which requires that a quasirandom multipartite graph minimizes the density of H among all graphs with the same edge densities between its parts; this property is called the step Sidorenko property. We show that many bipartite graphs fail to have the step Sidorenko property and use our results to show the existence of a bipartite edge-transitive graph that is not weakly norming; this answers a question of Hatami [Israel J. Math. 175 (2010), 125-150]., Comment: Minor correction on page 7

In 1975, Pippenger and Golumbic conjectured that every n-vertex graph has at most $n^k/(k^k - k)$ induced cycles of length k for k at least 5. We prove that every n-vertex graph has at most $2 n^k/k^k$ induced cycles of length k.

We prove the following 30-year old conjecture of Gy\H{o}ri and Tuza: the edges of every $n$-vertex graph $G$ can be decomposed into complete graphs $C_1,\ldots,C_\ell$ of orders two and three such that $|C_1|+\cdots+|C_\ell|\le (1/2+o(1))n^2$. This result implies the asymptotic version of the old result of Erd\H{o}s, Goodman and P\'osa that asserts the existence of such a decomposition with $\ell\le n^2/4$., Comment: We present a shorter proof of our main result; the original proof, which can be of independent interest, is contained in versions 1 and 2 of the manuscript. Small fixes suggested by the referee

We construct a fixed parameter algorithm parameterized by d and k that takes as an input a graph G' obtained from a d-degenerate graph G by complementing on at most k arbitrary subsets of the vertex set of G and outputs a graph H such that G and H agree on all but f(d,k) vertices. Our work is motivated by the first order model checking in graph classes that are first order interpretable in classes of sparse graphs. We derive as a corollary that if G_0 is a graph class with bounded expansion, then the first order model checking is fixed parameter tractable in the class of all graphs that can obtained from a graph G from G_0 by complementing on at most k arbitrary subsets of the vertex set of G; this implies an earlier result that the first order model checking is fixed parameter tractable in graph classes interpretable in classes of graphs with bounded maximum degree.

A graph is said to be walk-regular if, for each $\ell \geq 1$, every vertex is contained in the same number of closed walks of length $\ell$. We construct a $24$-vertex graph $H_4$ that is not walk-regular yet has maximized walk entropy, $S^V(H_4,\beta) = \log 24$, for some $\beta>0$. This graph is a counterexample to a conjecture of Benzi [Linear Algebra Appl.~443 (2014), 395--399, Conjecture 3.1]. We also show that there exist infinitely many temperatures $\beta_0>0$ so that $S^V(G,\beta_0)=\log n_G$ if and only if a graph $G$ is walk-regular., Comment: 7 pages, 1 figure

The theory of graph limits represents large graphs by analytic objects called graphons. Graph limits determined by finitely many graph densities, which are represented by finitely forcible graphons, arise in various scenarios, particularly within extremal combinatorics. Lovasz and Szegedy conjectured that all such graphons possess a simple structure, e.g., the space of their typical vertices is always finite dimensional; this was disproved by several ad hoc constructions of complex finitely forcible graphons. We prove that any graphon is a subgraphon of a finitely forcible graphon. This dismisses any hope for a result showing that finitely forcible graphons possess a simple structure, and is surprising when contrasted with the fact that finitely forcible graphons form a meager set in the space of all graphons. In addition, since any finitely forcible graphon represents the unique minimizer of some linear combination of densities of subgraphs, our result also shows that such minimization problems, which conceptually are among the simplest kind within extremal graph theory, may in fact have unique optimal solutions with arbitrarily complex structure.

Let d_i(G) be the density of the 3-vertex i-edge graph in a graph G, i.e., the probability that three random vertices induce a subgraph with i edges. Let S be the set of all quadruples (d_0,d_1,d_2,d_3) that are arbitrary close to 3-vertex graph densities in arbitrary large graphs. Huang, Linial, Naves, Peled and Sudakov have recently determined the projection of the set S to the (d_0,d_3) plane. We determine the projection of the set S to all the remaining planes., Comment: We have recently noticed a miscalculation in the proof of Lemma 7 and are preparing a revision of the manuscript