An official website of the United States government
Abstract Given a family$$\mathcal{F}$$of bipartite graphs, theZarankiewicz number$$z(m,n,\mathcal{F})$$is the maximum number of edges in an$$m$$by$$n$$bipartite graph$$G$$that does not contain any member of$$\mathcal{F}$$as a subgraph (such$$G$$is called$$\mathcal{F}$$-free). For$$1\leq \beta \lt \alpha \lt 2$$, a family$$\mathcal{F}$$of bipartite graphs is$$(\alpha,\beta )$$-smoothif for some$$\rho \gt 0$$and every$$m\leq n$$,$$z(m,n,\mathcal{F})=\rho m n^{\alpha -1}+O(n^\beta )$$. Motivated by their work on a conjecture of Erdős and Simonovits on compactness and a classic result of Andrásfai, Erdős and Sós, Allen, Keevash, Sudakov and Verstraëte proved that for any$$(\alpha,\beta )$$-smooth family$$\mathcal{F}$$, there exists$$k_0$$such that for all odd$$k\geq k_0$$and sufficiently large$$n$$, any$$n$$-vertex$$\mathcal{F}\cup \{C_k\}$$-free graph with minimum degree at least$$\rho (\frac{2n}{5}+o(n))^{\alpha -1}$$is bipartite. In this paper, we strengthen their result by showing that for every real$$\delta \gt 0$$, there exists$$k_0$$such that for all odd$$k\geq k_0$$and sufficiently large$$n$$, any$$n$$-vertex$$\mathcal{F}\cup \{C_k\}$$-free graph with minimum degree at least$$\delta n^{\alpha -1}$$is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families$$\mathcal{F}$$consisting of the single graph$$K_{s,t}$$when$$t\gg s$$. We also prove an analogous result for$$C_{2\ell }$$-free graphs for every$$\ell \geq 2$$, which complements a result of Keevash, Sudakov and Verstraëte.
more »
« less
This content will become publicly available on July 7, 2026
Counting independent sets in structured graphs
Abstract Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container method which found numerous spectacular applications over the years. We consider the question of how many independent sets we can have in a graph under structural restrictions. We show that any$$n$$-vertex graph with independence number$$\alpha$$without$$bK_a$$as an induced subgraph has at most$$n^{O(1)} \cdot \alpha ^{O(\alpha )}$$independent sets. This substantially improves the trivial upper bound of$$n^{\alpha },$$whenever$$\alpha \le n^{o(1)}$$and gives a characterisation of graphs forbidding which allows for such an improvement. It is also in general tight up to a constant in the exponent since there exist triangle-free graphs with$$\alpha ^{\Omega (\alpha )}$$independent sets. We also prove that if one in addition assumes the ground graph is chi-bounded one can improve the bound to$$n^{O(1)} \cdot 2^{O(\alpha )}$$which is tight up to a constant factor in the exponent.
more »
« less
- Award ID(s):
- 2349013
- PAR ID:
- 10632323
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- Combinatorics, Probability and Computing
- ISSN:
- 0963-5483
- Page Range / eLocation ID:
- 1 to 10
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Let$$\mathrm {R}$$be a real closed field. Given a closed and bounded semialgebraic set$$A \subset \mathrm {R}^n$$and semialgebraic continuous functions$$f,g:A \rightarrow \mathrm {R}$$such that$$f^{-1}(0) \subset g^{-1}(0)$$, there exist an integer$$N> 0$$and$$c \in \mathrm {R}$$such that the inequality (Łojasiewicz inequality)$$|g(x)|^N \le c \cdot |f(x)|$$holds for all$$x \in A$$. In this paper, we consider the case whenAis defined by a quantifier-free formula with atoms of the form$$P = 0, P>0, P \in \mathcal {P}$$for some finite subset of polynomials$$\mathcal {P} \subset \mathrm {R}[X_1,\ldots ,X_n]_{\leq d}$$, and the graphs of$$f,g$$are also defined by quantifier-free formulas with atoms of the form$$Q = 0, Q>0, Q \in \mathcal {Q}$$, for some finite set$$\mathcal {Q} \subset \mathrm {R}[X_1,\ldots ,X_n,Y]_{\leq d}$$. We prove that the Łojasiewicz exponent in this case is bounded by$$(8 d)^{2(n+7)}$$. Our bound depends ondandnbut is independent of the combinatorial parameters, namely the cardinalities of$$\mathcal {P}$$and$$\mathcal {Q}$$. The previous best-known upper bound in this generality appeared inP. Solernó, Effective Łojasiewicz Inequalities in Semi-Algebraic Geometry, Applicable Algebra in Engineering, Communication and Computing (1991)and depended on the sum of degrees of the polynomials defining$$A,f,g$$and thus implicitly on the cardinalities of$$\mathcal {P}$$and$$\mathcal {Q}$$. As a consequence, we improve the current best error bounds for polynomial systems under some conditions. Finally, we prove a version of Łojasiewicz inequality in polynomially bounded o-minimal structures. We prove the existence of a common upper bound on the Łojasiewicz exponent for certain combinatorially defined infinite (but not necessarily definable) families of pairs of functions. This improves a prior result of Chris Miller (C. Miller, Expansions of the real field with power functions, Ann. Pure Appl. Logic (1994)).more » « less
-
Abstract Theq-colour Ramsey number of ak-uniform hypergraphHis the minimum integerNsuch that anyq-colouring of the completek-uniform hypergraph onNvertices contains a monochromatic copy ofH. The study of these numbers is one of the central topics in Combinatorics. In 1973, Erdős and Graham asked to maximise the Ramsey number of a graph as a function of the number of its edges. Motivated by this problem, we study the analogous question for hypergaphs. For fixed$$k \ge 3$$and$$q \ge 2$$we prove that the largest possibleq-colour Ramsey number of ak-uniform hypergraph withmedges is at most$$\mathrm{tw}_k(O(\sqrt{m})),$$where tw denotes the tower function. We also present a construction showing that this bound is tight for$$q \ge 4$$. This resolves a problem by Conlon, Fox and Sudakov. They previously proved the upper bound for$$k \geq 4$$and the lower bound for$$k=3$$. Although in the graph case the tightness follows simply by considering a clique of appropriate size, for higher uniformities the construction is rather involved and is obtained by using paths in expander graphs.more » « less
-
Abstract What proportion of integers$$n \leq N$$may be expressed as$$x^2 + dy^2$$for some$$d \leq \Delta $$, with$$x,y$$integers? Writing$$\Delta = (\log N)^{\log 2} 2^{\alpha \sqrt {\log \log N}}$$for some$$\alpha \in (-\infty , \infty )$$, we show that the answer is$$\Phi (\alpha ) + o(1)$$, where$$\Phi $$is the Gaussian distribution function$$\Phi (\alpha ) = \frac {1}{\sqrt {2\pi }} \int ^{\alpha }_{-\infty } e^{-x^2/2} dx$$. A consequence of this is a phase transition: Almost none of the integers$$n \leq N$$can be represented by$$x^2 + dy^2$$with$$d \leq (\log N)^{\log 2 - \varepsilon }$$, but almost all of them can be represented by$$x^2 + dy^2$$with$$d \leq (\log N)^{\log 2 + \varepsilon}\kern-1.5pt$$.more » « less
-
Abstract For a subset$$A$$of an abelian group$$G$$, given its size$$|A|$$, its doubling$$\kappa =|A+A|/|A|$$, and a parameter$$s$$which is small compared to$$|A|$$, we study the size of the largest sumset$$A+A'$$that can be guaranteed for a subset$$A'$$of$$A$$of size at most$$s$$. We show that a subset$$A'\subseteq A$$of size at most$$s$$can be found so that$$|A+A'| = \Omega (\!\min\! (\kappa ^{1/3},s)|A|)$$. Thus, a sumset significantly larger than the Cauchy–Davenport bound can be guaranteed by a bounded size subset assuming that the doubling$$\kappa$$is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets$$A,B$$of$$\mathbb{F}_p$$of size at most$$\alpha p$$for an appropriate constant$$\alpha \gt 0$$, one only needs three elements$$b_1,b_2,b_3\in B$$to guarantee$$|A+\{b_1,b_2,b_3\}|\ge |A|+|B|-1$$. Allowing the use of larger subsets$$A'$$, we show that for sets$$A$$of bounded doubling, one only needs a subset$$A'$$with$$o(|A|)$$elements to guarantee that$$A+A'=A+A$$. We also address another conjecture and a question raised by Bollobás, Leader and Tiba on high-dimensional analogues and sets whose sumset cannot be saturated by a bounded size subset.more » « less
