Abstract. It is a well known result due to Korshunov and Sapozhenko that the hypercube in [Formula: see text] dimensions has [Formula: see text] independent sets. Jenssen and Keevash investigated in depth Cartesian powers of cycles of fixed even lengths far beyond counting independent sets. They wonder to which extent their results extend to cycles of odd length, where not even the easiest case, counting independent sets in Cartesian powers of the triangle, is known. In this paper, we make progress on their question by providing a lower bound, which we believe to be tight. We also obtain a less precise lower bound for the number of independent sets in Cartesian powers of arbitrary odd cycles and show how to approach this question both with the cluster expansion method as well as more directly with isoperimetric inequalities.

A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost-regular, uniform hypergraph H with small maximum codegree has an almost-perfect matching. We extend this result by obtaining a conflict-free matching, where conflicts are encoded via a collection C of subsets C ⊆ E (H). We say that a matching M ⊆ E (H) is conflict-free if M does not contain an element of C as a subset. Under natural assumptions on C, we prove that H has a conflict-free, almost-perfect matching. This has many applications, one of which yields new asymptotic results for so-called “high-girth” Steiner systems. Our main tool is a polynomial time random greedy algorithm which we call the “conflict-free matching process”. * The full version of the paper can be accessed at https://arxiv.org/abs/2205.05564

We consider bond percolation on random graphs with given degrees and bounded average degree. In particular, we consider the order of the largest component after the random deletion of the edges of such a random graph. We give a rough characterization of those degree distributions for which bond percolation with high probability leaves a component of linear order, known usually as a giant component. We show that essentially the critical condition has to do with the tail of the degree distribution. Our proof makes use of recent technique which is based on the switching method and avoids the use of the classic configuration model on degree sequences that have a limiting distribution. Thus our results hold for sparse degree sequences without the usual restrictions that accompany the configuration model.

In the 1960s, Erdös and Pósa proved that there is a packing-covering duality for cycles in graphs. As part of the graph minor project, Robertson and Seymour greatly extended this: there is such a duality for $H$-expansions in graphs if and only if $H$ is a planar graph (this includes the previous result for $H=K_3$). We consider vertex labeled graphs and minors and provide such a characterization for 2-connected labeled graphs $H$. In particular, this generalizes results of Kakimura, Kawarabayashi and Marx [ J. Combin. Theory Ser. B, 101 (2011), pp. 378--381] and Huynh, Joos, and Wollan [ Combinatorica, 39 (2019), pp. 91--133] up to weaker dependencies of the parameters.

Compared to the classical binomial random (hyper)graph model, the study of random regular hypergraphs is made more challenging due to correlations between the occurrence of different edges. We develop an edge-switching technique for hypergraphs which allows us to show that these correlations are limited for a large range of densities. This extends some previous results of Kim, Sudakov, and Vu for graphs. From our results we deduce several corollaries on subgraph counts in random $d$-regular hypergraphs. We also prove a conjecture of Dudek, Frieze, Ruciński, and Šileikis on the threshold for the existence of an $\ell$-overlapping Hamilton cycle in a random $d$-regular $r$-graph. Moreover, we apply our results to prove bounds on the query complexity of testing subgraph-freeness. The problem of testing subgraph-freeness in the general graphs model was first studied by Alon, Kaufman, Krivelevich, and Ron, who obtained several bounds on the query complexity of testing triangle-freeness. We extend some of these previous results beyond the triangle setting and to the hypergraph setting.

A key feature of Simonovits' proof of the classic Erdös--Pósa theorem is a simple subgraph of the host graph, a frame, that determines the outcome of the theorem. We transfer this frame technique to $A$-paths. With it we deduce a simple proof of Gallai's theorem, although with a worse bound, and we verify the Erdös--Pósa property for long and for even $A$-paths. We also show that even $A$-paths do not have the edge-Erdös--Pósa property.

We provide a combinatorial characterization of all testable properties of k-graphs (i.e. k-uniform hypergraphs). Here, a k-graph property P is testable if there is a randomized algorithm which makes a bounded number of edge queries and distinguishes with probability 2/3 between k-graphs that satisfy P and those that are far from satisfying P. For the 2-graph case, such a combinatorial characterization was obtained by Alon, Fischer, Newman and Shapira. Our results for the k-graph setting are in contrast to those of Austin and Tao, who showed that for the somewhat stronger concept of local repairability, the testability results for graphs do not extend to the 3-graph setting.

