Friendship bracket function

We denote a person with n friends with fn.

With (fk1,fk2,fk3,fk4, ... fkn), we denote that these n people each know each other. To clarify, when drawn as a graph, the graph is complete.


For Friend(k), we have a sequence of friend bracket functions. The nth element can have at most n+k persons, and the nth element can't be a friendship minor of an earlier element. It can have multiple brackets.

Friendship minor

Let the earlier element be expressed as

(fk1,fk2,fk3,fk4, ... fkt1)(fkt1+1,fkt1+2,fkt1+3,fkt1+4, ... fkt2)...(fktn+1,fktn+2,fktn+3,fktn+4, ... fktn+1)

Let the other element be expressed as

(fk1',fk2',fk3',fk4', ... fkt1'')(fkt1'+1',fkt1'+2',fkt1'+3',fkt1'+4', ... fkt2'')...(fktn''+1',fktn''+2',fktn''+3',fktn''+4', ... fktn'+1'')

For those who can't read the accents very well, every k has an accent, every t has an accent and every n has an accent.

An element is a friendship minor of an earlier element if, for some ordering of the brackets and the elements inside the brackets:

  • n ≤ n'
  • tq ≤ tq' for all q
  • ktn+q ≤ ktn'+q' for all q<tn+1-tn and for all n.

In informal terms:

  • There are at least as many brackets.
  • Each bracket has at least as many persons
  • Each person has at least as many friends as the person on the equal place.

Number of persons

The number of persons is lower than you might expect. In (f1,f3)(f1,f3)(f1,f3) there are 6 people on the first look. But you can have a person knowing 3 others, each knowing no-one else. So this are 4 persons.

Formally, we look for the smallest graph Q such that for the first bracket (fk1,fk2,fk3,fk4, ... fkn) in the element, we can find a minor of Q that has valences k1, k2, ... kn-1, kn and a minor is of the complete graph Kn.

If there are brackets with the same content, we can not use same minor again, we must use other minor.

The number of vertices q in the graph Q is the number of persons in the element of the sequence.

Values and bounds

For simplice denote f0 with n, f1 with o, f2 with p, f3 with q, etcetera.

Friend(0) and Friend(1)

Friend(0)=1, using (n)

Friend(1)=4, using (o,o), (n)(n)(n), (n)(n), (n)











Some people might recognize this as the sequence for SSCG(2). Indeed, Friend(2)+1≥SSCG(2).

Proving well-foundness

Its well-foundness follows form Higman's lemma. We apply it to every bracket, so they are WQO since the number of friends is WQO. Then the string of brackets is WQO since it consists of WQO brackets.

I'm not the one who noticed, Deedlit did.

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.