RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1993 Volume 5, Issue 3, Pages 64–75 (Mi dm691)

A threshold function with the Shannon effect for Boolean functions with respect to a symmetric group

O. V. Denisov


Abstract: We prove that if $A$ is the property of a Boolean function $f(x_1,\dots,x_n)$ of weight $r$ consisting in the fact that $f$ has a trivial inertia group with respect to the group $S_n$, then the function $A(n)=\ln n$ is a threshold function for property $A$.

UDC: 519.1

Received: 01.03.1993


 English version:
Discrete Mathematics and Applications, 1993, 3:5, 505–515

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025