388 research outputs found
On subgraphs of C-2k-free graphs and a problem of Kuhn and Osthus
No full textLet c denote the largest constant such that every C-6-free graph G contains a bipartite and C-4-free subgraph having a fraction c of edges of G. Gyori, Kensell and Tompkins showed that 3/8 0, and any integer k >= 2, there is a C-2k-free graph G' which does not contain a bipartite subgraph of girth greater than 2k with more than a fraction (1 - 1/2(2k-2)) 2/2k - 1 (1 + epsilon) of the edges of G'. There also exists a C-2k-free graph G '' which does not contain a bipartite and C-4-free subgraph with more than a fraction (1 - 1/2(k-1)) 1/k - 1 (1 + epsilon) of the edges of G ''. One of our proofs uses the following statement, which we prove using probabilistic ideas, generalizing a theorem of Erdos. For any epsilon > 0, and any integers a, b, k >= 2, there exists an a-uniform hypergraph H of girth greater than k which does not contain any b-colourable subhypergraph with more than a fraction (1 - 1/b(a-1)) (1+e) of the hyperedges of H. We also prove further generalizations of this theorem. In addition, we give a new and very short proof of a result of Kuhn and Osthus, which states that every bipartite C-2k-free graph G contains a C-4-free subgraph with at least a fraction 1/(k - 1) of the edges of G. We also answer a question of Kuhn and Osthus about C-2k-free graphs obtained by pasting together C-2l's (with k > l >= 3).LCBI
Generalized Turan densities in the hypercube
No full textA classical extremal, or Turan-type problem asks to determine ex(G, H), the largest number of edges in a subgraph of a graph G which does not contain a subgraph isomorphic to H. Alon and Shikhelman introduced the so-called generalized extremal number ex(G, T, H), defined to be the maximum number of subgraphs isomorphic to T in a subgraph of G that contains no subgraphs isomorphic to H. In this paper we investigate the case when G = Qn, the hypercube of dimension n, and T and H are smaller hypercubes or cycles. (c) 2022 Elsevier B.V. All rights reserved
Long path and cycle decompositions of even hypercubes
No full textWe consider edge decompositions of the n-dimensional hypercube Q into isomorphic copies of a given graph H. While a number of results are known about decomposing Q into graphs from various classes, the simplest cases of paths and cycles of a given length are far from being understood. A conjecture of Erde asserts that if n is even, ℓ < 2 and ℓ divides the number of edges of Q, then the path of length ℓ decomposes Q. Tapadia et al. proved that any path of length 2n, where 2 < n, satisfying these conditions decomposes Q. Here, we make progress toward resolving Erde’s conjecture by showing that cycles of certain lengths up to 2/n decompose Q. As a consequence, we show that Q can be decomposed into copies of any path of length at most 2/n dividing the number of edges of Q, thereby settling Erde’s conjecture up to a linear factor
Generalized planar Turán numbers
No full textIn a generalized Turán problem, we are given graphs H and F and seek to maximize the number of copies of H in an n-vertex graph not containing F as a subgraph. We consider generalized Turan problems where the host graph is planar. In particular, we obtain the order of magnitude of the maximum number of copies of a fixed tree in a planar graph containing no even cycle of length at most 2£, for all £, £ ^ 1. We also determine the order of magnitude of the maximum number of cycles of a given length in a planar C4-free graph. An exact result is given for the maximum number of 5-cycles in a C4-free planar graph. Multiple conjectures are also introduced.11Nsciescopu
Ramsey numbers of Boolean lattices
No full textThe poset Ramsey number (Formula presented.) is the smallest integer (Formula presented.) such that any blue–red coloring of the elements of the Boolean lattice (Formula presented.) has a blue-induced copy of (Formula presented.) or a red-induced copy of (Formula presented.). The weak poset Ramsey number (Formula presented.) is defined analogously, with weak copies instead of induced copies. It is easy to see that (Formula presented.). Axenovich and Walzer (Order 34 (2017), 287–298) showed that (Formula presented.). Recently, Lu and Thompson (Order 39 (2022), no. 2, 171–185) improved the upper bound to (Formula presented.). In this paper, we solve this problem asymptotically by showing that (Formula presented.). In the diagonal case, Cox and Stolee (Order 35 (2018), no. 3, 557–579) proved (Formula presented.) using a probabilistic construction. In the induced case, Bohman and Peng (arXiv preprint arXiv:2102.00317, 2021) showed (Formula presented.) using an explicit construction. Improving these results, we show that (Formula presented.) for all (Formula presented.) and large (Formula presented.) by giving an explicit construction; in particular, we prove that (Formula presented.). © 2023 The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence
The maximum number of copies in -free graphs
No full textGeneralizing Tur\'an's classical extremal problem, Alon and Shikhelman
investigated the problem of maximizing the number of copies in an -free
graph, for a pair of graphs and . Whereas Alon and Shikhelman were
primarily interested in determining the order of magnitude for large classes of
graphs , we focus on the case when and are paths, where we find
asymptotic and in some cases exact results. We also consider other structures
like stars and the set of cycles of length at least , where we derive
asymptotically sharp estimates. Our results generalize well-known extremal
theorems of Erd\H{o}s and Gallai
Inverse Turán numbers
No full text© 2021 Elsevier B.V.For given graphs G and F, the Turán number ex(G,F) is defined to be the maximum number of edges in an F-free subgraph of G. Foucaud, Krivelevich and Perarnau and later independently Briggs and Cox introduced a dual version of this problem wherein for a given number k, one maximizes the number of edges in a host graph G for which ex(G,H)<k. Addressing a problem of Briggs and Cox, we determine the asymptotic value of the inverse Turán number of the paths of length 4 and 5 and provide an improved lower bound for all paths of even length. Moreover, we obtain bounds on the inverse Turán number of even cycles giving improved bounds on the leading coefficient in the case of C4. Finally, we give multiple conjectures concerning the asymptotic value of the inverse Turán number of C4 and Pℓ, suggesting that in the latter problem the asymptotic behavior depends heavily on the parity of ℓ.11Nsciescopu
Large homogeneous subgraphs in bipartite graphs with forbidden induced subgraphs
No full textFor a bipartite graph G, let h similar to ( G ) be the largest t such that either G contains K t , t, a complete bipartite subgraph with parts of size t, or the bipartite complement of G contains K t , t as a subgraph. For a class of graphs F, let h similar to ( F ) = min { h similar to ( G ) : G is an element of F }. We say that a bipartite graph H is strongly acyclic if neither H nor its bipartite complement contains a cycle. By Forb ( n , H ) we denote the set of bipartite graphs with parts of size n, which do not contain H as an induced bipartite subgraph respecting the sides. One can easily show that h similar to ( Forb ( n , H ) ) = O ( n 1 - epsilon ) for a positive epsilon if H is not strongly acyclic. Here we ask whether h similar to ( Forb ( n , H ) ) is linear in n for any strongly acyclic graph H. We answer this question in the positive for all but four strongly acyclic graphs. We do not address this question for the remaining four graphs in this paper.11Nsciescopu
Turán numbers of Berge trees
No full text© 2022 Elsevier B.V.A classical conjecture of Erdős and Sós asks to determine the Turán number of a tree. We consider variants of this problem in the settings of hypergraphs and multi-hypergraphs. In particular, for all k and r, with r≥k(k−2), we show that any r-uniform hypergraph H with more than [Formula presented] hyperedges contains a Berge copy of any tree with k edges different from the k-edge star. This bound is sharp when r+1 divides n and for such values of n we determine the extremal hypergraphs.11Nsciescopu
Uniformity thresholds for the asymptotic size of extremal Berge-F-free hypergraphs
No full text© 2020 Elsevier Ltd. Let F=(U,E) be a graph and H=(V,E) be a hypergraph. We say that H contains a Berge-F if there exist injections ψ:U→V and φ:E→E such that for every e={u,v}∈E, {ψ(u),ψ(v)}⊂φ(e). Let exr(n,F) denote the maximum number of hyperedges in an r-uniform hypergraph on n vertices which does not contain a Berge-F. For small enough r and non-bipartite F, exr(n,F)=Ω(n2); we show that for sufficiently large r, exr(n,F)=o(n2). Let th(F)=min{r0:exr(n,F)=o(n2)for allr≥r0}. We show lower and upper bounds for th(F), the uniformity threshold of F. In particular, we obtain that th(△)=5, improving a result of Győri (2006). We also study the analogous problem for linear hypergraphs. Let exr L(n,F) denote the maximum number of hyperedges in an r-uniform linear hypergraph on n vertices which does not contain a Berge-F, and let the linear uniformity threshold thL(F)=min{r0:exr L(n,F)=o(n2)for allr≥r0}. We show that thL(F) is equal to the chromatic number of F11Nsciescopu
- …
