Mathematical tidbits
Home

1. Homotopy
2. Graph theory
3. Quantum computing
4. Stern sequence
5. Hypertrees
6. Circle packings
7. Presburger arithmetic
8. Complexity
9. Partition function and related functions

This is just a list of facts/definitions that didn't fit elsewhere.

1. Homotopy

1.1. Massey triple product

If [α]⬝[β] = 0 ⇒ α⬝β = dσ. If [β]⬝[γ] = 0 ⇒ β⬝γ = dτ. Then define the triple product with ⟨α, β, γ⟩ = [σ⬝γ - α⬝τ]

Keywords: Operads, A_∞, E_∞. "More associative than (associative) rings. More commutative than commutative rings."

2. Graph theory

Plabic graphs := planar bicolorable graphs.

2.1. Hadwiger's conjecture (1942)

The conjecture states that ∀ t≥1, every graph with no $K_t$ minor is (t-1)-coloring.

The conjecture is known to be true for 1 ≤ t ≤ 6. It implies the four-color theorem.

Linear Hadwiger's conjecture: ∃ C ≥ 1, ∀ t ≥ 1, every graph with no $K_t$ minor is Ct-colorable.

2.2. Minors and Models

These are inverse ideas.

We say that a graph G has an H minor if a graph isomorphic to H can be obtained from a subgraph of G by contracting edges.

Let H be a graph with $V(H) = {v_1, \ldots, v_t}$. A model of H in graph G is a collection of vertex-disjoint connected subgraphs $H_1, \ldots H_t$ such that ∀ i≠j∈[t] with $v_iv_j\in E(H)$, $H_i$ is adjacent to $H_j$ i.e. ∃ an edge with one end in $H_i$ and another end in $H_j$.

G has an H minor iff there exists a model of H in G.

2.3. Graph isomorphism

The graph isomorphism problem is known to be in NP but is one of the few problems for which we don't know if it is also in P or in NP-complete.

2.4. Prague dimension of graphs

Is NP-hard to determine

Let G^c denote the complement of a graph G. Then the Prague dimention is denoted $dim_p(G^c)$ and is the minimum $k$ such that ∃ a clique edge-coloring $C$ of $G$ which can be $k$-colored, i.e. all cliques in each color class are vertex-disjoint.

Note also that – \[dim_p(G^c) = \min_{C\text{ of }G}\chi^1(G) = cc^1(G),\] where $cc^1$ is the clieque chromatic index of $G$.

Note how it is easier to define the Prague dimension for the complement graph than for the graph directly.

2.5. Complement graph

Let $G_{n,p}$ denote the binomial random graph i.e. pick from $\binom{n}{2}$ edges randomly with probability $p$.

The complement graph of $G_{n,p}$ is $G_{n,1-p}$.

3. Quantum computing

3.1. PAC learning model

concept ≡ feature; c : X → {0, 1}
concept class ≡ collection of features
labelled examples (x, c(x))
x ~ D, distribution on X
given t samples (xᵢ, c(xᵢ)), i ∈ [t], compute with probability ≥ 1-δ, hypothesis c' such that Pr_x~D(c'(x) = c(x)) ≥ 1-ε.
Interesting question to ask is what should be the size of t in terms of ε and δ?

Note: a quantum version of sampling this distribution will look like (assuming X is discrete): \[|ψ\rangle = \sum_x \alpha_x |x, c(x)\rangle,\] where $\alpha_x = \sqrt{D(x)}$.

4. Stern sequence

Bruce Reznick has some notes on these at link.

def s : ℕ → ℕ
| 0 := 0
| 1 := 1
| 2n := s(n)
| 2n+1 := s(n) + s(n+1)

5. Hypertrees

wiki: https://en.wikipedia.org/wiki/Hypertree

A hypertree is a hypergraph whose host graph is a tree. Equivalently, h is a hypertree if ∃ a tree t such that ∀ e ∈ h there is a corresponding subtree of t having the same vertex set as e.

A connected graph g is a host graph of a connected hypergraph h if every hyperedge of h induces a connected subgraph in g.

As far as I can see, it is not very east to check if a hypergraph is a hypertree. However, there seem to be some equivalent graph-property-testing definitions for answering this question that are faster to check.

6. Circle packings

6.1. Circle packing – a mathematical tale by Kenneth Stephenson

Type: article
Reference: https://www.math.utk.edu/~kens/Notices_article.pdf
Key idea: Triangulation → Circle packing → Conformal mapping → metric → geometry
Source: This was communicated to Hirani by Nathan.

6.1.1. Triangulations → Circle packing

Original idea: from Thurston's "Note"

The packing is a configuration of circles that are tangent to one another.

Moreover, this packing is unique up to Möbius transformations and inversions of the sphere.

6.1.2. Circle packing (combinatorial data) → Conformal mapping (geometric data)

Original idea: "A finite Riemann mapping theorem", a talk by Thurston

6.1.3. Setup

Notation

$\mathbb{P}$: the sphere
ℂ: the euclidean plane
$\mathbb{D}$: the unit disc

Complex: the tangency patterns for circle packings are encoded as abstract simplicial 2-complexes K. Assume K triangulates an oriented topological surface. (In Graphsat, these complexes are Hypergraphs).

(Circle) Packing: a packing P for K is a configuration of circles such that,

