skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: On the order of the classical Erdős–Rogers functions
Abstract For an integer , the Erdős–Rogers function is the maximum integer such that every ‐vertex ‐free graph has a ‐free induced subgraph with vertices. It is known that for all , as . In this paper, we show that for all , there exists a constant such thatThis improves previous bounds of order by Dudek, Retter and Rödl and answers a question of Warnke.  more » « less
Award ID(s):
2347832
PAR ID:
10591670
Author(s) / Creator(s):
;
Publisher / Repository:
Open Access
Date Published:
Journal Name:
Bulletin of the London Mathematical Society
Volume:
57
Issue:
2
ISSN:
0024-6093
Page Range / eLocation ID:
582 to 598
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract We show that defines a birational map and has no fixed part for some bounded positive integermfor any ‐lc surfaceXsuch that is big and nef. For every positive integer , we construct a sequence of projective surfaces , such that is ample, for everyi, , and for any positive integerm, there existsisuch that has nonzero fixed part. These results answer the surface case of a question of Xu. 
    more » « less
  2. Abstract Let and be natural numbers greater or equal to 2. Let be a homogeneous polynomial in variables of degree with integer coefficients , where denotes the inner product, and denotes the Veronese embedding with . Consider a variety in , defined by . In this paper, we examine a set of integer vectors , defined bywhere is a nonsingular form in variables of degree with for some constant depending at most on and . Suppose has a nontrivial integer solution. We confirm that the proportion of integer vectors in , whose associated equation  is everywhere locally soluble, converges to a constant as . Moreover, for each place of , if there exists a nonzero such that and the variety in admits a smooth ‐point, the constant is positive. 
    more » « less
  3. Abstract Consider averages along the prime integers ℙ given by {\mathcal{A}_N}f(x) = {N^{ - 1}}\sum\limits_{p \in \mathbb{P}:p \le N} {(\log p)f(x - p).} These averages satisfy a uniform scale-free ℓ p -improving estimate. For all 1 < p < 2, there is a constant C p so that for all integer N and functions f supported on [0, N ], there holds {N^{ - 1/p'}}{\left\| {{\mathcal{A}_N}f} \right\|_{\ell p'}} \le {C_p}{N^{ - 1/p}}{\left\| f \right\|_{\ell p}}. The maximal function 𝒜 * f = sup N |𝒜 N f | satisfies ( p , p ) sparse bounds for all 1 < p < 2. The latter are the natural variants of the scale-free bounds. As a corollary, 𝒜 * is bounded on ℓ p ( w ), for all weights w in the Muckenhoupt 𝒜 p class. No prior weighted inequalities for 𝒜 * were known. 
    more » « less
  4. ABSTRACT For ak‐uniform hypergraph and a positive integer , the Ramsey number denotes the minimum such that every ‐vertex ‐free ‐uniform hypergraph contains an independent set of vertices. A hypergraph isslowly growingif there is an ordering of its edges such that for each . We prove that if is fixed and is any non‐k‐partite slowly growing ‐uniform hypergraph, then for ,In particular, we deduce that the off‐diagonal Ramsey number is of order , where is the triple system . This is the only 3‐uniform Berge triangle for which the polynomial power of its off‐diagonal Ramsey number was not previously known. Our constructions use pseudorandom graphs and hypergraph containers. 
    more » « less
  5. Abstract The matching polytope of a graphGis the convex hull of the indicator vectors of the matchings onG. We characterize the graphs whose associated matching polytopes are Gorenstein, and then prove that all Gorenstein matching polytopes possess the integer decomposition property. As a special case study, we examine the matching polytopes of wheel graphs and show that they arenotGorenstein, butdopossess the integer decomposition property. 
    more » « less