skip to main content

Title: Nimber Sequences of Node-Kayles Games
Node-Kayles is an impartial game played on a simple graph. The Sprague-Grundy theorem states that every impartial game is associated with a nonnegative integer value called a Nimber. This paper studies the Nimber sequences of various families of graphs, including 3-paths, lattice graphs, prism graphs, chained cliques, linked cliques, linked cycles, linked diamonds, hypercubes, and generalized Petersen graphs. For most of these families, we determine an explicit formula or a recursion on their Nimber sequences.
Authors:
; ; ; ; ; ; ;
Award ID(s):
1852378
Publication Date:
NSF-PAR ID:
10141270
Journal Name:
Journal of integer sequences
Volume:
23
ISSN:
1530-7638
Sponsoring Org:
National Science Foundation
More Like this
  1. Allostery is one of most important processes in molecular biology by which proteins transmit the information from one functional site to another, frequently distant site. The information on ligand binding or on posttranslational modification at one site is transmitted along allosteric communication path to another functional site allowing for regulation of protein activity. The detailed analysis of the general character of allosteric communication paths is therefore extremely important. It enables to better understand the mechanism of allostery and can be used in for the design of new generations of drugs. Considering all the PDB annotated allosteric proteins (from ASD - AlloSteric Database) belonging to four different classes (kinases, nuclear receptors, peptidases and transcription factors), this work has attempted to decipher certain consistent patterns present in the residues constituting the allosteric communication sub-system (ACSS). The thermal fluctuations of hydrophobic residues in ACSSs were found to be significantly higher than those present in the non- ACSS part of the same proteins, while polar residues showed the opposite trend. The basic residues and hydroxyl residues were found to be slightly more predominant than the acidic residues and amide residues in ACSSs, hydrophobic residues were found extremely frequently in kinase ACSSs. Despite having differentmore »sequences and different lengths of ACSS, they were found to be structurally quite similar to each other – suggesting a preferred structural template for communication. ACSS structures recorded low RMSD and high Akaike Information Criterion (AIC) scores among themselves. While the ACSS networks for all the groups of allosteric proteins showed low degree centrality and closeness centrality, the betweenness centrality magnitudes revealed nonuniform behavior. Though cliques and communities could be identified within the ACSS, maximal-common-subgraph considering all the ACSS could not be generated, primarily due to the diversity in the dataset. Barring one particular case, the entire ACSS for any class of allosteric proteins did not demonstrate “small world” behavior, though the sub-graphs of the ACSSs, in certain cases, were found to form small-world networks.« less
  2. Abstract Main results of the paper are as follows: (1) For any finite metric space $M$ the Lipschitz-free space on $M$ contains a large well-complemented subspace that is close to $\ell _{1}^{n}$ . (2) Lipschitz-free spaces on large classes of recursively defined sequences of graphs are not uniformly isomorphic to $\ell _{1}^{n}$ of the corresponding dimensions. These classes contain well-known families of diamond graphs and Laakso graphs. Interesting features of our approach are: (a) We consider averages over groups of cycle-preserving bijections of edge sets of graphs that are not necessarily graph automorphisms. (b) In the case of such recursive families of graphs as Laakso graphs, we use the well-known approach of Grünbaum (1960) and Rudin (1962) for estimating projection constants in the case where invariant projections are not unique.
  3. Clique-counting is a fundamental problem that has application in many areas eg. dense subgraph discovery, community detection, spam detection, etc. The problem of k-clique-counting is difficult because as k increases, the number of k-cliques goes up exponentially. Enumeration algorithms (even parallel ones) fail to count k-cliques beyond a small k. Approximation algorithms, like TuránShadow have been shown to perform well upto k = 10, but are inefficient for larger cliques. The recently proposed Pivoter algorithm significantly improved the state-of-the-art and was able to give exact counts of all k-cliques in a large number of graphs. However, the clique counts of some graphs (for example, com-lj) are still out of reach of these algorithms. We revisit the TuránShadow algorithm and propose a generalized framework called YACC that leverages several insights about real-world graphs to achieve faster clique-counting. The bottleneck in TuránShadow is a recursive subroutine whose stopping condition is based on a classic result from extremal combinatorics called Turán's theorem. This theorem gives a lower bound for the k-clique density in a subgraph in terms of its edge density. However, this stopping condition is based on a worst-case graph that does not reflect the nature of real-world graphs. Using techniques formore »quickly discovering dense subgraphs, we relax the stopping condition in a systematic way such that we get a smaller recursion tree while still maintaining the guarantees provided by TuránShadow. We deploy our algorithm on several real-world data sets and show that YACC reduces the size of the recursion tree and the running time by over an order of magnitude. Using YACC, we are able to obtain clique counts for several graphs for which clique-counting was infeasible before, including com-lj.« less
  4. Quasi-cliques are a type of dense subgraphs that generalize the notion of cliques, important for applications such as community/module detection in various social and biological networks. However, the existing quasi-clique definition and algorithms are only applicable to undirected graphs. In this paper, we generalize the concept of quasi-cliques to directed graphs by proposing $(\gamma_1, \gamma_2)$-quasi-cliques which have density requirements in both inbound and outbound directions of each vertex in a quasi-clique subgraph. An efficient recursive algorithm is proposed to find maximal $(\gamma_1, \gamma_2)$-quasi-cliques which integrates many effective pruning rules that are validated by ablation studies. We also study the finding of top-$k$ large quasi-cliques directly by bootstrapping the search from more compact quasi-cliques, to scale the mining to larger networks. The algorithms are parallelized with effective load balancing, and we demonstrate that they can scale up effectively with the number of CPU cores.
  5. We study a class of linear-quadratic stochastic differential games in which each player interacts directly only with its nearest neighbors in a given graph. We find a semiexplicit Markovian equilibrium for any transitive graph, in terms of the empirical eigenvalue distribution of the graph’s normalized Laplacian matrix. This facilitates large-population asymptotics for various graph sequences, with several sparse and dense examples discussed in detail. In particular, the mean field game is the correct limit only in the dense graph case, that is, when the degrees diverge in a suitable sense. Although equilibrium strategies are nonlocal, depending on the behavior of all players, we use a correlation decay estimate to prove a propagation of chaos result in both the dense and sparse regimes, with the sparse case owing to the large distances between typical vertices. Without assuming the graphs are transitive, we show also that the mean field game solution can be used to construct decentralized approximate equilibria on any sufficiently dense graph sequence.