# Tag Info

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