∀ (v : Vertex) ∈ K, ∃ (c_v : Circle) such that
∀ (⟨v, u⟩ : Edge) ∈ K, c_v and c_u are externally tangent.
∀ (⟨v, u, w⟩: Positively-Oriented-Face) ∈ K, ⟨c_v, c_u, c_w⟩ are positively-oriented-triple-of-tangent-circles.

Label: A label R of K is a map of Vertex → ℝ given by v ↦ radius(c_v).

The drawing can be constructed once we know K and R. The position of the vertices is not important, only the adjacencies in K matter. R needs to be computed.

6.1.4. Computing the labels

Flower: a circle surrounding by its tangent circles. The "petals" form an oriented chain of tangent circles. The chain is closed iff the original circle is centered at an internal vertex of K.
Angle sum: θ_R(v) is the sum of all angles incident at the vertex from the petals surrounding it. On other words, the sum is over all faces that are incident at v.
Packing condition: for an interior vertex, the sum must add up to some positive multiple of 2π.

If K is simply connected, then the packing condition suffices to guarantee a packing. If not simply connected, then "global obstructions" become important.

Univalent packing: ?? This part is unclear. Something to do local vs. global. ??

6.1.5. Note

I did not understand the rest of the article. 🤷

6.2. Circle Packing theorem

wiki: https://en.wikipedia.org/wiki/Circle_packing_theorem
related to: circle packing
also called: Koebe-Andreev-Thurston theorem

The interiors of a circle packing must be disjoint. Example image: File:Circle_packing_theorem_K5_minus_edge_example.svg

Circle packing theorem: For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G.

Koebe-Andreev-Thurston theorem: If G is a finite maximal planar graph, then the circle packing whose tangency graph is isomorphic to G is unique, up to Möbius transformations and reflections in lines.

A conformal map between two open sets in the plane or in a higher-dimensional space is a continuous function from one set to the other that preserves the angles between any two curves. The Riemann mapping theorem, formulated by Bernhard Riemann in 1851, states that, for any two open topological disks in the plane, there is a conformal map from one disk to the other.

Thurston used circle packings to find a conformal mapping from an arbitrary open disk A to the interior of a circle. The mapping from one topological disk A to another disk B could then be found by composing the map from A to a circle with the inverse of the map from B to a circle.

6.3. Enumeration of triangulations of the disc by William G. Brown

ref: Enumeration of triangulations of the disk by William G. Brown (paper)

A triangulation of type [n, m] of a disc is a polyhedron Ω having (m+3) exterior vertices and n interior vertices. Extrior edges are edges that have both vertices exterior.

I checked [n, 0] triangulations. They are always satisfiable for n ≤ 4.

7. Presburger arithmetic

Peano's axioms are not decidable.

Presburger Arithmetic (PA) are less powerful than Peano's. PA is consistent PA is complete PA is decidable PA has quantifier eliminanion

PA := ⟨ℤ, +, ≤⟩ is a first order theory for natural numbers.

8. Complexity

General classification of problems in complexity theory –

Representation: efficient, compact encoding
Decomposition: split objects into smallest number of simple objects
Dimension: embed objects into smallest number of one-dimensional objects

9. Partition function and related functions

The partition function counts the number of partitions of an integer n

\begin{align*} 5 &= 5 \\ &= 4+1 \\ &= 3+2 \\ &= 3+1+1 \\ &= 2+2+1 \\ &= 2+1+1+1 \\ &= 1+1+1+1+1 \end{align*}

∴ p(5) = 7.

9.1. Asymptotic formula for p(n)

This is due to Hardy-Ramanujan asymptotic. \[p(n) \sim \frac{1}{4n\sqrt{3}}e^{\pi\sqrt{2n/3}}\]

9.2. Congruences due to Ramanujan

p(5k+4) ≡ 0 mod 5
p(7k+5) ≡ 0 mod 7
p(11k+6) ≡ 0 mod 11

9.3. Recurrence relation for p(n)

\[p(n) = \frac{1}{n}\sum_{k=0}^{n-1}\sigma(n-k)p(k),\] where $\sigma$ is the sum of divisors.

9.4. Rademacher's formula

\[p(n) = 2\pi(24n-1)^{3/4}\sum_{c=1}^\infty\frac{A_c(n)}{c}I_{3/2}\left(\frac{\lambda(n)}{c}\right),\]

where $A_c(n)$ is the generalized Kloosterman sum and $I_{3/2}$ is the $3/2$-I-Bessel function.

9.5. k-colored partition function

$p_k(n) := k$-colored partition function.

9.5.1. Example

\begin{align*} 2 &= 2_r \\ &= 2_b \\ &= 1_r + 1_r \\ &= 1_b + 1_b \\ &= 1_r + 1_b \end{align*}

∴ $p_2(2) = 5$

9.6. Smallest parts function

$spt(n)$ counts the number of smallest parts among the partitions of n.

\begin{align*} 5 &= \textbf{5} \\ &= 4+\textbf{1} \\ &= 3+\textbf{2} \\ &= 3+\textbf{1}+\textbf{1} \\ &= 2+2+\textbf{1} \\ &= 2+\textbf{1}+\textbf{1}+\textbf{1} \\ &= \textbf{1}+\textbf{1}+\textbf{1}+\textbf{1}+\textbf{1} \end{align*}

∴ $spt(5) = 14$.

9.6.1. Asymptotics

It is surprising that the small parts function has "nice" assymptotics/recurrence etc.

\[spt(n) \sim \frac{\sqrt{6}}{\pi}\sqrt{n}p(n)\]

Mathematical tidbits Home

Table of Contents