# Questions tagged [co.combinatorics]

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

8,687 questions
Filter by
Sorted by
Tagged with
207 views

57 views

### Maximum size of vertex set with no induced connected component on more than k vertices

An independent set of a graph is a collection of vertices such that the induced subgraph consists of disconnected vertices. The maximum possible cardinality of an independent set is then called the ...
187 views

### Continued fraction associated to KdV solitons

Background (may be skipped by those interested only in the basic question and not important associations): “An essay on continued fractions” by Euler (translated by Myra and Bostwick Wyman) contains ...
148 views

77 views

### What property of ranked poset ensures that it is determined by its vertex-facet incidences?

For a convex polytope, its face poset is combinatorially determined by vertex-facet incidences. Now suppose we have an arbitrary finite poset that is ranked, so I can still speak of vertices and ...
128 views

### Relationship between Lambert $W$ function and Hypergeometric function

The Lambert $W$ Function is defined in this Wikipedia entry, while the Hypergeometric Function is defined in this other Wikipedia entry. There exists also a multivariate generalization which solves ...
147 views

163 views

### At most one perfect matching of a bipartite graph

I. Given biadjacency matrix $A$ of a bipartite graph on $2n$ vertices having $n$ vertices of either color on the constraints the graph either has $0$ perfect matchings $1$ perfect matchings is it ...
68 views

### Why is Schröder numbers equivalent to the number of perfect matchings for triangular grid of n squares and how the graph look like? [duplicate]

In the OEIS entry for the Schröder numbers is A006318. There is a comment which related the sequence to perfect matchings: The number of perfect matchings in a triangular grid of n squares (n = 1, 4, ...
405 views

### Real rootedness of a polynomial with binomial coefficients

It is possible to show using diverse techniques that the following polynomial: P_n(x)=1 + \binom{n}{2} x + \binom{n}{4} x^2 + \binom{n}{6} x^3 + \binom{n}{8} x^4 +\ldots + \binom{n}{2\lfloor\tfrac{n}...
57 views

### Subgraph isomorphism problem with linear map

I am working on proving the NP-hardness of a problem by reducing it from the subgraph isomorphism problem. Currently, I can reduce it from the following problem: Problem 1: Given two graphs $G=(V, E)$ ...
For any $n \in \mathbb{N}$ and $B \in \mathbb{R}_{\geq 0}$, let $\mathcal{P}(n,B)$ be the set of $n$-dimensional convex polytopes $\Delta \subseteq \mathbb{R}^n$, taken up to integral, unimodular ...