부산대학교 도서관

Summary: ``A boolean function in $n$ variables is {\it weakly evasive} ifits decision-tree complexity is $\Omega(n)$. By $k$-graphs we mean$k$-uniform hypergraphs. A $k$-{\it graph property} on $v$ vertices isa boolean function on $n=(^v_k)$ variables corresponding to the$k$-subsets of a $v$-set that is invariant under the $v!$ permutationsof the $v$-set (isomorphisms of $k$-graphs).\par``Rivest and Vuillemin (1976) proved that all non-constant monotonegraph properties $(k=2)$ are weakly evasive, confirming a conjecture ofAanderaa and Rosenberg (1973). Kulkarni, Qiao, and Sun (2013) provedthe analogous result for 3-graphs. We extend these results to$k$-graphs for every fixed $k$. From this, we show that monotoneboolean functions invariant under the action of a large primitive groupare weakly evasive.\par``While KQS (2013) employ the powerful topological approach of Kahn,Saks, and Sturtevant (1984) combined with heavy number theory, ourargument is elementary and self-contained (modulo some basic grouptheory). Inspired by the outline of the KQS approach, we formalize thegeneral framework of `orbit augmentation sequences' of sets with groupactions. We show that a parameter of such sequences, called the`spacing,' is a lower bound on the decision-tree complexity for anynontrivial monotone property that is $\Gamma$-invariant for all groups$\Gamma$ involved in the orbit augmentation sequence, assuming allthose groups are $p$-groups. We develop operations on such sequencessuch as composition and direct product which will provide helpfulmachinery for our applications. We apply this general technique to$k$-graphs via certain liftings of $k$-graphs with wreath productaction of $p$-groups.''