Cliques in random graphs
From MaRDI portal
Publication:4111621
DOI10.1017/S0305004100053056zbMath0344.05155OpenAlexW2138163102WikidataQ29392253 ScholiaQ29392253MaRDI QIDQ4111621
Publication date: 1976
Published in: Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0305004100053056
Related Items
The largest hole in sparse random graphs, Which networks permit stable allocations? A theory of network‐based comparisons, On the clique number of noisy random geometric graphs, Two-Point Concentration of the Independence Number of the Random Graph, How does the chromatic number of a random graph vary?, Two conjectured strengthenings of Turán's theorem, Phase transition in noisy high-dimensional random geometric graphs, Edge ideals of Erdős-Rényi random graphs: linear resolution, unmixedness and regularity, A critical probability for biclique partition of \(G_{n,p}\), Asymptotic bounds for clustering problems in random graphs, Testing community structure for hypergraphs, Tensor clustering with planted structures: statistical optimality and computational limits, On a method for random graphs, Networks beyond pairwise interactions: structure and dynamics, Energy landscape for large average submatrix detection problems in Gaussian random matrices, Solving the maximum clique problem using a tabu search approach, Coloring random graphs, TOPOLOGY OF RANDOM RIGHT ANGLED ARTIN GROUPS, Graph clustering via generalized colorings, Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number, On independent sets in random graphs, Sharp concentration of the chromatic number on random graphs \(G_{n,p}\), Threshold phenomena in random structures, Cliques in graphs excluding a complete graph minor, Constructions of independent sets in random intersection graphs, Unnamed Item, Chromatic number versus chromatic number in graphs with bounded clique number, Expose-and-merge exploration and the chromatic number of a random graph, Independence numbers and chromatic numbers of the random subgraphs of some distance graphs, Topological cliques of random graphs, On the sizes of large subgraphs of the binomial random graph, A simple spectral algorithm for recovering planted partitions, Unnamed Item, Distributed algorithms for random graphs, On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph, Sharp detection boundaries on testing dense subhypergraph, On the number of \(r\)-transitive orientations of \(G(n,p)\), Distinct degrees and homogeneous sets, One-Point Concentration of the Clique and Chromatic Numbers of the Random Cayley Graph on $\mathbb{F}_2^n$, Independence numbers of random sparse hypergraphs, More on the Bipartite Decomposition of Random Graphs, Local and global colorability of graphs, On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix, Degree sequences of random graphs, An algorithm for generating all maximal independent subsets of posets, On the concentration of the independence numbers of random hypergraphs, Hadwiger's conjecture is true for almost every graph, Online sum-paintability: the slow-coloring game, Isomorphisms between random graphs, Matrix and discrepancy view of generalized random and quasirandom graphs, Graphs which contain all small graphs, Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations, On the Number ofk-Dominating Independent Sets, Maximum sparse induced subgraphs of the binomial random graph with given number of edges, On the connectivity of proper colorings of random graphs and hypergraphs, Approximating independent set in perturbed graphs, On the independence number of random graphs, Application of statistical mechanics to combinatorial optimization problems: the chromatic number problem and \(q\)-partitioning of a graph., Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Testing copositivity via mixed-integer linear programming, Dense subgraphs of power-law random graphs, Non-concentration of the chromatic number of a random graph, Parallel tempering for the planted clique problem, On the independence and chromatic numbers of random regular graphs, Maximum induced forests in random graphs, Dense subgraphs in random graphs, Independent sets in graphs, Limiting distribution of short cycles in inhomogeneous random uniform hypergraph, Random regular graphs of high degree, Constraining the clustering transition for colorings of sparse random graphs, Asymptotically optimal induced universal graphs, The chromatic number of random intersection graphs, Random flag complexes and asymptotic syzygies, The chromatic number of random graphs, A generalization of maximal independent sets, Unnamed Item, The distribution of clusters in random graphs, Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs, On threshold probability for the stability of independent sets in distance graphs, On the maximum number of cliques in a graph, Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms, Largest sparse subgraphs of random graphs, Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview, Finding a planted clique by adaptive probing, Minimum coprime graph labelings, The size of a maximum subgraph of the random graph with a given number of edges, Approximability Distance in the Space of H-Colourability Problems, A note on the chromatic number of a dense random graph, Constrained spanning trees and the traveling salesman problem, Large independent sets in random regular graphs, Ising spins on thin graphs, On the chromatic number of random subgraphs of a certain distance graph, On the subgraph query problem, Superboolean rank and the size of the largest triangular submatrix of a random matrix, Tree and forest weights and their application to nonuniform random graphs, The largest tree in a random graph, Trees in random graphs, On the Chromatic Index of Random Uniform Hypergraphs, Large Induced Matchings in Random Graphs, Clustering in preferential attachment random graphs with edge-step, Upper bounds on the edge clique cover number of a graph, The maximum number of cliques in dense graphs, Sharp concentration of hitting size for random set systems, Component structure in the evolution of random hypergraphs, Bipartite decomposition of random graphs, The Complexity of Public-Key Cryptography, The maximum clique problem, The matching process and independent process in random regular graphs and hypergraphs, A probabilistic upper bound for the edge identification complexity of graphs, Large clique is hard on average for resolution
