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.

Advertisement

This entry was posted on Monday, August 31st, 2009 at 2:37 pm and is filed under 496/596: Independent study. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to 496 – Regressive functions on pairs

  1. Coloring problems « Teaching blog says:
    January 12, 2012 at 1:58 am

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

    Reply
  2. Coloring problems « A kind of library says:
    August 27, 2012 at 7:42 am

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

    Reply

Leave a Reply

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

Gravatar
WordPress.com Logo

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

Facebook photo

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

Cancel

Connecting to %s

%d bloggers like this: