MathDB

4

Part of 1992 Miklós Schweitzer

Problems(1)

graph inequality

Source: miklos schweitzer 1992 q4

10/24/2021
show there exist positive constants c1c_1 and c2c_2 such that for any n≥3n\geq 3, whenever T1T_1 and T2T_2 are two trees on the set of vertices X={1,2,...,n}X = \{1, 2, ..., n\}, there exists a function f:X→{−1,+1}f : X \to \{-1, +1\} for which ∣∑x∈Pf(x)∣<c1log⁡n\bigg | \sum_ {x \in P} f (x) \bigg | <c_1 \log n for any path P that is a subgraph of T1T_1 or T2T_2 , but with an upper bound c2log⁡n/log⁡log⁡nc_2 \log n / \log \log n the statement is no longer true.
combinatoricsgraph theoryinequalities