We prove that, for any finite set of minimal r-graph patterns, there is a finite family $\mathcal F$ of forbidden r-graphs such that the extremal Turán constructions for $\mathcal F$ are precisely the maximum r-graphs obtainable from mixing the given patterns in any way via blowups and recursion. This extends the result by the second author [30], where the above statement was established for a single pattern.

We present two applications of this result. First, we construct a finite family $\mathcal F$ of $3$-graphs such that there are exponentially many maximum $\mathcal F$-free $3$-graphs of each large order n and, moreover, the corresponding Turán problem is not finitely stable. Second, we show that there exists a finite family $\mathcal {F}$ of $3$-graphs whose feasible region function attains its maximum on a Cantor-type set of positive Hausdorff dimension.

Thomassen’s chord conjecture from 1976 states that every longest cycle in a $3$-connected graph has a chord. The circumference $c(G)$ and induced circumference $c'(G)$ of a graph G are the length of its longest cycles and the length of its longest chordless cycles, respectively. Harvey [‘A cycle of maximum order in a graph of high minimum degree has a chord’, Electron. J. Combin. 24(4) (2017), Article no. 4.33, 8 pages] proposed the stronger conjecture: every $2$-connected graph G with minimum degree at least $3$ has $c(G)\geq c'(G)+2$. This conjecture implies Thomassen’s chord conjecture. We observe that wheels are the unique Hamiltonian graphs for which the circumference and the induced circumference differ by exactly one. Thus, we need only consider non-Hamiltonian graphs for Harvey’s conjecture. We propose a conjecture involving wheels that is equivalent to Harvey’s conjecture on non-Hamiltonian graphs. A graph is $\ell $-holed if all its holes have length exactly $\ell $. We prove that Harvey’s conjecture and hence also Thomassen’s conjecture hold for $\ell $-holed graphs and graphs with a small induced circumference.

Geometric parameters in general and curvature in particular play a fundamental role in our understanding of the structure and functioning of real-world networks. Here, the discretisation of the Ricci curvature proposed by Forman is adapted to capture the global influence of the network topology on individual edges of a graph. This is implemented mathematically by assigning communicability distances to edges in the Forman–Ricci definition of curvature. We study analytically both the edge communicability curvature and the global graph curvature and give mathematical characterisations of them. The Forman–Ricci communicability curvature is interpreted ‘physically‘ on the basis of a non-conservative diffusion process taking place on the graph. We then solve analytically a toy model that allows us to understand the fundamental differences between edges with positive and negative Forman–Ricci communicability curvature. We complete the work by analysing three examples of applications of this new graph-theoretic invariant on real-world networks: (i) the network of airport flight connections in the USA, (ii) the neuronal network of the worm Caenorhabditis elegans and (iii) the collaboration network of authors in computational geometry, where we strengthen the many potentials of this new measure for the analysis of complex systems.

We consider the count of subgraphs with an arbitrary configuration of endpoints in the random-connection model based on a Poisson point process on ${\mathord{\mathbb R}}^d$. We present combinatorial expressions for the computation of the cumulants and moments of all orders of such subgraph counts, which allow us to estimate the growth of cumulants as the intensity of the underlying Poisson point process goes to infinity. As a consequence, we obtain a central limit theorem with explicit convergence rates under the Kolmogorov distance and connectivity bounds. Numerical examples are presented using a computer code in SageMath for the closed-form computation of cumulants of any order, for any type of connected subgraph, and for any configuration of endpoints in any dimension $d{\geq} 1$. In particular, graph connectivity estimates, Gram–Charlier expansions for density estimation, and correlation estimates for joint subgraph counting are obtained.

Given a fixed small graph H and a larger graph G, an H-factor is a collection of vertex-disjoint subgraphs $H'\subset G$, each isomorphic to H, that cover the vertices of G. If G is the complete graph $K_n$ equipped with independent U(0,1) edge weights, what is the lowest total weight of an H-factor? This problem has previously been considered for $H=K_2$, for example. We show that if H contains a cycle, then the minimum weight is sharply concentrated around some $L_n = \Theta(n^{1-1/d^*})$ (where $d^*$ is the maximum 1-density of any subgraph of H). Some of our results also hold for H-covers, where the copies of H are not required to be vertex-disjoint.

