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.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


  • Home
  • Search Results
  • Page 1 of 1

Search for: All records

Award ID contains: 2347832

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; (, Random Structures & Algorithms)
    ABSTRACT A theorem of Shearer states that every ‐vertex triangle‐free graph of maximum degree contains an independent set of size at least . Ajtai, Komlós, Pintz, Spencer and Szemerédi proved that every ‐uniform ‐vertex “uncrowded” hypergraph of maximum degree has an independent set of size at least for some depending only on . Shearer asked whether his method for triangle‐free graphs could be extended to uniform hypergraphs. In this paper, we answer this in the affirmative, thereby giving a short proof of the theorem of Ajtai, Komlós, Pintz, Spencer and Szemerédi for a wider class of “locally sparse” hypergraphs. 
    more » « less
    Full Text Available 
  2. ; (, Bulletin of the London Mathematical Society)
    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
    Full Text Available 
  3. ; ; ; (, Random Structures & Algorithms)
    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
    Full Text Available 
  4. ; ; ; (, Bulletin of the London Mathematical Society)
    Abstract Building on recent work of Mattheus and Verstraëte, we establish a general connection between Ramsey numbers of the form for a fixed graph and a variant of the Zarankiewicz problem asking for the maximum number of 1s in an by ‐matrix that does not have any matrix from a fixed finite family derived from as a submatrix. As an application, we give new lower bounds for the Ramsey numbers and , namely, and . We also show how the truth of a plausible conjecture about Zarankiewicz numbers would allow an approximate determination of for any fixed integer . 
    more » « less
    Full Text Available 
  5. ; ; ; ; ; (, Computational Geometry)
    Full Text Available 
  6. ; ; ; ; ; ; ; (, Proceedings of the American Mathematical Society)
    A natural open problem in Ramsey theory is to determine those 3 3 -graphs H H for which the off-diagonal Ramsey number r ( H , K n ( 3 ) ) r(H, K_n^{(3)}) grows polynomially with n n . We make substantial progress on this question by showing that if H H is tightly connected or has at most two tight components, then r ( H , K n ( 3 ) ) r(H, K_n^{(3)}) grows polynomially if and only if H H is contained in an iterated blowup of an edge. 
    more » « less
    Full Text Available 
  7. ; ; ; ; ; ; (, Discrete analysis)
    Full Text Available 
  8. ; (, Annals of Mathematics)
    Full Text Available 
  9. ; (, SIAM news)
    Accepted Manuscript Full Text Available