# 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.

6,832
questions

**2**

votes

**1**answer

28 views

### Model for random graphs where clique number remains bounded

In the Erd?s-Rényi model for random graphs,the clique number is seen to go to infinity al the number of vertices grows. Is anyone aware of models for random graphs with bounded ...

**6**

votes

**0**answers

65 views

### On the first sequence without collinear triple

Let $u_n$ be the sequence lexicographically first among the sequences of nonnegative integers with graphs without collinear three points (as for $a_n=n^2$ or $b_n=2^n$). It is a variation of that one.
...

**1**

vote

**0**answers

42 views

### The scutoid as a noninscribable polyhedron

I have no a good backround in combinatorial geometry but I would like to ask next question, because I think that it is interesting.
I know from the book [1], section B18 and the post Combinatorially ...

**2**

votes

**1**answer

37 views

### Chromatic Polynomial when two disjoint graphs are joined at $2$ distinct points

Consider a graph with chromatic polynomial $P(x)$ joined to a clique of order $k$ in two distinct points (joining here just means interesection of points). Then, what is the chromatic polynomial of ...

**5**

votes

**0**answers

48 views

### An upper bound on the minimum number of vertices in a girth 5 graph of chromatic number $k$

Is there a known upper bound on the minimum number of vertices in a graph with girth 5 and chromatic number $k$? Could you also give references for this?

**9**

votes

**4**answers

436 views

### Sums of binomial coefficients weighted by incomplete gamma

I am interested in proving that
$$\sum_{k=0}^n\frac{k}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}=1
$$
and
$$\sum_{k=0}^n\frac{k^2}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}=2.
$$
I verified it numerically ...

**19**

votes

**0**answers

424 views

### On the first sequence without triple in arithmetic progression

In this Numberphile video (from 3:36 to 7:41), Neil Sloane explains an amazing sequence:
It is the lexicographically first among the sequences of positive integers without triple in arithmetic ...

**9**

votes

**2**answers

342 views

### Regular subsets of $\text{PSL}(2, q)$

Suppose a group $G$ acts on a set $\Omega$. Call a subset $A \subset G$ regular (or sharply transitive or simply transitive or...) if for every two points $\omega_1, \omega_2 \in \Omega$ there is a ...

**2**

votes

**1**answer

153 views

### What generalizes symmetric polynomials to other finite groups?

Multivariate polynomial indexed by ${1, \ldots, n}$ are acted on by $S_n$: for $\sigma \in S_n$, define $\sigma(x_i) = x_{\sigma(x_i)}$, etc. Symmetric polynomials are those polynomials which are ...

**4**

votes

**0**answers

56 views

### Is there any edge- but not vertex-transitive polytope in $d\ge 4$ dimensions?

I consider convex polytopes $P\subset\Bbb R^d$. The polytope is called vertex- resp. edge-transitive, if any vertex resp. edge can be mapped to any other by a symmetry of the polytope.
I am looking ...

**1**

vote

**1**answer

33 views

### Induced subgraphs of the line graph of a dense linear hypergraph

Given a hypergraph $H=(V,E)$ we associate to it its line graph $L(H)$ given by $V(L(H)) =E$ and $$E(L(H)) = \big\{\{e_1,e_2\}: e_1\neq e_2 \in E \text{ and } e_1\cap e_2 \neq \emptyset \big\}.$$
We ...

**1**

vote

**1**answer

42 views

### Rank and edges in a combinatorial graph?

Fix a $d\in\mathbb N$ and consider the matrix $M\in\{0,1\}^{2^d\times d}$ of all $0/1$ vectors of length $d$. Consider the matrix $G\in\{0,1\}^{n\times n}$ whose $ij$ the entry is $0$ if inner product ...

**-1**

votes

**0**answers

29 views

### Somewhat complicated Routing Problem [on hold]

Based on routing problems, in this grid, how many ways can you go from A to B? What methods can be used here?
Link to the Image

**2**

votes

**1**answer

111 views

### Combinatorial problem on periodic dyck paths from homological algebra

edit: I added conjecture 2 that looks much more accessible.
Here is the elementary combinatorial translation of the problem (read below for the homological background):
Let $n \geq 2$.
A Nakayama ...

**0**

votes

**1**answer

105 views

### From Steiner systems to geometric lattices to matroids

I am looking for a specific matroid. I found a source that claimed to discuss these matroids, but then, only discusses geometric lattice. Even more, in that paper, the geometric lattice that seems to ...