PaperlayerView exact revision on arXiv

Source-linked AI summary

Eigenvalues and Linear Quasirandom Hypergraphs

John Lenz, Dhruv Mubayi

arXiv:1208.4863v4math.CO

TL;DR

The paper addresses whether hypergraph quasirandomness has an eigenvalue criterion equivalent to established counting properties. It defines spectral and related properties for proper partitions and proves equivalences under a coregularity condition, with a stated exception for one implication.

  • Problem

    For k-uniform hypergraphs, the spectral property Eig equivalent to Disc had not been generalized, leaving open the question posed by Conlon, Han, Person, and Schacht.

    Source: §1.2 · p. 3

  • Method

    For each proper partition π, the paper defines expansion, eigenvalue, and cycle properties and studies their equivalence for looped, coregular hypergraph sequences.

    Source: §1.2 · pp. 3–4

  • Results

    For looped, ⌊pn⌋-coregular sequences, the paper proves equivalences among its hypergraph expansion, eigenvalue, and cycle properties for each proper partition π.

    Source: §1.2 · pp. 3–4

  • Takeaways & Limitations

    The results provide a spectral criterion alongside counting and expansion criteria for the stated class of hypergraphs.

    Source: §1.2 · pp. 3–4

    The main theorem assumes looped, ⌊pn⌋-coregular sequences; all implications except Cycle4ℓ[π] ⇒ Eig[π] are stated to hold under the weaker edge-density condition.

    Source: §1.2 · p. 4

Abstract

from arXiv · show

Let p(k) denote the partition function of k. For each k >= 2, we describe a list of p(k)-1 quasirandom properties that a k-uniform hypergraph can have. Our work connects previous notions on linear hypergraph quasirandomness of Kohayakawa-R\"odl-Skokan and Conlon-H\`{a}n-Person-Schacht and the spectral approach of Friedman-Wigderson. For each of the quasirandom properties that are described, we define a largest and second largest eigenvalue. We show that a hypergraph satisfies these quasirandom properties if and only if it has a large spectral gap. This answers a question of Conlon-H\`{a}n-Person-Schacht. Our work can be viewed as a partial extension to hypergraphs of the seminal spectral results of Chung-Graham-Wilson for graphs.

1 Introduction

Building on graph quasirandomness and earlier hypergraph counting criteria, the paper develops spectral criteria for hypergraph quasirandomness. It proves equivalences among counting, expansion, cycle, and eigenvalue properties under specified conditions.

1.1 Previous Results

  • Kohayakawa, Nagle, Rdl, and Schacht showed that Disc is equivalent to counting linear hypergraphs, while Conlon, Han, Person, and Schacht linked Disc to a linear four-cycle count.Earlier strengthened quasirandomness properties were also shown equivalent to Count[All].Source: §1.1 · p. 2

1.2 Our Results

  • For every proper partition π, the paper defines Expand[π], Eig[π], and Cycle4[π] and proves them equivalent for looped, ⌊pn⌋-coregular hypergraph sequences.Eig[π] requires λ1,π(Hn) = p n^k/2 + o(n^k/2) and λ2,π(Hn) = o(n^k/2).Source: §1.2 · pp. 3–4
  • The results include counting labeled copies of each fixed π-linear hypergraph and upper bounds on copies of the π-type four-cycle and longer cycles.The respective properties are Count[π-linear], Cycle4[π], and Cycle4ℓ[π].Source: §1.2 · p. 4
  • The authors report that all stated implications except Cycle4ℓ[π] ⇒ Eig[π] hold with the weaker edge-density condition |E(Hn)| ≥ p replacing coregularity.A companion paper proves that remaining implication for sequences of looped hypergraphs with the stated density condition.Source: §1.2 · p. 4
  • For π = 1 + 85 + 1, the stated equivalences recover the weak quasirandom properties studied by Kohayakawa, Rdl, and Skokan and Conlon, Han, Person, and Schacht.In this case, Eig[π] is the corresponding spectral property.Source: §1.2 · p. 5
  • Partition refinement orders the expansion properties: refinement implies the corresponding Count[π-linear] implication, while a companion paper [33] proves distinctness for non-refinements.The paper describes these properties as distinct and arranged in a poset via partition refinement.Source: §1.2 · p. 5

2 Hypergraph Cycles

The paper builds hypergraph cycles from partition-dependent steps, joining attach tuples into paths and identifying path endpoints to form cycles. The resulting cycle is independent, up to isomorphism, of the ordering of its partition.

2 Hypergraph Cycles

  • For a partition π = (k1, . . . , kt), the step enlarges each vertex of the all-ones step into the corresponding part size and has two attach tuples.The attach tuples consist of vertices whose binary codes end in zero or one.Source: §2 · p. 5
  • A path of length 2ℓ concatenates ℓ steps by identifying successive attach tuples, and a cycle identifies the path’s two remaining attach tuples.The cycle construction is stated for ℓ ≥ 2.Source: §2 · pp. 5–7
  • Reordering the parts of π does not change the cycle up to isomorphism, so Cπ,2ℓ can be defined using any ordering of π.The proof builds the cycle from ℓ copies of a step with a cyclically shifted partition ordering.Source: §2 · pp. 7–8
  • A walk is an edge-preserving map from the path into a hypergraph, while a circuit is an edge-preserving map from the cycle, allowing vertices to repeat.Source: §2 · p. 8
  • For length four, a direct binary-string definition avoids the step-and-path construction, while the all-ones cycle also matches Conlon et al.’s reflection definition.In the direct definition, an edge is formed when each part’s code deletes a different bit from a shared binary string.Source: §2 · p. 8