The traditional Erdos-Renyi model of a random network is of little use in modelling the type of complex networks which modern researchers study. In this graph, every pair of vertices is equally likely to be connected by an edge. However, 21st century networks are of diverse nature and usually exhibit inhomogeneity among their nodes. This motivates the study, for a fixed degree sequence D=(d1, ..., dn), of a uniformly chosen simple graph G(D) on {1, ..., n} where the vertex i has degree di. In this paper, we study the existence of a giant component in G(D). A heuristic argument suggests that a giant component in G(D) will exist provided that the sum of the squares of the degrees is larger than twice the sum of the degrees. In 1995, Molloy and Reed essentially proved this to be the case when the degree sequence D under consideration satisfies certain technical conditions [Random Structures & Algorithms, 6:161-180]. This work has attracted considerable attention, has been extended to degree sequences under weaker conditions and has been applied to random models of a wide range of complex networks such as the World Wide Web or biological systems operating at a sub-molecular level. Nevertheless, the technical conditions on D restrict the applicability of the result to sequences where the vertices of high degree play no important role. This is a major problem since it is observed in many real-world networks, such as scale-free networks, that vertices of high degree (the so-called hubs) are present and play a crucial role. In this paper we characterize when a uniformly random graph with a fixed degree sequence has a giant component. Our main result holds for every degree sequence of length n provided that a minor technical condition is satisfied. The typical structure of G(D) when D does not satisfy this condition is relatively simple and easy to understand. Our result gives a unified criterion that implies all the known results on the existence of a giant component in G(D), including both the generalizations of the Molloy-Reed result and results on more restrictive models. Moreover, it turns out that the heuristic argument used in all the previous works on the topic, does not extend to general degree sequences.

For a graph $G$, let $\nu_s(G)$ be the size of a largest induced matching of $G$. We prove that $\nu_s(G)\geq\frac{n(G)}{(\lceil{\Delta}/{2}\rceil+1)(\lfloor{\Delta}/{2}\rfloor+1)}$ for every graph of sufficiently large maximum degree $\Delta$ and without isolated vertices. This bound is sharp. Moreover, there is a polynomial-time algorithm which computes induced matchings of the size stated above.

For a graph $G$, let $\nu_s(G)$ be the strong matching number of $G$. We prove the sharp bound $\nu_s(G)\geq \frac{n(G)}{9}$ for every graph $G$ of maximum degree at most 4 and without isolated vertices that does not contain a certain blown-up 5-cycle as a component. This result implies a strengthening of a consequence, namely, $\nu_s(G)\geq \frac{m(G)}{18}$ for such graphs and $\nu_s(G)\geq \frac{m(G)}{20}$ for a graph of maximum degree 4, of the well-known conjecture of Erdös and Nešetřil, which says that the strong chromatic index $\chi_s'(G)$ of a graph $G$ is at most $\frac{5}{4}\Delta(G)^2$, since $\nu_s(G)\geq \frac{m(G)}{\chi_s'(G)}$ and $n(G)\geq \frac{2m(G)}{\Delta(G)}$. This bound is tight and the proof implies a polynomial time algorithm to find an induced matching of this size.

We investigate the threshold probability for connectivity of sparse graphs under weak assumptions. As a corollary this completely solves the problem for Cartesian powers of arbitrary graphs. In detail, let $G$ be a connected graph on $k$ vertices, $G^n$ be the $n$th Cartesian power of $G$, $\alpha_i$ be the number of vertices of degree $i$ of $G$, $\lambda$ be a positive real number, and $G^n_p$ be the graph obtained from $G^n$ by deleting every edge independently with probability $1-p$. If $\sum_{i} \alpha_i(1-p)^i=\lambda^{\frac{1}{n}}$, then $\lim_{n\rightarrow \infty}\mathbb{P}[G^n_p {\rm\ is\ connected}]=\exp(-\lambda)$. This result extends known results for regular graphs. The main result implies that the threshold probability does not depend on the graph structure of $G$ itself, but only on the degree sequence of the graph.

We prove that a cubic graph with $m$ edges has an induced matching with at least $m/9$ edges. Our result generalizes a result for planar graphs due to Kang, Mnich, and Müller (SIAM J. Discrete Math., 26 (2012), pp. 1383--1411) and solves a conjecture of Henning and Rautenbach.