Near optimal thresholds for existence of dilated configurations in \mathbb{F}_q^d

Abstract: Let

E s u b s e t m a t h b b F_{q}^{d}

and

l V e r t c d o t V e r t : m a t h b b F_{q}^{d} o m a t h b b F_{q}

defined as

l V e r t a l p h a V e r t := a l p h a_{1}^{2} + d o t s + a l p h a_{d}^{2}

if

a l p h a = (a l p h a_{1}, d o t s, a l p h a_{d}) i n m a t h b b F_{q}^{d}

, where

m a t h b b F_{q}^{d}

is the

d

-dimensional vector space over the finite field

m a t h b b F_{q}

with

q

elements. Let

k g e q 1

and

A

is a nonempty subset of

(i, j) : 1 l e q i < j l e q k + 1

. In this paper, we prove that for any nonzero square element

r i n m a t h b b F_{q}

and

l v e r t E v e r t g g_{k} q^{d / 2}

one can find two

(k + 1)

-tuples in

E

such that one of them is dilated by

r

with respect to the other only on

| A |

edges. More precisely, there exist

(x_{1}, d o t s, x_{k + 1}) i n E^{k + 1}

and

(y_{1}, d o t s, y_{k + 1}) i n E^{k + 1}

such that

l V e r t y_{i} - y_{j} V e r t = r l V e r t x_{i} - x_{j} V e r t

if

(i, j) i n A

and

x_{i} e q x_{j}, y_{i} e q y_{j}

if

1 l e q i < j l e q k + 1

. In particular, we present two proofs first of which utilizes the machinery of group actions which is typically used to handle problems of this nature, whereas the second one is more combinatorial in nature and is based on the averaging argument. Moreover, we show that in two dimensions the threshold

d / 2

is sharp when

q e q u i v 3 p m o d 4

. As a corollary of this result, varying the underlying set

A

we obtain thresholds for existence of dilated

k

-paths,

k

-cycles, and

k

-stars

(k g e q 3)

. These results partly generalize some results of the second author.

This page was built for publication: Near optimal thresholds for existence of dilated configurations in $\mathbb{F}_q^d$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6437047)