A path forward: Tropicalization in extremal combinatorics
A path forward: Tropicalization in extremal combinatorics
复制标题
前进之路：极值组合的热带化
DOI：
10.1016/j.aim.2022.108561
复制
发表时间：
2022
影响因子：
1.7
通讯作者：
Raymond, Annie
中科院分区：
文献类型：
--
作者：
Blekherman, Grigoriy;Raymond, Annie
极值组合学中的许多重要问题可以用证明图同态数中的一个纯二项式不等式来表述，即证明hm (h1， G) a 1⋯hm (H k， G) a k≥hm (H k+ 1， G) a k+ 1⋯hm (H m， G) am对一些固定图H 1，…，H m和所有图G都成立。一个突出的例子是Sidorenko的猜想。对于图U={h1，…，hm}的固定集合，U的图中有效的纯二项式不等式的指数向量形成凸锥。我们计算了几个图族的这个锥，包括完全图、偶环、星形和路径；后者是我们计算过的最有趣、最复杂的情况。在所有这些情况下，我们观察到一个诱人的多面体现象：有效的纯二项式不等式的锥实际上是有理多面体，因此所有有效的纯二项式不等式都可以从极限射线的指数向量的有限集合中生成。利用Kopparty和Rossman（[17]）的工作，我们证明了当所有图H i是串并联和弦时，有效不等式的锥确实是有理多面体，并且我们推测对于任何有限集合u，多面体都成立。我们证明了多面体现象也出现在拟阵和简单复合体中。我们对路径不等式的描述涉及到最近在[29]中以其原始形式证明的Erdős-Simonovits猜想的推广以及以前未观察到的新不等式族。我们还解决了Kopparty和Rossman关于路径同态支配指数的一个开放问题。我们的主要工具之一是热带化，这是一种在复杂代数几何中众所周知的技术，于2010年首次应用于极值组合。我们证明了几个关于热带化的结果，这些结果可能是独立的兴趣。
Many important problems in extremal combinatorics can be stated as proving a pure binomial inequality in graph homomorphism numbers, ie, proving that hom (H 1, G) a 1⋯ hom (H k, G) a k≥ hom (H k+ 1, G) a k+ 1⋯ hom (H m, G) a m holds for some fixed graphs H 1,…, H m and all graphs G. One prominent example is Sidorenko's conjecture. For a fixed collection of graphs U={H 1,…, H m}, the exponent vectors of valid pure binomial inequalities in graphs of U form a convex cone. We compute this cone for several families of graphs including complete graphs, even cycles, stars and paths; the latter is the most interesting and intricate case that we compute. In all of these cases, we observe a tantalizing polyhedrality phenomenon: the cone of valid pure binomial inequalities is actually rational polyhedral, and therefore all valid pure binomial inequalities can be generated from the finite collection of exponent vectors of the extreme rays. Using the work of Kopparty and Rossman ([17]), we show that the cone of valid inequalities is indeed rational polyhedral when all graphs H i are series-parallel and chordal, and we conjecture that polyhedrality holds for any finite collection U. We demonstrate that the polyhedrality phenomenon also occurs in matroids and simplicial complexes. Our description of the inequalities for paths involves a generalization of the Erdős-Simonovits conjecture recently proved in its original form in [29] and a new family of inequalities not observed previously. We also solve an open problem of Kopparty and Rossman on the homomorphism domination exponent of paths. One of our main tools is tropicalization, a well-known technique in complex algebraic geometry, first applied in extremal combinatorics in [3]. We prove several results about tropicalizations which may be of independent interest.
登录
查看更多内容
洛瓦斯会见魏斯费勒和莱曼
DOI：
--
发表时间：
2018
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
Holger Dell;Martin Grohe;Gaurav Rattan
通讯作者：
Gaurav Rattan
对数凹多项式，I：熵和用于计算拟阵基数的确定性近似算法
影响因子：
2.5
作者：
Nima Anari;S. Gharan;C. Vinzant
通讯作者：
C. Vinzant
西多伦科猜想的两种方法
DOI：
10.1090/tran/6487
发表时间：
2013
期刊：
arXiv: Combinatorics
影响因子：
--
作者：
J. Kim;Choongbum Lee;Joonkyung Lee
通讯作者：
Joonkyung Lee
“热带凸性”勘误表
影响因子：
0.9
作者：
M. Develin;B. Sturmfels
通讯作者：
B. Sturmfels
多面体集的热带凸包
DOI：
--
发表时间：
2019
期刊：
ArXivorg
影响因子：
--
作者：
Hill, Cvetelina;Lamboglia, Sara;Pasley Simon, Faye
通讯作者：
Pasley Simon, Faye