Nearly complete graphs decomposable into large induced matchings and their applications
Nearly complete graphs decomposable into large induced matchings and their applications
复制标题
DOI：
10.1145/2213977.2214074
复制
发表时间：
2011-11
期刊：
影响因子：
--
通讯作者：
N. Alon;Ankur Moitra;B. Sudakov
中科院分区：
文献类型：
--
作者：
N. Alon;Ankur Moitra;B. Sudakov
我们描述了（非常）密集的图的两个构造，它们是大型诱发匹配的边缘分离工会。尺寸N1-O（1）。以强烈的形式）猜想的是，在共享通道上进行通信的Birk，Linear和Meshulam的结果大大改善了（稍微）扩展了Samorodnitsky和Trevisan的图形测试的分析，我们的构造解决了Vempala的组合问题，内容涉及定向Steiner树问题的候选舍入计划。
We describe two constructions of (very) dense graphs which are edge disjoint unions of large induced matchings. The first construction exhibits graphs on N vertices with (N2)-o(N2) edges, which can be decomposed into pairwise disjoint induced matchings, each of size N1-o(1). The second construction provides a covering of all edges of the complete graph KN by two graphs, each being the edge disjoint union of at most N2-δ induced matchings, where δ>0.076. This disproves (in a strong form) a conjecture of Meshulam, substantially improves a result of Birk, Linial and Meshulam on communicating over a shared channel, and (slightly) extends the analysis of Hastad and Wigderson of the graph test of Samorodnitsky and Trevisan for linearity. Additionally, our constructions settle a combinatorial question of Vempala regarding a candidate rounding scheme for the directed Steiner tree problem.