## TPTP Problem File: GRA027^1.p

View Solutions - Solve Problem

```%------------------------------------------------------------------------------
% File     : GRA027^1 : TPTP v7.2.0. Released v3.6.0.
% Domain   : Graph Theory
% Problem  : R(3,3) > 4
% Version  : Especial.
% English  :

%          : [Bro08] Brown (2008), Email to G. Sutcliffe
% Source   : [Bro08]
% Names    :

% Status   : Theorem
% Rating   : 0.70 v7.2.0, 0.75 v7.1.0, 0.71 v7.0.0, 0.88 v6.4.0, 0.71 v6.3.0, 0.67 v6.1.0, 0.83 v5.5.0, 0.80 v5.4.0, 1.00 v3.7.0
% Syntax   : Number of formulae    :    1 (   0 unit;   0 type;   0 defn)
%            Number of atoms       :   48 (   0 equality;  48 variable)
%            Maximal formula depth :   17 (  17 average)
%            Number of connectives :   58 (  11   ~;   4   |;  12   &;  28   @)
%                                         (   0 <=>;   3  =>;   0  <=;   0 <~>)
%                                         (   0  ~|;   0  ~&)
%            Number of type conns  :   20 (  20   >;   0   *;   0   +;   0  <<)
%            Number of symbols     :    1 (   0   :;   0   =)
%            Number of variables   :   13 (   0 sgn;  12   !;   1   ?;   0   ^)
%                                         (  13   :;   0  !>;   0  ?*)
%                                         (   0  @-;   0  @+)
% SPC      : TH0_THM_NEQ_NAR

% Comments : If a type alpha has exactly n elements, then we can prove
%            R(k,l) > n by finding a graph (symmetric binary relation) on type
%            alpha with no k-cliques and no l-independent sets. Likewise, we
%            can prove R(k,l) <= n by proving every graph (symmetric binary
%            relation) on alpha must have a k-clique or l-independent set.
%            There is one type with 4 elements: o > o. There are two types
%            with 16 elements: o > o > o and (o > o) > o. There are two types
%            with 256 elements: o > o > o > o and o > (o > o) > o.  This means
%            we always have two formulations of R(k,l) >/<= 16 and two
%            formulations of R(k,l) >/<= 256.
%          :
%------------------------------------------------------------------------------
thf(ramsey_l_3_3_4,conjecture,(
? [G: ( \$o > \$o ) > ( \$o > \$o ) > \$o] :
( ! [Xx: \$o > \$o,Xy: \$o > \$o] :
( ( G @ Xx @ Xy )
=> ( G @ Xy @ Xx ) )
& ! [Xx0: \$o > \$o,Xx1: \$o > \$o,Xx2: \$o > \$o,Xp0: ( \$o > \$o ) > \$o,Xp1: ( \$o > \$o ) > \$o] :
( ( ( Xp0 @ Xx0 )
& ~ ( Xp0 @ Xx1 )
& ~ ( Xp0 @ Xx2 )
& ~ ( Xp1 @ Xx0 )
& ( Xp1 @ Xx1 )
& ~ ( Xp1 @ Xx2 ) )
=> ( ~ ( G @ Xx1 @ Xx0 )
| ~ ( G @ Xx2 @ Xx0 )
| ~ ( G @ Xx2 @ Xx1 ) ) )
& ! [Xx0: \$o > \$o,Xx1: \$o > \$o,Xx2: \$o > \$o,Xp0: ( \$o > \$o ) > \$o,Xp1: ( \$o > \$o ) > \$o] :
( ( ( Xp0 @ Xx0 )
& ~ ( Xp0 @ Xx1 )
& ~ ( Xp0 @ Xx2 )
& ~ ( Xp1 @ Xx0 )
& ( Xp1 @ Xx1 )
& ~ ( Xp1 @ Xx2 ) )
=> ( ( G @ Xx1 @ Xx0 )
| ( G @ Xx2 @ Xx0 )
| ( G @ Xx2 @ Xx1 ) ) ) ) )).

%------------------------------------------------------------------------------
```