Journal: Journal of Combinatorial Theory, Series B

Abbreviation

Comb. Theory, Ser. B

Publisher

Elsevier

Journal Volumes

ISSN

0095-8956
1096-0902

Description

Filters

Reset filters

Search Results

Publications 1 - 10 of 55
  • Comparable pairs in families of sets
    Item type: Journal Article
    Alon, Noga; Das, Shagnik; Glebov, Roman; et al. (2015)
    Journal of Combinatorial Theory, Series B
  • On the chromatic number of random graphs
    Item type: Journal Article
    Coja-Oghlan, Amin; Panagiotou, Konstantinos; Steger, Angelika (2008)
    Journal of Combinatorial Theory, Series B
  • The Hamilton space of pseudorandom graphs
    Item type: Journal Article
    Christoph , Micha; Nenadov , Rajko; Petrova , Kalina (2026)
    Journal of Combinatorial Theory, Series B
    We show that if n is odd and p≥Clog⁡n/n, then with high probability Hamilton cycles in G(n,p) span its cycle space. More generally, we show this holds for a class of graphs satisfying certain natural pseudorandom properties. The proof is based on a novel idea of parity-switchers, which can be thought of as analogues of absorbers in the context of cycle spaces. As another application of our method, we show that Hamilton cycles in a near-Dirac graph G, that is, a graph G with odd n vertices and minimum degree n/2+C for sufficiently large constant C, span its cycle space.
  • Small subgraphs in random graphs and the power of multiple choices
    Item type: Journal Article
    Muetze, Torsten; Spoehel, Reto; Thomas, Henning (2011)
    Journal of Combinatorial Theory, Series B
  • An algorithmic framework for obtaining lower bounds for random Ramsey problems
    Item type: Journal Article
    Nenadov, Rajko; Person, Yury; Škorić, Nemanja; et al. (2017)
    Journal of Combinatorial Theory, Series B
  • Long cycles, heavy cycles and cycle decompositions in digraphs
    Item type: Journal Article
    Knierim, Charlotte; Larcher, Maxime; Martinsson, Anders; et al. (2021)
    Journal of Combinatorial Theory, Series B
    Hajós conjectured in 1968 that every Eulerian n-vertex graph can be decomposed into at most ⌊(n−1)/2⌋ edge-disjoint cycles. This has been confirmed for some special graph classes, but the general case remains open. In a sequence of papers by Bienia and Meyniel (1986) [1], Dean (1986) [7], and Bollobás and Scott (1996) [2] it was analogously conjectured that every directed Eulerian graph can be decomposed into O(n) cycles. In this paper, we show that every directed Eulerian graph can be decomposed into O(nlogΔ) disjoint cycles, thus making progress towards the conjecture by Bollobás and Scott. Our approach is based on finding heavy cycles in certain edge-weightings of directed graphs. As a further consequence of our techniques, we prove that for every edge-weighted digraph in which every vertex has out-weight at least 1, there exists a cycle with weight at least Ω(loglogn/logn), thus resolving a question by Bollobás and Scott.
  • A problem of Erdős on the minimum number of k-cliques
    Item type: Journal Article
    Das, Shagnik; Huang, Hao; Ma, Jie; et al. (2013)
    Journal of Combinatorial Theory, Series B
  • Ordered Ramsey numbers
    Item type: Journal Article
    Conlon, David; Fox, Jacob; Lee, Choongbum; et al. (2017)
    Journal of Combinatorial Theory, Series B
  • The Turan number of blow-ups of trees
    Item type: Journal Article
    Grzesik, Andrzej; Janzer, Oliver; Nagy, Zoltan Lorant (2022)
    Journal of Combinatorial Theory, Series B
    A conjecture of Erdos from 1967 asserts that any graph on n vertices which does not contain a fixed r-degenerate bipartite graph F has at most Cn(2-1/r) edges, where C is a constant depending only on F. We show that this bound holds for a large family of r-degenerate bipartite graphs, including all r-degenerate blow-ups of trees. Our results generalise many previously proven cases of the Erdos conjecture, including the related results of Furedi and Alon, Krivelevich and Sudakov. Our proof uses supersaturation and a random walk on an auxiliary graph.Crown Copyright (C) 2022 Published by Elsevier Inc.
  • On sets not belonging to algebras and rainbow matchings in graphs
    Item type: Journal Article
    Clemens, Dennis; Ehrenmueler, Julia; Pokrovskiy, Alexey (2017)
    Journal of Combinatorial Theory, Series B
Publications 1 - 10 of 55