## Combinatorics Seminar

When: Sunday, March 25, 10am

Where: Schreiber 309

Speaker: Zilin
Jiang, Technion

Title: How to guess an
n-digit number

## Abstract:

In a deductive game for two
players, SF and PGOM, SF conceals an n-digit number x = x_1,
..., x_n, and PGOM, who knows n, tries to
identify x by asking a number of questions, which are answered by SF.

Each question is an n-digit
number y = y_1, ..., y_n;
each answer is a number a(x, y), the number of subscripts i
such that x_i = y_i.
Moreover we require the questions from PGOM are predetermined.

In this talk, I will show
that the minimum number of questions required to determine x is (2+o(1))n / lg
n. A more general problem is to determine the asymptotic formula of the metric
dimension of Cartesian powers of a graph.

I will state the class of
graphs for which the formula can be determined, and the smallest graphs for
which we did not manage to settle.

Joint
work with Nikita Polyanskii.