An official website of the United States government
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
On the number of edges of separated multigraphs
Abstract We prove that the number of edges of a multigraph with vertices is at most , provided that any two edges cross at most once, parallel edges are noncrossing, and the lens enclosed by every pair of parallel edges in contains at least one vertex. As a consequence, we prove the following extension of the Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi, and Leighton, if has edges, in any drawing of with the above property, the number of crossings is . This answers a question of Kaufmann et al. and is tight up to the logarithmic factor.
more »
« less
- Award ID(s):
- 1800746
- PAR ID:
- 10461993
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Journal of Graph Theory
- ISSN:
- 0364-9024
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Over the last two decades, frameworks for distributed-memory parallel computation, such as MapReduce, Hadoop, Spark and Dryad, have gained significant popularity with the growing prevalence of large network datasets. The Massively Parallel Computation (MPC) model is the de-facto standard for studying graph algorithms in these frameworks theoretically. Subgraph counting is one such fundamental problem in analyzing massive graphs, with the main algorithmic challenges centering on designing methods which are both scalable and accurate. Given a graph G = (V, E) with n vertices, m edges and T triangles, our first result is an algorithm that outputs a (1+ε)-approximation to T, with asymptotically optimal round and total space complexity provided any S ≥ max{(√ m, n²/m)} space per machine and assuming T = Ω(√{m/n}). Our result gives a quadratic improvement on the bound on T over previous works. We also provide a simple extension of our result to counting any subgraph of k size for constant k ≥ 1. Our second result is an O_δ(log log n)-round algorithm for exactly counting the number of triangles, whose total space usage is parametrized by the arboricity α of the input graph. We extend this result to exactly counting k-cliques for any constant k. Finally, we prove that a recent result of Bera, Pashanasangi and Seshadhri (ITCS 2020) for exactly counting all subgraphs of size at most 5 can be implemented in the MPC model in Õ_δ(√{log n}) rounds, O(n^δ) space per machine and O(mα³) total space. In addition to our theoretical results, we simulate our triangle counting algorithms in real-world graphs obtained from the Stanford Network Analysis Project (SNAP) database. Our results show that both our approximate and exact counting algorithms exhibit improvements in terms of round complexity and approximation ratio, respectively, compared to two previous widely used algorithms for these problems.more » « less
-
Abstract A result of Gyárfás says that for every 3‐coloring of the edges of the complete graph , there is a monochromatic component of order at least , and this is best possible when 4 divides . Furthermore, for all and every ‐coloring of the edges of the complete ‐uniform hypergraph , there is a monochromatic component of order at least and this is best possible for all . Recently, Guggiari and Scott and independently Rahimi proved a strengthening of the graph case in the result above which says that the same conclusion holds if is replaced by any graph on vertices with minimum degree at least ; furthermore, this bound on the minimum degree is best possible. We prove a strengthening of the case in the result above which says that the same conclusion holds if is replaced by any ‐uniform hypergraph on vertices with minimum ‐degree at least ; furthermore, this bound on the ‐degree is best possible.more » « less
-
We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate --- in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games. We introduce a class of games we call anchored. We then introduce a simple transformation on games called \emph{anchoring}, inspired in part by the Feige-Kilian transformation, that turns \emph{any} (multiplayer) game into an anchored game. Unlike the Feige-Kilian transformation, our anchoring transformation is completeness preserving. We prove an exponential-decay parallel repetition theorem for anchored games that involve any number of entangled players. We also prove a threshold version of our parallel repetition theorem for anchored games. Together, our parallel repetition theorems and anchoring transformation provide the first hardness amplification techniques for general entangled games. We give an application to the games version of the Quantum PCP Conjecture.more » « less
-
Abstract Let denote the complete 3‐uniform hypergraph on vertices and the 3‐uniform hypergraph on vertices consisting of all edges incident to a given vertex. Whereas many hypergraph Ramsey numbers grow either at most polynomially or at least exponentially, we show that the off‐diagonal Ramsey number exhibits an unusual intermediate growth rate, namely,for some positive constants and . The proof of these bounds brings in a novel Ramsey problem on grid graphs which may be of independent interest: what is the minimum such that any 2‐edge‐coloring of the Cartesian product contains either a red rectangle or a blue ?more » « less
