BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We determine the maximum number of copies of Ks,s in a C2s+2-free n-vertex graph for all integers s≥2 and sufficiently large n. Moreover, for s∈{2,3} and any integer n we obtain the maximum number of cycles of length 2s in an n-vertex C2s+2-free bipartite graph.
A classical extremal, or Turán-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.
We generalize several classical theorems in extremal combinatorics by replacing a global constraint with an inequality which holds for all objects in a given class. In particular we obtain generalizations of Turán's theorem, the Erdős-Gallai theorem, the LYM-inequality, the Erdős-Ko-Rado theorem and the Erdős-Szekeres theorem on sequences.
In this paper we disprove a conjecture of Lidický and Murphy about the number of copies of a given graph in a Kr-free graph and give an alternative general conjecture. We also prove an asymptotically tight bound on the number of copies of any bipartite graph of radius at most 2 in a triangle-free graph.
We resolve a conjecture of Cox and Martin by determining asymptotically for every k≥2 the maximum number of copies of C2k in an n-vertex planar graph.
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 ℓ.
We consider edge decompositions of the n-dimensional hypercube Qn into isomorphic copies of a given graph H. While a number of results are known about decomposing Qn 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, ℓ<2n and ℓ divides the number of edges of Qn, then the path of length ℓ decomposes Qn. Tapadia et al.\ proved that any path of length 2mn, where 2m<n, satisfying these conditions decomposes Qn. Here, we make progress toward resolving Erde's conjecture by showing that cycles of certain lengths up to 2n+1/n decompose Qn. As a consequence, we show that Qn can be decomposed into copies of any path of length at most 2n/n dividing the number of edges of Qn, thereby settling Erde's conjecture up to a linear factor.
In a generalized Turán problem, we are given graphs H and F and seek to maximize the number of copies of H in an F-free graph of order n. We consider generalized Turán 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 obtain 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.
In this note we show that the maximum number of edges in a 3-uniform hypergraph without a Berge cycle of length four is at most (1+o(1))10n3/2. This improves earlier estimates by Győri and Lemons and by Füredi and Özkahya.
In 1964, Erdős, Hajnal and Moon introduced a saturation version of Turán's classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a Kr-free, n-vertex graph with the property that the addition of any further edge yields a copy of Kr. We consider analogues of this problem in other settings. We prove a saturation version of the Erdős-Szekeres theorem about monotone subsequences and saturation versions of some Ramsey-type theorems on graphs and Dilworth-type theorems on posets. We also consider semisaturation problems, wherein we allow the family to have the forbidden configuration, but insist that any addition to the family yields a new copy of the forbidden configuration. In this setting, we prove a semisaturation version of the Erdős-Szekeres theorem on convex k-gons, as well as multiple semisaturation theorems for sequences and posets.
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 r+1n(k−1) 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.
Let La(n,P) be the maximum size of a family of subsets of [n]={1,2,...,n} not containing P as a (weak) subposet, and let h(P) be the length of a longest chain in P. The best known upper bound for La(n,P) in terms of ∣P∣ and h(P) is due to Chen and Li, who showed that La(n,P)≤m+11(∣P∣+21(m2+3m−2)(h(P)−1)−1)(⌊n/2⌋n) for any fixed m≥1. In this paper we show that La(n,P)≤2k−11(∣P∣+(3k−5)2k−2(h(P)−1)−1)(⌊n/2⌋n) for any fixed k≥2, improving the best known upper bound. By choosing k appropriately, we obtain that La(n,P)=O(h(P)log2(h(P)∣P∣+2))(⌊n/2⌋n) as a corollary, which we show is best possible for general P. We also give a different proof of this corollary by using bounds for generalized diamonds. We also show that the Lubell function of a family of subsets of [n] not containing P as an induced subposet is O(nc) for every c>21.
We consider several classes of intersection graphs of line segments in the plane and prove new equality and separation results between those classes. In particular, we show that: (1) intersection graphs of grounded segments and intersection graphs of downward rays form the same graph class, (2) not every intersection graph of rays is an intersection graph of downward rays, and (3) not every intersection graph of rays is an outer segment graph. The first result answers an open problem posed by Cabello and Jejčič. The third result confirms a conjecture by Cabello. We thereby completely elucidate the remaining open questions on the containment relations between these classes of segment graphs. We further characterize the complexity of the recognition problems for the classes of outer segment, grounded segment, and ray intersection graphs. We prove that these recognition problems are complete for the existential theory of the reals. This holds even if a 1-string realization is given as additional input.
Let G be a graph with a distribution of pebbles on its vertices. A pebbling move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. The optimal pebbling number of G is the smallest number of pebbles which can placed on the vertices of G such that, for any vertex v of G, there is a sequence of pebbling moves resulting in at least one pebble on v. We determine the optimal pebbling number for several classes of induced subgraphs of the square grid, which we call staircase graphs.
A classical theorem of De Bruijn and Erdős asserts that any noncollinear set of n points in the plane determines at least n distinct lines. We prove that an analogue of this theorem holds for graphs. Restricting our attention to comparability graphs, we obtain a version of the De Bruijn-Erdős theorem for partially ordered sets (posets). Moreover, in this case, we have an improved bound on the number of lines depending on the height of the poset. The extremal configurations are also determined.
We introduce a method of decomposing the family of intervals along a cyclic permutation into chains to determine the size of the largest family of subsets of [n]:={1,2,...,n} not containing one or more given posets as a subposet. De Bonis, Katona and Swanepoel determined the size of the largest butterfly-free family. We strengthen this result by showing that, for certain posets containing the butterfly poset as a subposet, the same bound holds. We also obtain the corresponding LYM-type inequalities.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.