Message Boards Message Boards

[TMJ] Improving the Kruskal—Katona Bounds for Complete Subgraphs of a Graph

Posted 6 years ago

New THE MATHEMATICA JOURNAL article:


Improving the Kruskal—Katona Bounds for Complete Subgraphs of a Graph

by ROBERT COWEN


ABSTRACT: An important problem in graph theory is to find the number of complete subgraphs of a given size in a graph. If the graph is very large, it is usually only possible to obtain upper bounds for these numbers based on the numbers of complete subgraphs of smaller sizes. The Kruskal–Katona bounds are often used for these calculations. We investigate these bounds in specific cases and study how they might be improved.

enter image description here

POSTED BY: Moderation Team

Hello Robert,

For further computational exploration, you may be interested in the following functions:

FindClique can find cliques efficiently (much more efficiently than taking Subgraphs of vertex Subsets).

The IGraph/M package has the IGCliqueSizeCounts function which can count cliques of various sizes even more efficeintly. E.g.,

IGCliqueSizeCounts[graph, {3,5}]

will counts cliques between sizes 3 and 5.

Finally, I would advise against trying to use ' in variable names. While a = 1; a' = 2; appears to work and create two distinct variable, the ' is quite literally interpreted as a derivative, in this case the derivative of "1" (which is of course nonsense). Now try b=1, then evaluate b'—and you get 2 as the answer, because according to Mathematica, that is "the derivative of 1).

POSTED BY: Szabolcs Horvát
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract