Search Results

I've been pondering the following generalisation of a famous problem (the special case where $T = \mathbb{N})$: Question: We have some totally-ordered set $T$ of mathematicians, each wearing a hat wh …

There's an extremely elementary theorem whose only known proof relies on the existence of a rank-into-rank cardinal (basically the strongest large cardinal axiom not known to contradict ZFC). Let $R_ …

I can, at least, answer your question 'Is this in fact the correct answer?' with an affirmative 'no'. Specifically, we can replace the upper bound $2^{n/3} \approxeq 1.26^n$ with the slightly better …

A graph $G$ is described as a unit-distance graph if there exists a function $f:G \rightarrow \mathbb{C}$ such that for every edge $(u,v) \in E(G)$, we have $|f(u) - f(v)| = 1$. Obviously, we can nec …

The outer automorphism of $S_6$.

Here's an example (credit: Paul Russell) of the sort of bijection you want to rule out. Question: Find an explicit bijection $f$ between the size-$k$ and size-$(k + 1)$ subsets of $\{1, 2, \dots, 2k+ …

Let $\mathcal{G}$ be the set of isomorphism classes of finite groups. There is an operation $\mathrm{Aut} : \mathcal{G} \rightarrow \mathcal{G}$ which gives the automorphism group of a given group, u …

I can prove that all sufficiently large integers are representable. Firstly, observe that there is a unique way, up to isomorphism, to choose three edges $p, q, r$ of the Petersen graph such that the …

There are no such graphs when $n$ is odd, by the handshaking lemma. Conversely, for all even $n \geq 224$, we claim such a graph exists. In particular, given two planar 5-regular graphs $G$, $H$ each …

Theorem (difficult): Every planar graph can have its edges directed such that the indegree of each vertex is $\leq 3$. Strengthening (easy): Every plane graph can have its edges directed such that th …

Yes, your conjecture is true. Suppose otherwise. Then there exists a counterexample $f : \mathcal{P}(8) \rightarrow \{0, 1\}$. For each set $X \in \mathcal{P}(8)$, let the proposition $P_X$ denote $f …

The Leech lattice $\Lambda_{24}$ answers your question with quite a large multiplicity. The unique $24$-dimensional laminated lattice, defined by $\Lambda_0$ being the one-point lattice and $\Lambda …

Let $\mathbb{F}_q$ be a finite field and $k$ be a positive integer. If we colour each point of the infinite-dimensional projective space $\mathbb{F}_q \mathbb{P}^{\infty}$ with one of $k$ colours, can …

Lemma: Someone only able to speak an infinite cubefree word can convey information at least $1/24$ of the speed of an ordinary person able to speak an arbitrary binary sequence. Proof: Consider the f …

There exists a polynomial-time reduction from the NP-complete partition problem (special case of the subset sum problem) to determining whether a finite graph is a subgraph of the triangular lattice. …