Search

Let f^{(r)}(n;s,k) be the maximum number of edges of an r-uniform hypergraph on n vertices not containing a subgraph with k edges and at most s vertices. In 1973, Brown, Erdős, and Sós conjectured that the limit \begin{equation*} \lim _{n\to \infty } n^{-2} f^{(3)}(n;k+2,k) \end{equation*} exists for all k and confirmed it for k=2. Recently, Glock showed this for k=3. We settle the next open case, k=4, by showing that f^{(3)}(n;6,4)=\left (\frac {7}{36}+o(1)\right)n^2 as n\to \infty. More generally, for all k\in \{3,4\}, r\ge 3 and t\in [2,r-1], we compute the value of the limit \lim _{n\to \infty } n^{-t}f^{(r)}(n;k(r-t)+t,k), which settles a problem of Shangguan and Tamo. [ABSTRACT FROM AUTHOR]

A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost‐regular, uniform hypergraph H$\mathcal {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$\mathcal {C}$ of subsets C⊆E(H)$C\subseteq E(\mathcal {H})$. We say that a matching M⊆E(H)$\mathcal {M}\subseteq E(\mathcal {H})$ is conflict‐free if M$\mathcal {M}$ does not contain an element of C$\mathcal {C}$ as a subset. Under natural assumptions on C$\mathcal {C}$, we prove that H$\mathcal {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 random greedy algorithm which we call the 'conflict‐free matching process'. [ABSTRACT FROM AUTHOR]

We prove that in all regular robust expanders G, every edge is asymptotically equally likely contained in a uniformly chosen perfect matching M. We also show that given any fixed matching or spanning regular graph N in G, the random variable |M ∩ E(N)| is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders. [ABSTRACT FROM AUTHOR]

As observed by Rautenbach and Sereni [SIAM J. Discrete Math. 28 (2014) 335-341] there is a gap in the proof of the theorem of Balister et al. [Combin. Probab. Comput. 13 (2004) 311-317], which states that the intersection of all longest paths in a connected circular arc graph is nonempty. In this paper we close this gap.

We prove that any quasirandom uniform hypergraph H can be approximately decomposed into any collection of bounded degree hypergraphs with almost as many edges. In fact, our results also apply to multipartite hypergraphs and even to the sparse setting when the density of H quickly tends to 0 in terms of the number of vertices of H. Our results answer and address questions of Kim, Kühn, Osthus and Tyomkyn; and Glock, Kühn and Osthus as well as Keevash. The provided approximate decompositions exhibit strong quasirandom properties which are very useful for forthcoming applications. Our results also imply approximate solutions to natural hypergraph versions of long-standing graph decomposition problems, as well as several decomposition results for (quasi)random simplicial complexes into various more elementary simplicial complexes such as triangulations of spheres and other manifolds. [ABSTRACT FROM AUTHOR]

We prove that for any integer k≥2$$ k\ge 2 $$ and ε>0$$ \varepsilon >0 $$, there is an integer ℓ0≥1$$ {\ell}_0\ge 1 $$ such that any k‐uniform hypergraph on n vertices with minimum codegree at least (1/2+ε)n$$ \left(1/2+\varepsilon \right)n $$ has a fractional decomposition into (tight) cycles of length ℓ$$ \ell $$ (ℓ$$ \ell $$‐cycles for short) whenever ℓ≥ℓ0$$ \ell \ge {\ell}_0 $$ and n is large in terms of ℓ$$ \ell $$. This is essentially tight. This immediately yields also approximate integral decompositions for these hypergraphs into ℓ$$ \ell $$‐cycles. Moreover, for graphs this even guarantees integral decompositions into ℓ$$ \ell $$‐cycles and solves a problem posed by Glock, Kühn, and Osthus. For our proof, we introduce a new method for finding a set of ℓ$$ \ell $$‐cycles such that every edge is contained in roughly the same number of ℓ$$ \ell $$‐cycles from this set by exploiting that certain Markov chains are rapidly mixing. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of K2n+1 into edge-disjoint copies of a given 2-factor. We show that this can be achieved for all large n. We actually prove a significantly more general result, which allows for decompositions into more general types of factors. In particular, this also resolves the Hamilton-Waterloo problem for large n. [ABSTRACT FROM AUTHOR]

A tight Hamilton cycle in a k-uniform hypergraph (k-graph) G is a cyclic ordering of the vertices of G such that every set of k consecutive vertices in the ordering forms an edge. Rödl, Ruciński and Szemerédi proved that for $k\ge 3$ , every k-graph on n vertices with minimum codegree at least $n/2+o(n)$ contains a tight Hamilton cycle. We show that the number of tight Hamilton cycles in such k-graphs is ${\exp(n\ln n-\Theta(n))}$. As a corollary, we obtain a similar estimate on the number of Hamilton ${\ell}$ -cycles in such k-graphs for all ${\ell\in\{0,\ldots,k-1\}}$ , which makes progress on a question of Ferber, Krivelevich and Sudakov. [ABSTRACT FROM AUTHOR]

In the 1960s, Erd Hos and Posa 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 = K3). 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. [ABSTRACT FROM AUTHOR]

A celebrated theorem of Pippenger states that any almost regular hypergraph with small codegrees has an almost perfect matching. We show that one can find such an almost perfect matching which is 'pseudorandom', meaning that, for instance, the matching contains as many edges from a given set of edges as predicted by a heuristic argument. [ABSTRACT FROM AUTHOR]

We prove a rainbow version of the blow‐up lemma of Komlós, Sárközy, and Szemerédi for μn‐bounded edge colorings. This enables the systematic study of rainbow embeddings of bounded degree spanning subgraphs. As one application, we show how our blow‐up lemma can be used to transfer the bandwidth theorem of Böttcher, Schacht, and Taraz to the rainbow setting. It can also be employed as a tool beyond the setting of μn‐bounded edge colorings. Kim, Kühn, Kupavskii, and Osthus exploit this to prove several rainbow decomposition results. Our proof methods include the strategy of an alternative proof of the blow‐up lemma given by Rödl and Ruciński, the switching method, and the partial resampling algorithm developed by Harris and Srinivasan. [ABSTRACT FROM AUTHOR]

For a collection G={G1,⋯,Gs} of not necessarily distinct graphs on the same vertex set V, a graph H with vertices in V is a G‐transversal if there exists a bijection ϕ:E(H)→[s] such that e∈E(Gϕ(e)) for all e∈E(H). We prove that for |V|=s⩾3 and δ(Gi)⩾s/2 for each i∈[s], there exists a G‐transversal that is a Hamilton cycle. This confirms a conjecture of Aharoni. We also prove an analogous result for perfect matchings. [ABSTRACT FROM AUTHOR]

A classical result of Komlós, Sárközy, and Szemerédi states that every n‐vertex graph with minimum degree at least (1/2 + o(1))n contains every n‐vertex tree with maximum degree O(n/logn). Krivelevich, Kwan, and Sudakov proved that for every n‐vertex graph Gα with minimum degree at least αn for any fixed α > 0 and every n‐vertex tree T with bounded maximum degree, one can still find a copy of T in Gα with high probability after adding O(n) randomly chosen edges to Gα. We extend the latter results to trees with (essentially) unbounded maximum degree; for a given no(1)≤Δ≤cn/logn and α > 0, we determine up to a constant factor the number of random edges that we need to add to an arbitrary n‐vertex graph with minimum degree αn in order to guarantee with high probability a copy of any fixed n‐vertex tree with maximum degree at most Δ. [ABSTRACT FROM AUTHOR]

We prove that if T1, ..., Tn is a sequence of bounded degree trees such that Ti has i vertices, then Kn has a decomposition into T1, ..., Tn. This shows that the tree packing conjecture of Gyárfás and Lehel from 1976 holds for all bounded degree trees (in fact, we can allow the first o.n/ trees to have arbitrary degrees). Similarly, we show that Ringel's conjecture from 1963 holds for all bounded degree trees. We deduce these results from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs. Our proofs involve Szemerédi's regularity lemma, results on Hamilton decompositions of robust expanders, random walks, iterative absorption as well as a recent blow-up lemma for approximate decompositions. [ABSTRACT FROM AUTHOR]

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 '-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. [ABSTRACT FROM AUTHOR]

A key feature of Simonovits' proof of the classic Erdőos--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. [ABSTRACT FROM AUTHOR]

We prove that for every graph, any vertex subset S, and given integers [ABSTRACT FROM AUTHOR]

For a fixed degree sequence $${\mathcal {D}}=(d_1,\ldots ,d_n)$$ , let $$G({\mathcal {D}})$$ be a uniformly chosen (simple) graph on $$\{1,\ldots ,n\}$$ where the vertex i has degree $$d_i$$ . In this paper we determine whether $$G({\mathcal {D}})$$ has a giant component with high probability, essentially imposing no conditions on $${\mathcal {D}}$$ . We simply insist that the sum of the degrees in $${\mathcal {D}}$$ which are not 2 is at least $$\lambda (n)$$ for some function $$\lambda $$ going to infinity with n. This is a relatively minor technical condition, and when $${\mathcal {D}}$$ does not satisfy it, both the probability that $$G({\mathcal {D}})$$ has a giant component and the probability that $$G({\mathcal {D}})$$ has no giant component are bounded away from 1. [ABSTRACT FROM AUTHOR]

We prove χ′s(G) ≤ 1.93 Δ(G)2 for graphs of sufficiently large maximum degree where χ′s(G) is the strong chromatic index of G. This improves an old bound of Molloy and Reed. As a by-product, we present a Talagrand-type inequality where we are allowed to exclude unlikely bad outcomes that would otherwise render the inequality unusable. [ABSTRACT FROM PUBLISHER]

We show the following for every sufficiently connected graph G, any vertex subset S of G, and given integer k: there are k disjoint odd cycles in G each containing a vertex of S or there is set X of at most [ABSTRACT FROM AUTHOR]

For a graph G, let vs(G) be the size of a largest induced matching of G. We prove that vs(G) ≥ n(G)/(⌈Δ/2⌇+1)(⌈Δ/2⌇+1) for every graph of sufficiently large maximum degree Δ and without isolated vertices. This bound is sharp. Moreover, there is a polynomial-time algorithm which computes induced matchings of the size stated above. [ABSTRACT FROM AUTHOR]

If $$G$$ is a claw-free Hamiltonian graph of order $$n$$ and maximum degree $$\Delta $$ with $$\Delta \ge 24$$ , then $$G$$ has cycles of at least $$\min \left\{ n,\left\lceil \frac{3}{2}\Delta \right\rceil \right\} -2$$ many different lengths. [ABSTRACT FROM AUTHOR]

For a graph G, let νs(G) be the strong matching number of G. We prove the sharp bound νs(G) ≥ 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, νs(G) ≥ m(G)/18 for such graphs and νs(G) ≥ 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 χ's(G) of a graph G is at most 5/4Δ(G)², since νs(G) ≥ m(G)/χ's(G) and n(G) ≥ 2m(G)/Δ(G). This bound is tight and the proof implies a polynomial time algorithm to find an induced matching of this size. [ABSTRACT FROM AUTHOR]

We characterize the graphs for which the independence number equals the packing number. As a consequence we obtain simple structural descriptions of the graphs for which (i) the distance- k -packing number equals the distance- 2 k -packing number, and (ii) the distance- k -matching number equals the distance- 2 k -matching number. This last result considerably simplifies and extends previous results of Cameron and Walker (2005). For positive integers k 1 and k 2 with k 1 < k 2 and ⌈ ( 3 k 2 + 1 ) / 2 ⌉ ≤ 2 k 1 + 1 , we prove that it is NP-hard to determine for a given graph whether its distance- k 1 -packing number equals its distance- k 2 -packing number. [ABSTRACT FROM AUTHOR]

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, Gn be the nth Cartesian power of G, αi be the number of vertices of degree i of G, λ be a positive real number, and Gnp be the graph obtained from Gn by deleting every edge independently with probability 1 − p. If ∑i αi(1 − p)i = λ 1/n , then limn→∞ ℙ[Gnp is connected] = exp(−λ). 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. [ABSTRACT FROM AUTHOR]

We give a complete characterization of mixed unit interval graphs, the intersection graphs of closed, open, and half-open unit intervals of the real line. This is a proper superclass of the well-known unit interval graphs. Our result solves a problem posed by Dourado, Le, Protti, Rautenbach, and Szwarcfiter (Mixed unit interval graphs, Discrete Math 312, 3357-3363 (2012)). [ABSTRACT FROM AUTHOR]

The Gallai graph Gal ( G ) of a graph G has the edges of G as its vertices, and two distinct vertices e and f of Gal ( G ) are adjacent in Gal ( G ) if the edges e and f of G are adjacent in G but do not span a triangle in G . In the present paper we characterize those graphs whose Gallai graphs are forests or trees, respectively. [ABSTRACT FROM AUTHOR]

Abstract: We prove that and for every triangle-free graph with maximum degree at most , where is the independence number and is the matching number of , respectively. These results are sharp for a graph on vertices. Furthermore we show for -free graphs, where is the chromatic number and is the clique number of , respectively. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]