𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graph Ramsey Theory and the Polynomial Hierarchy

✍ Scribed by Marcus Schaefer

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
402 KB
Volume
62
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

In the Ramsey theory of graphs F Γ„ (G, H) means that for every way of coloring the edges of F red and blue F will contain either a red G or a blue H. Arrowing, the problem of deciding whether F Γ„ (G, H), lies in 6 p 2 =coNP NP and it was shown to be coNP-hard by Burr [Bur90]. We prove that Arrowing is 6 p 2 -complete, simultaneously settling a conjecture of Burr and providing a rare natural example of a problem complete for a higher level of the polynomial hierarchy. We also show that Strong Arrowing, the induced subgraph version of Arrowing, is 6 p 2 -complete, and that the complexity of not arrowing stars is the same as that of finding a perfect matching.

πŸ“œ SIMILAR VOLUMES

Generalized Ramsey theory for graphs IV,
Generalized Ramsey theory for graphs IV, the Ramsey multiplicity of a graph
✍ F. Harary; G. Prins πŸ“‚ Article πŸ“… 1974 πŸ› John Wiley and Sons 🌐 English βš– 412 KB

A paopm graph G has no isolated points. I t s R m e y r u m b a r ( G ) i s the m i n i m p such that every 2-coloring of the edges of K contains a monochromatic G. The Ramhey m & t @ m y R(G) i s P the r (G) ' With j u s t one exception, namely Kq, we determine R(G) f o r proper graphs u i t h a t

The ramsey numbers for stripes and one c
The ramsey numbers for stripes and one complete graph
✍ Peter Lorimer πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 244 KB πŸ‘ 1 views

The Ramsey numbers M,,, n,P,, ..., n,P,), p > 2, are calculated. ## 1. Introduction One class of generalized Ramsey numbers that are known exactly are those for the graphs nP2 which consist of n disjoint paths of length 2; E. J. Cockayne and the author proved in 111 that d r(nlp2, ..., n d P 2 ) =

The polynomial and linear time hierarchi
The polynomial and linear time hierarchies in V0
✍ Leszek A. KoΕ‚odziejczyk; Neil Thapen πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 203 KB

## Abstract We show that the bounded arithmetic theory V^0^ does not prove that the polynomial time hierarchy collapses to the linear time hierarchy (without parameters). The result follows from a lower bound for bounded depth circuits computing prefix parity, where the circuits are allowed some au