|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Three steps away from Shapiro’s problem: lower bounds for graphic sums with functions ‘max’ or ‘min’ in denominatorsстатья Исследовательская статья
- Автор: Sadov Sergey
- Журнал: ArXiv e-prints
- Год издания: 2021
- Первая страница: 1
- Последняя страница: 37
- Номер статьи: arXiv:2106.10877 [math.CO]
- DOI: 10.48550/ARXIV.2106.10877
- Аннотация: Taking Shapiro's cyclic sums $\sum_{i=1}^n x_i/(x_{i+1}+x_{i+2})$ (assuming index addition mod n) as a starting point, we introduce a broader class of cyclic sums, called generalized Shapiro-Diananda sums, where the denominators are p-th order power means of the sets $\{x_{i+j_1},...,x_{i+j_k}\}$ with fixed distinct integers $j_1,...,j_k$ and 1≤i≤n.Generalizing further, we replace the set of arguments of the power mean in the i-th denominator by an arbitrary nonempty subset of {1,…,n} interpreted as the set of out-neighbors of the node number i in a directed graph with n nodes. We call such sums graphic power sums since their structure is controlled by directed graphs.The inquiry, as in the well-researched case of Shapiro's sums, concerns the greatest lower bound of the given ``sum'' as a function of positive variables $x_1,...,x_n$. We show that the cases of p=+∞ (max-sums) and p=−∞ (min-sums) are tractable.For the max-sum associated with a given graph the g.l.b. is always an integer; for a strongly connected graph it equals to graph's girth.For the similar min-sum, we could not relate the g.l.b. to a known combinatorial invariant; we only give some estimates and describe a method for finding the g.l.b., which has factorial complexity in n.A satisfactory analytical treatment is available for the secondary minimization -- when the g.l.b.'s of min-sums for individual graphs are mininized over the class of strongly connected graphs with n nodes. The result (depending only on n) is found to be asymptotic to $e\ln n$.
- Добавил в систему: Садов Сергей Юрьевич