Search for: All records

Abstract The classical Hadwiger conjecture dating back to 1940s states that any graph of chromatic number at leastrhas the clique of orderras a minor. Hadwiger's conjecture is an example of a well‐studied class of problems asking how large a clique minor one can guarantee in a graph with certain restrictions. One problem of this type asks what is the largest size of a clique minor in a graph onnvertices of independence numberat mostr. If true Hadwiger's conjecture would imply the existence of a clique minor of order. Results of Kühn and Osthus and Krivelevich and Sudakov imply that if one assumes in addition thatGisH‐free for some bipartite graphHthen one can find a polynomially larger clique minor. This has recently been extended to triangle‐free graphs by Dvořák and Yepremyan, answering a question of Norin. We complete the picture and show that the same is true for arbitrary graphH, answering a question of Dvořák and Yepremyan. In particular, we show that any‐free graph has a clique minor of order, for some constantdepending only ons. The exponent in this result is tight up to a constant factor in front of theterm. 

Abstract The list Ramsey number , recently introduced by Alon, Bucić, Kalvari, Kuperwasser, and Szabó, is a list‐coloring variant of the classical Ramsey number. They showed that if is a fixed ‐uniform hypergraph that is not ‐partite and the number of colors goes to infinity, . We prove that if and only if is not ‐partite. 

Abstract We study quantitative relationships between the triangle removal lemma and several of its variants. One such variant, which we call the triangle-free lemma , states that for each $$\epsilon>0$$ there exists M such that every triangle-free graph G has an $$\epsilon$$ -approximate homomorphism to a triangle-free graph F on at most M vertices (here an $$\epsilon$$ -approximate homomorphism is a map $$V(G) \to V(F)$$ where all but at most $$\epsilon \left\lvert{V(G)}\right\rvert^2$$ edges of G are mapped to edges of F ). One consequence of our results is that the least possible M in the triangle-free lemma grows faster than exponential in any polynomial in $$\epsilon^{-1}$$ . We also prove more general results for arbitrary graphs, as well as arithmetic analogues over finite fields, where the bounds are close to optimal. 

Abstract We prove several different anti-concentration inequalities for functions of independent Bernoulli-distributed random variables. First, motivated by a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn, we prove some “Poisson-type” anti-concentration theorems that give bounds of the form 1/ e + o (1) for the point probabilities of certain polynomials. Second, we prove an anti-concentration inequality for polynomials with nonnegative coefficients which extends the classical Erdős–Littlewood–Offord theorem and improves a theorem of Meka, Nguyen and Vu for polynomials of this type. As an application, we prove some new anti-concentration bounds for subgraph counts in random graphs.