Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Monotone Properties of k-Uniform Hypergraphs Are Weakly Evasive

Monotone Properties of k-Uniform Hypergraphs Are Weakly Evasive A Boolean function in n variables is weakly evasive if its decision-tree complexity is (n). By k-graphs, we mean k-uniform hypergraphs. A k-graph property on v vertices is a Boolean function on n = vk 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). In 1976, Rivest and Vuillemin proved that all nonconstant monotone graph properties (k = 2) are weakly evasive, confirming a conjecture of Aanderaa and Rosenberg in 1973. Then, in 2013, Kulkarni, Qiao, and Sun (KQS) 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. Although KQS employ the powerful topological approach of Kahn et al. in 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 -invariant for all groups 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 that 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Monotone Properties of k-Uniform Hypergraphs Are Weakly Evasive

Black, Timothy
ACM Transactions on Computation Theory (TOCT) , Volume 11 (3): 14 – Apr 26, 2019
Download PDF
14 pages

Loading next page...
 
/lp/association-for-computing-machinery/monotone-properties-of-k-uniform-hypergraphs-are-weakly-evasive-b8001Boucg
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3313908
Publisher site
See Article on Publisher Site

Abstract

A Boolean function in n variables is weakly evasive if its decision-tree complexity is (n). By k-graphs, we mean k-uniform hypergraphs. A k-graph property on v vertices is a Boolean function on n = vk 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). In 1976, Rivest and Vuillemin proved that all nonconstant monotone graph properties (k = 2) are weakly evasive, confirming a conjecture of Aanderaa and Rosenberg in 1973. Then, in 2013, Kulkarni, Qiao, and Sun (KQS) 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. Although KQS employ the powerful topological approach of Kahn et al. in 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 -invariant for all groups 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 that 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.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Apr 26, 2019

Keywords: Decision-tree complexity

References

  • Evasiveness and the distribution of prime numbers
    Babai, László; Banerjee, Anandam; Kulkarni, Raghav; Naik, Vipul
  • Finite permutation groups and finite simple groups
    Cameron, Peter J.
  • Evasiveness of subgraph containment and related properties
    Chakrabarti, Amit; Khot, Subhash; Shi, Yaoyun
  • Decision tree complexity of graph properties with dimension at most 5
    Gao, Suixiang; Lin, Guohui
  • A survey on hypergraph products
    Hellmuth, Marc; Ostermeier, Lydia; Stadler, Peter F.
  • A topological approach to evasiveness
    Kahn, Jeff; Saks, Michael; Sturtevant, Dean
  • Further results on the Aanderaa-Rosenberg conjecture
    Kleitman, Daniel J.; Kwiatkowski, David J.
  • Evasiveness through a circuit lens
    Kulkarni, Raghav
  • Any monotone property of 3-uniform hypergraphs is weakly evasive
    Kulkarni, Raghav; Qiao, Youming; Sun, Xiaoming
  • Fixed-point sets of group actions on finite acyclic complexes
    Oliver, Robert
  • 1976/77
    Rivest, Ronald L.; Vuillemin, Jean
  • An Introduction to the Theory of Groups
    Rotman, Joseph J.
  • On the recognition complexity of some graph properties
    Triesch, Eberhard
  • The Method of Trigonometrical Sums in the Theory of Numbers (Russian)
    Vinogradov, Ivan Matveevich
  • Monotone bipartite graph properties are evasive
    Yao, Andrew Chi-Chih