20

I'm not sure if this is exactly what you're looking for, but the main topic of Herb Wilf's article What is an Answer? is how to answer the question "How many ______ are there?" His basic thesis is that an alleged answer to such a question is satisfactory only if it provides an algorithm whose computational complexity is significantly less than the ...


10

Six years later it's hard to know if this is still a question of interest. For the record (since I stumbled across the question), the answer is yes and it's a consequence of a more general phenomenon. The main theorem of the paper of Stevens and Warren (Thm 5 in https://arxiv.org/abs/2102.05446) states that for any convex (or concave) functions $f, g:\mathbb{...


7

Let $\Delta$ be a matroid complex, i.e., an abstract simplicial complex whose faces are the independent sets of a matroid $M$. Let $K[\Delta]$ denote the face ring (aka "Stanley-Reisner ring") of $\Delta$ over a field $K$. Let $\beta_i(K[\Delta])$ denote the Betti numbers of a minimal free resolution of $K[\Delta]$, regarded as a module (in fact, ...


6

If I understand what you are looking for, I think (even though it's a noun) the term combinatorial Gray code can be an answer to your question. A combinatorial Gray code gives a means of listing a particular class of objects in an order which differ by a small amount (e.g. a classical Gray code which list binary strings by a single bit flip, listing subsets ...


5

The upper bound in Makowsky and Rotics says that with 4 labels, you can build $P_{n-1}$ in such a way that the two leaves have unique labels. From there you merely insert one more vertex with a fourth label, and make it adjacent to the two leaves of your $P_{n-1}$ to get $C_n$. This actually shows that the linear clique-width of $C_n$ is at most $4$, and it ...


5

If $G=(V,E)$ is a countable graph, you can partition $\omega$ into disjoint infinite sets $A_x$ indexed by $x\in\binom V1\cup\binom V2$ and define an injective map $f:V\to[\omega]^\omega$ by $$f(v)=\bigcup\{A_{\{v,w\}}:w\in V\setminus N_G(v)\}\supseteq A_{\{v\}};$$ then $f(v)\cap f(w)=\varnothing$ if $\{v,w\}\in E$ and $f(v)\cap f(w)=A_{\{v,w\}}$ otherwise.


5

For a graph $G$, the $t$-th power of $G$ is the graph $G^t$ with the same vertex set as $G$ and where two vertices are adjacent in $G^t$ if they are connected by a path with at most $t$ edges in $G$. The distance-$t$ chromatic number of $G$, often denoted $\chi_t(G)$, is the chromatic number of $G^t$. As noted by Sam Hopkins in the comments, you are asking ...


4

Hint: it's always worth checking the Online Encyclopedia of Integer Sequences. For $r=3$ the values of $N$ are the sequence A002426. There's a wealth of literature references, a number of comments which you could try generalising, and the asymptotic $N \sim \sqrt{\frac{3}{8\pi}} 3^m m^{-1/2}$. For $r=4$ the sequence is A005725. There's a recurrence for the g....


3

I claim that every graph with $\leq \aleph_1$ vertices can be embedded in $[\omega]^\omega$ in the manner Dominic described. This means that we have a consistent answer to Dominic's question: the answer is yes assuming that the Continuum Hypothesis holds. Recall that $\mathcal P(\omega) / \mathrm{fin}$ denotes the Boolean algebra of all subsets of $\omega$ ...


3

My first thought for the case where $|V|\leq \aleph_0$ is that surely the Rado graph can be constructed as an induced subgraph of $([\omega]^{\omega}, E)$ (since the Rado graph contains a copy of every finite or countably infinite graph, you are then done). Indeed, this is shown in "Existential closure of block intersection graphs of infinite designs ...


3

Expanding on my comment, here's what the two steps look like combinatorially. Induction from $S_k$ to $B_k$ sends $S^\lambda$ to $\bigoplus_{\mu, \gamma} W(\mu,\gamma)^{\oplus c^\lambda_{\mu,\gamma}}$ where $c^\lambda_{\mu,\gamma} $ denotes a Littlewood–Richardson coefficient. This I think is easy to see using Frobenius reciprocity and the fact that $W(\mu,\...


3

This is just a comment, but too long to fit in the 600 character limit. It would be interesting for someone to compile a list of all functions $B(n)$ for which some combinatorial use has been found for a generating function $\sum a_n\frac{x^n}{B(n)}$. Moreover, for which of these functions $B(n)$ can an example of such a generating function be given that ...


Only top voted, non community-wiki answers of a minimum length are eligible