Fix some n and k. Consider the following directed graph: vertices are all functions $2^n\rightarrow 2^n$ and a vertex f has an edge to a vertex g for every h such that $f=h\circ g$ and h depends only on k of the inputs (i.e. there is some set of k elements such that $h(x)=h(y)$ for all $x,y$ that are equal on those k elements). I am interested in the structure of this graph, in particular clustering. I really would like to know if anyone has studied this graph, but since this is Mathoverflow, in the interests of concreteness I would like to know, for a given $a,b$ the number of subsets $S$ of the vertices, having size $a$ and such that the proportion of edges incident to $S$ which connect two vertices of $S$ is at least $b$
2
-
1$\begingroup$ Quite different, but in case you don't know this work already, this reminds me of work by Kahn, Kalai, Linial; also Mossel using Fourier analysis to look at functions of $n$ Boolean variables, focusing on lower bounds for the sensitivity to a single one of the variables. $\endgroup$– Anthony QuasOct 30, 2014 at 5:46
-
$\begingroup$ This looks like K-out-of-N systems in operations research and system analysis: K-out-of-N system can be deined such that a system works if at least K out of N vertices satisfy a boolean function. Also the work (The influence of variables on boolean functions by Kalai-Linnea-et al.)[www.ma.huji.ac.il/~kalai/kkl.ps] may be useful. $\endgroup$– hhhApr 18, 2016 at 10:55
Add a comment
|