Previous work on Ramsey multiplicity focused primarily on the multiplicity of complete graphs of constant size. We study the question for larger complete graphs, specifically showing that in every 2-coloring of a complete graph on @math vertices, there are at least @math monochromatic complete subgraphs of size between @math and @math . We also study bounds on the ratio between a maximum and a random red clique in a graph, and the ratio between a maximum and a random monochromatic clique in a graph.
The work most related to this paper is that of Sz ' e kely @cite_12 . He showed that for large enough @math , in any @math -coloring of a complete graph on @math vertices there are at least @math monochromatic complete subgraphs, and there is @math -coloring with at most @math monochromatic complete subgraphs. Our Theorem improves over his lower bound. In the same work, Sz ' e kely also provides upper bounds on Ramsey multiplicities for Half-Ramsey graphs. We prove lower bounds that match his upper bounds (up to low order terms). See Corollary .
@cite_12
2038712425 2625025510 2266714125 2086631032
Ramsey's theorem guarantees that if G is a graph, then any 2-coloring of the edges of a large enough complete graph yields a monochromatic copy of G. Interesting problems arise when one asks how many such G must occur. A survey of this and related problems is given, along with a number of new results. We prove two results regarding cycles in properly edge-colored graphs. First, we make a small improvement to the recent breakthrough work of Alon, Pokrovskiy and Sudakov who showed that every properly edge-colored complete graph @math on @math vertices has a rainbow cycle on at least @math vertices, by showing that @math has a rainbow cycle on at least @math vertices. Second, by modifying the argument of Hatami and Shor which gives a lower bound for the length of a partial transversal in a Latin Square, we prove that every properly colored complete graph has a Hamilton cycle in which at least @math different colors appear. For large @math , this is an improvement of the previous best known lower bound of @math of Andersen. Numerous graph mining applications rely on detecting subgraphs which are large near-cliques. Since formulations that are geared towards finding large near-cliques are hard and frequently inapproximable due to connections with the Maximum Clique problem, the poly-time solvable densest subgraph problem which maximizes the average degree over all possible subgraphs "lies at the core of large scale data mining" [10]. However, frequently the densest subgraph problem fails in detecting large near-cliques in networks. In this work, we introduce the k-clique densest subgraph problem, k ≥ 2. This generalizes the well studied densest subgraph problem which is obtained as a special case for k=2. For k=3 we obtain a novel formulation which we refer to as the triangle densest subgraph problem: given a graph G(V,E), find a subset of vertices S* such that τ(S*)=max limitsS ⊆ V t(S) |S|, where t(S) is the number of triangles induced by the set S. On the theory side, we prove that for any k constant, there exist an exact polynomial time algorithm for the k-clique densest subgraph problem . Furthermore, we propose an efficient 1 k-approximation algorithm which generalizes the greedy peeling algorithm of Asahiro and Charikar [8,18] for k=2. Finally, we show how to implement efficiently this peeling framework on MapReduce for any k ≥ 3, generalizing the work of Bahmani, Kumar and Vassilvitskii for the case k=2 [10]. On the empirical side, our two main findings are that (i) the triangle densest subgraph is consistently closer to being a large near-clique compared to the densest subgraph and (ii) the peeling approximation algorithms for both k=2 and k=3 achieve on real-world networks approximation ratios closer to 1 rather than the pessimistic 1 k guarantee. An interesting consequence of our work is that triangle counting, a well-studied computational problem in the context of social network analysis can be used to detect large near-cliques. Finally, we evaluate our proposed method on a popular graph mining application. A general theorem on the complexity of a class of recognition problems is proved. As a particular case the following result is given: There is no algorithm which, for any 2-coloration of the infinite complete graph, can produce a monochromatic subgraph of k vertices within 2k2 steps (at each step the color of an arbitrary edge is questioned).