부산대학교 도서관

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