Journal: Journal of Combinatorial Theory, Series B

Abbreviation

Comb. Theory, Ser. B

Publisher

Academic Press

Journal Volumes

ISSN

0095-8956

Description

Filters

2022 - 20238
Reset filters

Search Results

Publications 1 - 8 of 8
  • A new bound for the Brown–Erdős–Sós problem
    Item type: Journal Article
    Conlon, David; Gishboliner, Lior; Levanzov, Yevgeny; et al. (2023)
    Journal of Combinatorial Theory, Series B
    Let f(n,v,e) denote the maximum number of edges in a 3-uniform hypergraph not containing e edges spanned by at most v vertices. One of the most influential open problems in extremal combinatorics then asks, for a given number of edges e≥3, what is the smallest integer d=d(e) such that f(n,e+d,e)=o(n2)? This question has its origins in work of Brown, Erdős and Sós from the early 70's and the standard conjecture is that d(e)=3 for every e≥3. The state of the art result regarding this problem was obtained in 2004 by Sárközy and Selkow, who showed that f(n,e+2+⌊log2e⌋,e)=o(n2). The only improvement over this result was a recent breakthrough of Solymosi and Solymosi, who improved the bound for d(10) from 5 to 4. We obtain the first asymptotic improvement over the Sárközy–Selkow bound, showing that f(n,e+O(loge/logloge),e)=o(n2).
  • Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant
    Item type: Journal Article
    Steiner, Raphael (2022)
    Journal of Combinatorial Theory, Series B
    Hadwiger's conjecture states that every Kt-minor free graph is (t−1)-colorable. A qualitative strengthening of this conjecture raised by Gerards and Seymour, known as the Odd Hadwiger's conjecture, states similarly that every graph with no odd Kt-minor is (t−1)-colorable. For both conjectures, their asymptotic relaxations remain open, i.e., whether an upper bound on the chromatic number of the form Ct for some constant C>0 exists. We show that if every graph without a Kt-minor is f(t)-colorable, then every graph without an odd Kt-minor is 2f(t)-colorable. As a direct corollary, we present a new state of the art bound O(tloglogt) for the chromatic number of graphs with no odd Kt-minor. Moreover, the short proof of our result substantially simplifies the proofs of all the previous asymptotic bounds for the chromatic number of odd Kt-minor free graphs established in a sequence of papers during the last 12 years.
  • Ramsey number of 1-subdivisions of transitive tournaments
    Item type: Journal Article
    Draganić, Nemanja; Munhá Correia, David; Sudakov, Benny; et al. (2022)
    Journal of Combinatorial Theory, Series B
    The study of problems concerning subdivisions of graphs has a rich history in extremal combinatorics. Confirming a conjecture of Burr and Erdős, Alon proved in 1994 that subdivided graphs have linear Ramsey numbers. Later, Alon, Krivelevich and Sudakov showed that every n-vertex graph with at least εn2 edges contains a 1-subdivision of the complete graph on cεn vertices, resolving another old conjecture of Erdős. In this paper we consider the directed analogue of these problems and show that every tournament on at least (2+o(1))k2 vertices contains the 1-subdivision of a transitive tournament on k vertices. This is optimal up to a multiplicative factor of 4 and confirms a conjecture of Girão, Popielarz and Snyder.
  • Dichromatic number and forced subdivisions
    Item type: Journal Article
    Gishboliner, Lior; Steiner, Raphael; Szabó, Tibor (2022)
    Journal of Combinatorial Theory, Series B
    We investigate bounds on the dichromatic number of digraphs which avoid a fixed digraph as a topological minor. For a digraph F, denote by maderχ→(F) the smallest integer k such that every k-dichromatic digraph contains a subdivision of F. As our first main result, we prove that if F is an orientation of a cycle then maderχ→(F)=v(F). This settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura and Thomassé. We also extend this result to the more general class of orientations of cactus graphs, and to bioriented forests. Our second main result is that maderχ→(F)=4 for every tournament F of order 4. This is an extension of the classical result by Dirac that 4-chromatic graphs contain a K4-subdivision to directed graphs.
  • Ramsey numbers of semi-algebraic and semi-linear hypergraphs
    Item type: Journal Article
    Jin, Zhihan; Tomon, István (2023)
    Journal of Combinatorial Theory, Series B
    An r-uniform hypergraph H is semi-algebraic of complexity t=(d,D,m) if the vertices of H correspond to points in Rd and the edges of H are determined by the sign-pattern of m degree-D polynomials. Semi-algebraic hypergraphs of bounded complexity provide a general framework for studying geometrically defined hypergraphs. The much-studied semi-algebraic Ramsey number Rrt(s,n) denotes the smallest N such that every r-uniform semi-algebraic hypergraph of complexity t on N vertices contains either a clique of size s or an independent set of size n. Conlon, Fox, Pach, Sudakov and Suk proved that Rrt(n,n)n(logn)1/3−o(1) for some complexity t. In addition, motivated by results of Bukh and Matoušek and Basit, Chernikov, Starchenko, Tao and Tran, we study the complexity of the Ramsey problem when the defining polynomials are linear, that is, when D=1. In particular, we prove that Rrd,1,m(n,n)≤2O(n4r2m2), while from below, we establish Rr1,1,1(n,n)≥2Ω(n⌊r/2⌋−1).
  • Turán problems for edge-ordered graphs
    Item type: Journal Article
    Gerbner, Dániel; Methuku, Abhishek; Nagy, Dániel T.; et al. (2023)
    Journal of Combinatorial Theory, Series B
    In this paper we initiate a systematic study of the Turán problem for edge-ordered graphs. A simple graph is called edge-ordered if its edges are linearly ordered. This notion allows us to study graphs (and in particular their maximum number of edges) when a subgraph is forbidden with a specific edge-order but the same underlying graph may appear with a different edge-order. We prove an Erdős-Stone-Simonovits-type theorem for edge-ordered graphs—we identify the relevant parameter for the Turán number of an edge-ordered graph and call it the order chromatic number. We establish several important properties of this parameter. We also study Turán numbers of edge-ordered paths, star forests and the cycle of length four. We make strong connections to Davenport-Schinzel theory, the theory of forbidden submatrices, and show an application in discrete geometry.
  • Discrepancies of spanning trees and Hamilton cycles
    Item type: Journal Article
    Gishboliner, Lior; Krivelevich, Michael; Michaeli, Peleg (2022)
    Journal of Combinatorial Theory, Series B
    We study the multicolour discrepancy of spanning trees and Hamilton cycles in graphs. As our main result, we show that under very mild conditions, the r-colour spanning-tree discrepancy of a graph G is equal, up to a constant, to the minimum s such that G can be separated into r equal parts by deleting s vertices. This result arguably resolves the question of estimating the spanning-tree discrepancy in essentially all graphs of interest. In particular, it allows us to immediately deduce as corollaries most of the results that appear in a recent paper of Balogh, Csaba, Jing and Pluhár, proving them in wider generality and for any number of colours. We also obtain several new results, such as determining the spanning-tree discrepancy of the hypercube. For the special case of graphs possessing certain expansion properties, we obtain exact asymptotic bounds. We also study the multicolour discrepancy of Hamilton cycles in graphs of large minimum degree, showing that in any r-colouring of the edges of a graph with n vertices and minimum degree at least [Formula presented], there must exist a Hamilton cycle with at least [Formula presented] edges in some colour. This extends a result of Balogh et al., who established the case r=2. The constant [Formula presented] in this result is optimal; it cannot be replaced by any smaller constant.
  • An average degree condition for independent transversals
    Item type: Journal Article
    Glock, Stefan; Sudakov, Benny (2022)
    Journal of Combinatorial Theory, Series B
    In 1994, Erdős, Gyárfás and Łuczak posed the following problem: given disjoint vertex sets V1,…,Vn of size k, with exactly one edge between any pair Vi,Vj, how large can n be such that there will always be an independent transversal? They showed that the maximal n is at most (1+o(1))k2, by providing an explicit construction with these parameters and no independent transversal. They also proved a lower bound which is smaller by a 2e-factor. In this paper, we solve this problem by showing that their upper bound construction is best possible: if n≤(1−o(1))k2, there will always be an independent transversal. In fact, this result is a very special case of a much more general theorem which concerns independent transversals in arbitrary partite graphs that are ‘locally sparse’, meaning that the maximum degree between each pair of parts is relatively small. In this setting, Loh and Sudakov provided a global maximum degree condition for the existence of an independent transversal. We show that this can be relaxed to an average degree condition. We can also use our new theorem to establish tight bounds for a more general version of the Erdős–Gyárfás–Łuczak problem and solve a conjecture of Yuster from 1997. This exploits a connection to the Turán numbers of complete bipartite graphs, which might be of independent interest.
Publications 1 - 8 of 8