Ordered and convex geometric trees with linear extremal function

Abstract: The extremal functions

e x_{i g h t a r r o w} (n, F)

and

e x_{c i r} (n, F)

for ordered and convex geometric acyclic graphs

F

have been extensively investigated by a number of researchers. Basic questions are to determine when

e x_{i g h t a r r o w} (n, F)

and

e x_{c i r} (n, F)

are linear in

n

, the latter posed by Brass-K'arolyi-Valtr in 2003. In this paper, we answer both these questions for every tree

F

. We give a forbidden subgraph characterization for a family

c a l T

of ordered trees with

k

edges, and show that

e x_{i g h t a r r o w} (n, T) = (k - 1) n - k c h o o s e 2

for all

n g e q k + 1

when

T i n c a l T

and

e x_{i g h t a r r o w} (n, T) = O m e g a (n l o g n)

for

T o t i n c a l T

. We also describe the family of the convex geometric trees with linear Tur' an number and show that for every convex geometric tree

F

not in this family,

e x_{c i r} (n, F) = O m e g a (n l o g l o g n)

.

Recommendations

Cites Work

Cited In (6)

This page was built for publication: Ordered and convex geometric trees with linear extremal function