We give a simplified version of the proofs that, outside of their isolated vertices, the complement of the enhanced power graph and of the power graph are connected and have diameter at most $3$.

The triangle removal states that if G contains $\varepsilon n^2$ edge-disjoint triangles, then G contains $\delta (\varepsilon )n^3$ triangles. Unfortunately, there are no sensible bounds on the order of growth of $\delta (\varepsilon )$, and at any rate, it is known that $\delta (\varepsilon )$ is not polynomial in $\varepsilon $. Csaba recently obtained an asymmetric variant of the triangle removal, stating that if G contains $\varepsilon n^2$ edge-disjoint triangles, then G contains $2^{-\operatorname {\mathrm {poly}}(1/\varepsilon )}\cdot n^5$ copies of $C_5$. To this end, he devised a new variant of Szemerédi’s regularity lemma. We obtain the following results:

• • We first give a regularity-free proof of Csaba’s theorem, which improves the number of copies of $C_5$ to the optimal number $\operatorname {\mathrm {poly}}(\varepsilon )\cdot n^5$.

• • We say that H is $K_3$-abundant if every graph containing $\varepsilon n^2$ edge-disjoint triangles has $\operatorname {\mathrm {poly}}(\varepsilon )\cdot n^{\lvert V(H)\rvert }$ copies of H. It is easy to see that a $K_3$-abundant graph must be triangle-free and tripartite. Given our first result, it is natural to ask if all triangle-free tripartite graphs are $K_3$-abundant. Our second result is that assuming a well-known conjecture of Ruzsa in additive number theory, the answer to this question is negative.

Our proofs use a mix of combinatorial, number-theoretic, probabilistic and Ramsey-type arguments.

A pebble tree is an ordered tree where each node receives some colored pebbles, in such a way that each unary node receives at least one pebble, and each subtree has either one more or as many leaves as pebbles of each color. We show that the contraction poset on pebble trees is isomorphic to the face poset of a convex polytope called pebble tree polytope. Beside providing intriguing generalizations of the classical permutahedra and associahedra, our motivation is that the faces of the pebble tree polytopes provide realizations as convex polytopes of all assocoipahedra constructed by K. Poirier and T. Tradler only as polytopal complexes.

We prove a full measurable version of Vizing’s theorem for bounded degree Borel graphs, that is, we show that every Borel graph $\mathcal {G}$ of degree uniformly bounded by $\Delta \in \mathbb {N}$ defined on a standard probability space $(X,\mu )$ admits a $\mu $-measurable proper edge coloring with $(\Delta +1)$-many colors. This answers a question of Marks [Question 4.9, J. Amer. Math. Soc. 29 (2016)] also stated in Kechris and Marks as a part of [Problem 6.13, survey (2020)], and extends the result of the author and Pikhurko [Adv. Math. 374, (2020)], who derived the same conclusion under the additional assumption that the measure $\mu $ is $\mathcal {G}$-invariant.

In the last two decades the study of random instances of constraint satisfaction problems (CSPs) has flourished across several disciplines, including computer science, mathematics and physics. The diversity of the developed methods, on the rigorous and non-rigorous side, has led to major advances regarding both the theoretical as well as the applied viewpoints. Based on a ceteris paribus approach in terms of the density evolution equations known from statistical physics, we focus on a specific prominent class of regular CSPs, the so-called occupation problems, and in particular on $r$-in-$k$ occupation problems. By now, out of these CSPs only the satisfiability threshold – the largest degree for which the problem admits asymptotically a solution – for the $1$-in-$k$ occupation problem has been rigorously established. Here we determine the satisfiability threshold of the $2$-in-$k$ occupation problem for all $k$. In the proof we exploit the connection of an associated optimization problem regarding the overlap of satisfying assignments to a fixed point problem inspired by belief propagation, a message passing algorithm developed for solving such CSPs.

Let Γ be a finite graph and let $A(\Gamma)$ be the corresponding right-angled Artin group. From an arbitrary basis $\mathcal B$ of $H^1(A(\Gamma),\mathbb F)$ over an arbitrary field, we construct a natural graph $\Gamma_{\mathcal B}$ from the cup product, called the cohomology basis graph. We show that $\Gamma_{\mathcal B}$ always contains Γ as a subgraph. This provides an effective way to reconstruct the defining graph Γ from the cohomology of $A(\Gamma)$, to characterize the planarity of the defining graph from the algebra of $A(\Gamma)$ and to recover many other natural graph-theoretic invariants. We also investigate the behaviour of the cohomology basis graph under passage to elementary subminors and show that it is not well-behaved under edge contraction.

