排序方式: 共有3条查询结果,搜索用时 0 毫秒
1
1.
2.
Krzysztof Choromanski 《Journal of Graph Theory》2013,74(1):122-132
A celebrated unresolved conjecture of Erdös and Hajnal (see Discrete Appl Math 25 (1989), 37–52) states that for every undirected graph H, there exists , such that every graph on n vertices which does not contain H as an induced subgraph contains either a clique or an independent set of size at least . In (Combinatorica (2001), 155–170), Alon et al. proved that this conjecture was equivalent to a similar conjecture about tournaments. In the directed version of the conjecture cliques and stable sets are replaced by transitive subtournaments. For a fixed undirected graph H, define to be the supremum of all ε for which the following holds: for some n0 and every every undirected graph with vertices not containing H as an induced subgraph has a clique or independent set of size at least . The analogous definition holds if H is a tournament. We call the Erdös–Hajnal coefficient of H. The Erdös–Hajnal conjecture is true if and only if for every H. We prove in this article that:
- the Erdös–Hajnal coefficient of every graph H is at most ,
- there exists such that the Erdös–Hajnal coefficient of almost every tournament T on k vertices is at most , i.e. the proportion of tournaments on k vertices with the coefficient exceeding goes to 0 as k goes to infinity.
3.
Berahas Albert S. Cao Liyuan Choromanski Krzysztof Scheinberg Katya 《Foundations of Computational Mathematics》2022,22(2):507-560
Foundations of Computational Mathematics - In this paper, we analyze several methods for approximating gradients of noisy functions using only function values. These methods include finite... 相似文献
1