3 Hypergraph Eigenvalues

The paper defines largest and second largest hypergraph eigenvalues with respect to a partition, using adjacency maps and tensor products. These definitions extend familiar graph eigenvalues and relate to earlier hypergraph definitions.

3 Hypergraph Eigenvalues

  • The eigenvalue framework starts from the symmetric k-linear adjacency map of a hypergraph, whose values on vertex indicators encode edges.Friedman and Wigderson’s approach is the starting point selected for the paper’s purposes.Source: §3 · pp. 9–10
  • For π = 1 + · · · + 1, the largest eigenvalue is the spectral norm of the adjacency map and the second measures the norm after subtracting the all-ones contribution.The section introduces this case before extending the definitions to general partitions.Source: §3 · p. 10
  • For a general ordered partition, tensor products group the coordinates into blocks of sizes k1, . . . , kt, yielding a t-linear map used to define λ1,π(H) and λ2,π(H).The lifted map is defined on tensor-product spaces indexed by ordered ki-sets of vertices.Source: §3 · pp. 10–11
  • For graphs, λ1,1+1 matches the largest adjacency-matrix eigenvalue in absolute value, and for regular graphs λ2,1+1 matches the second largest in absolute value.For hypergraphs with loops, the all-ones-partition definitions match Friedman and Wigderson’s definitions in the stated cases.Source: §3 · p. 11

4 Eig[π] ⇒Expand[π]

This section connects eigenvalues to expansion through a hypergraph Expander Mixing Lemma. It uses the largest eigenvalue to establish the expected edge density and the second eigenvalue to control discrepancies.

4 Eig[π] ⇒Expand[π]

  • The hypergraph Expander Mixing Lemma bounds the discrepancy between e(S1, . . . , St) and its density-based expectation using λ2,π(H).Here e(S1, . . . , St) counts ordered tuples whose union is an edge, with each si drawn from Si.Source: §4 · p. 12
  • If λ1,π(Hn) = p n^k/2 + o(n^k/2), then the sequence has |E(Hn)| = p n^k/k! + o(n^k) edges.Source: §4 · p. 13
  • Together, the eigenvalue conditions in Eig[π] imply Expand[π]: the edge density fixes the expected count and λ2,π(H) = o(n^k/2) makes the discrepancy term small.Source: §4 · p. 13

5 Expand[π] ⇒Count[π-linear]

The section proves that expansion yields the expected counts of fixed π-linear hypergraphs. Its embedding argument inductively extends copies after removing a final edge.

5 Expand[π] ⇒Count[π-linear]

  • Under the stated density and expansion assumptions, every fixed π-linear hypergraph F with m edges and f vertices has p^m n^f + o(n^f) labeled copies.Source: §5 · p. 14
  • The proof removes the last edge in a π-linear ordering, then partitions that edge into A1, . . . , At to group its intersections with earlier edges.Each group Ai has size ki for the partition π = (k1, . . . , kt).Source: §5 · p. 14
  • For each embedded remainder, the proof forms sets Si(Q*) of possible ki-vertex extensions and uses expansion to count edges across those sets.The number of labeled extensions also accounts for the fixed ordering multiplicities Δi.Source: §5 · pp. 14–15
  • Induction applies because deleting the final edge preserves π-linearity, allowing the count for the smaller hypergraph to extend to F.Source: §5 · p. 15

6 Cycle4ℓ[π] ⇒Eig[π]

This section proves that Cycle4ℓ[π] implies Eig[π] for sequences of d-coregular, k-uniform hypergraphs with loops, using powers of multilinear maps to connect cycle counts with eigenvalues.

6 Cycle4ℓ[π] ⇒Eig[π]

  • For d-coregular k-uniform hypergraph sequences with loops, Cycle4ℓ[π] implies Eig[π].In this setting, λ1,π(H) = d n^(k/2−1), and the vectors maximizing τ⃗π are scaled all-ones vectors; companion paper develops the algebra for the implication without the coregularity restriction.Source: §6 · p. 15

6.1 Products and powers of multilinear maps

  • Multilinear-map products contract a shared argument, and recursively defined powers yield a symmetric matrix used in the spectral argument.The powers are defined for exponents that are powers of two because the product requires matching domains.Source: §6.1 · p. 16

6.2 Counting walks and circuits

  • Powers of the adjacency map count labeled walks, while traces of those powers count circuits.The walk counts include possibly degenerate copies and walks of length 2ℓ.Source: §6.2 · pp. 17, 20

6.3 Bounding eigenvalues from cycle counts

  • Multilinear-map inequalities and d-coregularity bound the second eigenvalue from cycle counts, yielding the stated implication.The argument uses the regularity of step counts for fixed attach tuples.Source: §6 · p. 15, §6.3 · pp. 22–23
  • The proof orders the eigenvalues by absolute value for a square symmetric matrix A and uses the bound on its second eigenvalue to obtain the spectral conclusion.The matrix is A[τ^(2t−1)_π].Source: §6.3 · p. 23
  • Under Cycle4ℓ[π], λ2,π(H) = o(n^(k/2)), establishing Eig[π] for the stated hypergraph sequences.The proof concludes that the second eigenvalue of the constructed matrix is o(n^(2t−2)k), then applies Corollary 12.Source: §6.3 · p. 23
Loading 1208.4863v4…