For a given graph $H$, we say that a graph $G$ has a perfect $H$-subdivision tiling if $G$ contains a collection of vertex-disjoint subdivisions of $H$ covering all vertices of $G.$ Let $\delta _{\mathrm {sub}}(n, H)$ be the smallest integer $k$ such that any $n$-vertex graph $G$ with minimum degree at least $k$ has a perfect $H$-subdivision tiling. For every graph $H$, we asymptotically determined the value of $\delta _{\mathrm {sub}}(n, H)$. More precisely, for every graph $H$ with at least one edge, there is an integer $\mathrm {hcf}_{\xi }(H)$ and a constant $1 \lt \xi ^*(H)\leq 2$ that can be explicitly determined by structural properties of $H$ such that $\delta _{\mathrm {sub}}(n, H) = \left (1 - \frac {1}{\xi ^*(H)} + o(1) \right )n$ holds for all $n$ and $H$ unless $\mathrm {hcf}_{\xi }(H) = 2$ and $n$ is odd. When $\mathrm {hcf}_{\xi }(H) = 2$ and $n$ is odd, then we show that $\delta _{\mathrm {sub}}(n, H) = \left (\frac {1}{2} + o(1) \right )n$.

For each uniformity $k \geq 3$, we construct $k$ uniform linear hypergraphs $G$ with arbitrarily large maximum degree $\Delta$ whose independence polynomial $Z_G$ has a zero $\lambda$ with $\left \vert \lambda \right \vert = O\left (\frac {\log \Delta }{\Delta }\right )$. This disproves a recent conjecture of Galvin, McKinley, Perkins, Sarantis, and Tetali.

We show that if $\Gamma $ is a point group of $\mathbb {R}^{k+1}$ of order two for some $k\geq 2$ and $\mathcal {S}$ is a k-pseudomanifold which has a free automorphism of order two, then either $\mathcal {S}$ has a $\Gamma $-symmetric infinitesimally rigid realisation in ${\mathbb R}^{k+1}$ or $k=2$ and $\Gamma $ is a half-turn rotation group. This verifies a conjecture made by Klee, Nevo, Novik and Zheng for the case when $\Gamma $ is a point-inversion group. Our result implies that Stanley’s lower bound theorem for centrally symmetric polytopes extends to pseudomanifolds with a free simplicial automorphism of order 2, thus verifying (the inequality part of) another conjecture of Klee, Nevo, Novik and Zheng. Both results actually apply to a much larger class of simplicial complexes – namely, the circuits of the simplicial matroid. The proof of our rigidity result adapts earlier ideas of Fogelsanger to the setting of symmetric simplicial complexes.

This article explores the notions of $\mathcal {F}$-transitivity and topological $\mathcal {F}$-recurrence for backward shift operators on weighted $\ell ^p$-spaces and $c_0$-spaces on directed trees, where $\mathcal {F}$ represents a Furstenberg family of subsets of $\mathbb {N}_0$. In particular, we establish the equivalence between recurrence and hypercyclicity of these operators on unrooted directed trees. For rooted directed trees, a backward shift operator is hypercyclic if and only if it possesses an orbit of a bounded subset that is weakly dense.

We establish the restricted sumset analog of the celebrated conjecture of Sárközy on additive decompositions of the set of nonzero squares over a finite field. More precisely, we show that if $q>13$ is an odd prime power, then the set of nonzero squares in $\mathbb {F}_q$ cannot be written as a restricted sumset $A \hat {+} A$, extending a result of Shkredov. More generally, we study restricted sumsets in multiplicative subgroups over finite fields as well as restricted sumsets in perfect powers (over integers) motivated by a question of Erdős and Moser. We also prove an analog of van Lint–MacWilliams’ conjecture for restricted sumsets, which appears to be the first analogue of Erdős--Ko–Rado theorem in a family of Cayley sum graphs.

