496 – Regressive functions on pairs

[Updated September 4, 2009.]

(For background, see my paper Regressive functions on pairs, in my papers page.)

Here, {{\mathbb N}=\{0,1,\dots\}.} For {X\subseteq{\mathbb N},} we denote by {X^{[2]}} the set of unordered pairs of elements of {X.} We will use interval notation, with the understanding that our variables range over natural numbers so, for example, {[3,6)=\{3,4,5\}.}

Suppose that {0\notin X.} A function {f:X^{[2]}\rightarrow{\mathbb N}} is regressive iff {f(t)<{\rm min}(t).} We will usually write {f(a,b)} for {f(\{a,b\})} with the understanding that {a<b.}

A subset {H\subseteq X} is min-homogeneous for {f} iff whenever {a<b<c} are in {H,} then {f(a,b)=f(a,c).}

Given {0<n\in{\mathbb N},} denote by {g(n)} the smallest integer {N} such that whenever {f:[n,N]^{[2]}\rightarrow{\mathbb N}} is regressive, there is a min-homogeneous set {H\subset[n,N]} of size at least {4.}

We want to bound the function {g(n)} as precisely as possible.

Here are some exact values and bounds:

  • {g(1)=5.}
  • {g(2)=15.}
  • {g(3)=37.}
  • {g(n)\le 2^{n-1}(n+7)-3.} 
    (In the paper, I prove the weaker bound {g(n)\le 2^n n+12\cdot 2^{n-3}+1} for {n\ge3.})
  • {g(n+1)\ge 2g(n)+3.}

I will be modifying the table above if additional results are found.

Typeset using LaTeX2WP.

Advertisements

2 Responses to 496 – Regressive functions on pairs

  1. […] also presents some results we obtained during a reading course he took with me as an undergrad, on regressive Ramsey numbers, based on my […]

  2. […] also presents some results we obtained during a reading course he took with me as an undergrad, on regressive Ramsey numbers, based on my […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: