MathDB

graph inequality

Source: miklos schweitzer 1992 q4

October 24, 2021

combinatoricsgraph theoryinequalities

Problem Statement

show there exist positive constants

c_1

and

c_2

such that for any

n\geq 3

, whenever

T_1

and

T_2

are two trees on the set of vertices

X = \{1, 2, ..., n\}

, there exists a function

f : X \to \{-1, +1\}

for which

\bigg | \sum_ {x \in P} f (x) \bigg | <c_1 \log n

for any path P that is a subgraph of

T_1

or

T_2

, but with an upper bound

c_2 \log n / \log \log n

the statement is no longer true.

Back to Problems View on AoPS