Let $f^{(r)}(n;s,k)$ denote the maximum number of edges in an n-vertex r-uniform hypergraph containing no subgraph with k edges and at most s vertices. Brown, Erdős, and Sós [New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan 1971), pp. 53–63, Academic Press 1973] conjectured that the limit $\lim _{n\rightarrow \infty }n^{-2}f^{(3)}(n;k+2,k)$ exists for all k. The value of the limit was previously determined for $k=2$ in the original paper of Brown, Erdős, and Sós, for $k=3$ by Glock [Bull. Lond. Math. Soc., 51 (2019) 230–236] and for $k=4$ by Glock, Joos, Kim, Kühn, Lichev, and Pikhurko [Proc. Amer. Math. Soc., Series B, 11 (2024) 173–186] while Delcourt and Postle [Proc. Amer. Math. Soc., 152 (2024), 1881–1891] proved the conjecture (without determining the limiting value).

In this article, we determine the value of the limit in the Brown–Erdős–Sós problem for $k\in \{5,6,7\}$. More generally, we obtain the value of $\lim _{n\rightarrow \infty }n^{-2}f^{(r)}(n;rk-2k+2,k)$ for all $r\geqslant 3$ and $k\in \{5,6,7\}$. In addition, by combining these new values with recent results of Bennett, Cushman, and Dudek [arxiv:2309.00182, 2023] we obtain new asymptotic values for several generalized Ramsey numbers.

A graph G is called chromatic-choosable if $\chi (G)=ch(G)$. A natural problem is to determine the minimum number of vertices in a non-chromatic-choosable graph with given chromatic number. It was conjectured by Ohba, and proved by Noel, Reed, and Wu that k-chromatic graphs G with $|V(G)| \le 2k+1$ are chromatic-choosable. This upper bound on $|V(G)|$ is tight. It is known that if k is even, then $G=K_{3 \star (k/2+1), 1 \star (k/2-1)}$ and $G=K_{4, 2 \star (k-1)}$ are non-chromatic-choosable k-chromatic graphs with $|V(G)| =2 k+2$. Some subgraphs of these two graphs are also non-chromatic-choosable. The main result of this paper is that all other k-chromatic graphs G with $|V(G)| =2 k+2$ are chromatic-choosable. In particular, if $\chi (G)$ is odd and $|V(G)| \le 2\chi (G)+2$, then G is chromatic-choosable, which was conjectured by Noel.

Structural convergence is a framework for the convergence of graphs by Nešetřil and Ossona de Mendez that unifies the dense (left) graph convergence and Benjamini-Schramm convergence. They posed a problem asking whether for a given sequence of graphs $(G_n)$ converging to a limit $L$ and a vertex $r$ of $L$, it is possible to find a sequence of vertices $(r_n)$ such that $L$ rooted at $r$ is the limit of the graphs $G_n$ rooted at $r_n$. A counterexample was found by Christofides and Král’, but they showed that the statement holds for almost all vertices $r$ of $L$. We offer another perspective on the original problem by considering the size of definable sets to which the root $r$ belongs. We prove that if $r$ is an algebraic vertex (i.e. belongs to a finite definable set), the sequence of roots $(r_n)$ always exists.

The present paper explores a connection between two concepts arising from different fields of mathematics. The first concept, called vine, is a graphical model for dependent random variables. This concept first appeared in a work of Joe (1994), and the formal definition was given later by Cooke (1997). Vines have nowadays become an active research area whose applications can be found in probability theory and uncertainty analysis. The second concept, called MAT-freeness, is a combinatorial property in the theory of freeness of logarithmic derivation modules of hyperplane arrangements. This concept was first studied by Abe-Barakat-Cuntz-Hoge-Terao (2016), and soon afterwards investigated further by Cuntz-Mücksch (2020).

In the particular case of graphic arrangements, the last two authors (2023) recently proved that the MAT-freeness is completely characterized by the existence of certain edge-labeled graphs, called MAT-labeled graphs. In this paper, we first introduce a poset characterization of a vine. Then we show that, interestingly, there exists an explicit equivalence between the categories of locally regular vines and MAT-labeled graphs. In particular, we obtain an equivalence between the categories of regular vines and MAT-labeled complete graphs.

Several applications will be mentioned to illustrate the interaction between the two concepts. Notably, we give an affirmative answer to a question of Cuntz-Mücksch that MAT-freeness can be characterized by a generalization of the root poset in the case of graphic arrangements.