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

7,551
questions

**3**

votes

**0**answers

20 views

### Invertibility of discrete Laplacian

In QFT and Statistical Mechanics the discrete Laplacian usually plays a key role when we want to discretize the theory. However, few books (at least to my knowledge) really work the properties of this ...

**1**

vote

**0**answers

56 views

### $V$-like actions of $V$

This continues my question about prefix-continuous bijections (since the answer was "yes").
Notation and conventions: Let $A$ be a finite alphabet and $L \subset A^*$ a language. Let $G$ be a group. ...

**8**

votes

**0**answers

58 views

### $\mathfrak{sl}_3$ webs without faces having a multiple of 4 sides

In settling the main conjecture of Cyclic action on Kreweras walks, see https://arxiv.org/abs/2005.14031, a rather interesting object popped up.
Recall from
Kuperberg, Greg, Spiders for
rank 2 Lie ...

**1**

vote

**0**answers

29 views

### Bandwidth of two-dimensional grid graphs

Suppose that $G$ is a subgraph of the two-dimensional grid and there are $n$ vertices in $G$. What is the maximum possible graph bandwidth of $G$ as a function of $n$?
If $G$ is a square grid graph ...

**0**

votes

**0**answers

54 views

### A number related to rank

Given $n$ a natural number we know minimum $m$ over all choices of $v_i=\begin{bmatrix}a_{i1}\\\vdots\\a_{in}\end{bmatrix}\in\mathbb R^n$ such that $$I=\sum_{i=1}^mv_iv_i'$$ holds where $'$ is ...

**0**

votes

**0**answers

24 views

### Similar polynomial forms over different rings

The aim of this post is to know about results related to polynomial expressions evaluated over different rings (with respect to different operations of the ring).
Suppose we have a polynomial $P_d$ ...

**6**

votes

**1**answer

128 views

### Is there a prefix-continuous bijection between finite words and eventually zero words?

Let
$$ X = \{x \in \{0,1\}^{\omega} \;|\; \exists m: \forall i \geq m: x_i = 0\} $$
(one-way infinite eventually zero words). Let $\{0,1\}^*$ denote the finite (not necessarily nonempty) words over $\{...

**0**

votes

**0**answers

21 views

### On full rank submatrices of a construction

Take two matrices $T_1$ and $T_2$ in $\mathbb Z^{n\times n}$ with entries uniformly in $[-b,b]\cap\mathbb Z$ at some $b>0$. The matrices will be of rank $n$ each with probability at least $1-\frac1{...

**5**

votes

**1**answer

191 views

### Size of a family of sets of $k$-separated functions over $\{0,1,\ldots,n-1\}$

For $n\ge 1$ we write $[n]$ to denote the set $\{0,1,\ldots,n-1\}$. Let $2^{[n]}$ be the set of all functions from $[n]$ to $\{0,1\}$. Let $\mathcal{F}$ and $\mathcal{G}$ be two nonempty subsets of $2^...

**-1**

votes

**1**answer

56 views

### Effect of collapsing two vertices of distance $2$

Motivating example. Consider the graph $G=(V,E)$ with $V = \{0,1,2,3\}$ and $E = \big\{\{i,i+1\}: i\in \{0,1,2\}\big\}$. We have $\chi(G) = 2$, but if we collapse $0$ and $3$, we get the complete ...

**1**

vote

**0**answers

46 views

### Number of solutions to linear diophantine equations, with natural coefficients in a box

Let c, k, d $ \in \mathbb{N} $, let a, x $ \in \mathbb{N}^k $ suppose for all i $ \leq $ k, $ x_i \leq d $, $ a_i \in \mathcal{O}(d2^i) $ and $ \sum{a_ix_i} = c $ my question is for the value of c ...

**5**

votes

**1**answer

84 views

### What is known about the duals of cyclic polytopes?

What is known about the duals of cyclic polytopes, in particular, their facets (or equivalently, the vertex-figures of cyclic polytopes)?
In even dimensions, all facets of the dual are ...

**3**

votes

**1**answer

168 views

### Number of points in a lattice and an oblong box

I have a very simple question in geometry of numbers. (It is a slight modification of Counting points on the intersection of a box and a lattice .) There's a bound I can easily prove, and it's good ...

**4**

votes

**0**answers

106 views

### The Jacobson radical as a bimodule

Let $A$ be a finite dimensional algebra with Jacobson radical $J$.
Question 1: In case $A$ is a Nakayama algebra with a linear quiver corresponding to a Dyck path $D$ (via its Auslander-Reiten ...

**2**

votes

**0**answers

55 views

### Balanced Gray codes for powers of 2

All of the binary 4-bit cyclic balanced Gray code sequences can be formed from simple reversals, bit-permutations, and circular shifts of the one Wikipedia example:
...

**2**

votes

**0**answers

73 views

### Generalized partitions

Let $\kappa>0$ be a cardinal and $X$ be a set. We set $[X]^\kappa = \{A \in {\cal P}(X): |A| = \kappa\}$.
If ${\cal A}\subseteq {\cal P}(X)$ we say that ${\cal B} \subseteq {\cal P}(X)$ is an ${\...

**0**

votes

**1**answer

30 views

### Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques

Let $G$ be a perfect/ weakly perfect Cayley graph on an abelian group with respect to a symmetric generating set. In addition let the clique number be $\omega$ which divides the order of graph $n$. ...

**7**

votes

**1**answer

372 views

+50

### Boundedness of total current in electrical network

Consider the following symmetric matrix (adjacency matrix):
$$A=(a_{ij})_{1\leq i,j\leq n}$$
such that $a_{ij}=a_{ji}, a_{ii}=0$ and $a_{ij}=0$ for $|i-j|\geq k$ where $k\geq3$. We also have $1\leq a_{...

**6**

votes

**0**answers

84 views

### Any comparison between the category of cubes and its opposite?

To model topological spaces combinatorially, one can use simplicial sets -- or cubical sets. Simplicial sets are defined as presheaves on the simplex category $\Delta$, the category of non-empty ...

**3**

votes

**1**answer

140 views

### Is there a 4-polytope without 3-gonal and 4-gonal faces, other than the 120-cell?

The question is in the title:
Question: Is there any 4-dimensional polytope without 3-gonal and 4-gonal faces (of dimension two), other than the 120-cell?
I consider only convex polytopes (convex ...

**1**

vote

**1**answer

130 views

### Cayley graphs do not have isolated maximal cliques

Let a Cayley graph $G$ of a group $H$ with respect to the generating set $\{s_i\}$ have a clique of order $> 2$. In addition assume the graph $G$ is non-complete. If the clique size is less than ...

**4**

votes

**0**answers

68 views

### Maximal number of commuting functions of a finite set

Let $S$ be a finite set with $n$ elements and let $F_S$ denote the set of functions from $S$ to $S$. I wonder whether anything is known about the maximal cardinality of a commuting subset of $F_S$? A ...

**9**

votes

**1**answer

150 views

### Lattice structure in the root poset

Let $W$ be a Coxeter group with simple generators $s_1$, $s_2$, ..., $s_r$. Let $\Phi^+$ be the corresponding positive root system, with $\alpha_i$ the positive root corresponding to $s_i$. Bjorner ...

**0**

votes

**0**answers

33 views

### Generalization of multinomial theorem for powers of multinomial coefficients

I am trying to estimate the following expectation value in the multinomial probability distribution:
\begin{equation}
\mathbb{E}_{P}\left[ \left( \frac{n!}{x_1!..x_k!}\right)^{\alpha - 1} \right]
\...

**0**

votes

**0**answers

29 views

### Average number of edges of an induced graph by using the edge-based node selection technique on a graph with arbitrary degree distribution

Let $G(U,V,E)$ be a simple, undirected, bipartite graph and $U=\{u_1,u_2,{\cdots},u_n\}$ and $V=\{ v_{1},v_{2},\cdots,v_{n}\}$. Let $d_k^l$ be the number of vertex with degree $k$ in $l$, where $l \in ...

**1**

vote

**1**answer

143 views

### Do there exist graphs whose adjacency matrix is positive semi-definite? [closed]

If so, could you provide examples and specify the conditions under which this occurs? Thank you in advance

**1**

vote

**1**answer

86 views

### Explanation of a proof of an embedding lemma of Bollobas and Thomason

I do not understand the proof of Bollobas and Thomason of an embedding lemma. There is a lot of notation to present first, then the statement of the lemma, then the precise question about the proof.
...

**7**

votes

**0**answers

247 views

### Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?

Is the following lemma a well known result in graph theory?
I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...

**8**

votes

**1**answer

86 views

### Sizes of connected components from a random choice in a grid

This is inspired by the illustration in this recently updated question. So we take a (fairly big) $n$ and an $n \times n$ grid where we draw at random one diagonal in each of the $1 \times 1$ squares. ...

**1**

vote

**0**answers

50 views

### Untruncate permutohedron of order 5

I would like to understand commutation classes of reduced expressions of the longest element in $S_5$ a little better. For this, it makes sense to look at the permutohedron of order 5. Since I am only ...

**3**

votes

**4**answers

387 views

### Can one show combinatorially how $\operatorname{lcm}(1, \dotsc, n)$ grows?

Let us write $M(n)$ for $\operatorname{lcm}(1,\dotsc,n)$ for $n$ a positive integer. Asymptotically $M(n)$ tends toward $e^n$. This result uses analytic number theory. (Lcm is least common multiple, ...

**-2**

votes

**0**answers

16 views

### Search Algorithm in d-D Tucker

The algorithm of search a complementary edge in TUCKER seems to need at most O(n^2) time complexity. How to query with fewer vertices?

**29**

votes

**1**answer

734 views

### Sum over 0-1 matrices

I stumbled across the following formula when working on a research problem in theoretical computer science. I am looking for a simple proof of it, or any idea which might prove useful.
I checked its ...

**1**

vote

**1**answer

123 views

### Monge's solution to the 'transporting earth' problem

In Schrijver's A course in combinatorial optimization (page 49, Application 3.3), I came across the transporting earth problem which is quoted below (replaced the French text by its English ...

**13**

votes

**5**answers

1k views

### Striking existence theorems with mild conditions, and simple to state: more recent examples?

I would like to write an article about powerful existence theorems that assert, under mild and simple conditions, that some basic pattern or regularity exist. See some examples below. By mild ...

**12**

votes

**0**answers

261 views

### Combinatorial proof of invertibility of a symmetric matrix associated to the ring of matrices over a finite field

Let $F$ be a finite field of $q$ elements with characteristic $p$. Let $M_n(F)$ be the ring of $n\times n$ matrices over $F$. We define a $q^{n^2}\times q^{n^2}$ symmetric matrix $L$ over the ...

**2**

votes

**0**answers

114 views

### Graphs which are built from complete graphs : Reference request

Let $V$ be a set of $n$ vertices. Fix $3 \le k \le n$. Let $\binom V k$ be the set of all $k$ element subsets of $V$.
We add the edges in $V$ as follows: Let $\mathcal S \subseteq \binom V k$ be ...

**7**

votes

**1**answer

171 views

### Induction step in Bóna and Ehrenborg's proof that the generating function of the alternating runs has -1 as a root of a certain multiplicity

This is a crosspost of a question I asked on Mathematics SE four months ago. Periodically bumping it and placing a bounty on it to attract more attention were to no avail. There are some comments ...

**0**

votes

**0**answers

33 views

### Visualization of higher Bruhat order B(5,2)

I made the following images of the higher Bruhat order B(5,2) (in the sense of Manin/Schechtman) with vZome:
image 1
image 2
image 3
Unfortunately, in vZome its not possible do have regular octagons,...

**2**

votes

**0**answers

42 views

### The expected size of a subtree of any labelled rooted tree

Consider the set of labelled rooted trees of size $n$, $\mathcal{T}_n$. Let $r$ be the root of each tree $T=(V,E)\in\mathcal{T}$, $r\in V(T)$, and let $n(u)$ be the number of vertices of the subtree $...

**1**

vote

**1**answer

47 views

### Relation between expected values of eigenvalues of Laplacian matrix of a graph and eigenvalues of expected Laplacian matrix of that graph?

Particularly, I am dealing with Erdős–Rényi random 𝐺(𝑛,𝑝), so the expected Laplacian matrix of 𝐺(𝑛,𝑝) is 𝑝(𝐽𝑛−𝐼𝑛), where 𝐽𝑛 and 𝐼𝑛 are one and identity matrices, respectively.
In ...

**1**

vote

**2**answers

40 views

### Cyclic inequality for 2 dimensional simplex elements

Let $p=(p_{1},p_{2},p_{3})\in\Delta$, with $\Delta:=\lbrace p\in(0,1)^{3}\ |\ p_{1}+p_{2}+p_{3}=1 \rbrace$. I aim to prove (not knowing whether it is true though) that
\begin{equation}
p_{1}^{p_{3}-p_{...

**6**

votes

**1**answer

193 views

### Cartesian dissimilarity of a function $\ f:A^3\to A^3\ $ and its inverse

Let $\ A\ $ be an arbitrary set. Let $\ |A|>1\ $ (to avoid triviality). Let each of the functions $\ f_k:A^{\{1\ 2\ 3\}}\to A\ $ depend on all three arguments for $\ k=1\ 2\ 3,\ $ while each of the ...

**3**

votes

**0**answers

36 views

### Size of the smallest union chain containing a family

A family of sets $\mathcal{F}$ is a union chain if each set in $\mathcal{F}$ of size at least $2$ is the union of two other sets in $\mathcal{F}$. That is, $X\in \mathcal{F}$ and $|X|\geq 2$, then $X=...

**0**

votes

**0**answers

42 views

### Lower bounds on the length of circuits, depending on the number of times it crosses itself

I have this problem that I have been stuck on for months, and would like to know if somebody can tell me a way to attack the problem. Let me ask the problem in a simple example below.
Let $G(V,E)$ be ...

**1**

vote

**0**answers

84 views

### Do you recognise this setup of structure on a poset?

The setup is that we have a finite poset $P$, with a multiplicative rank function $r_{xy}:P\times P\rightarrow \mathbb{N}$, and a symmetric pairing $\langle\ ,\ \rangle:P\times P\rightarrow\mathbb{N}$....

**2**

votes

**0**answers

70 views

### How many ways to cover a N×N chessboard with white and black boxes by some restrictions?

Suppose we have a N×N chessboard and the boxes ■, □.
We should cover the chessboard with those boxes but there can not have the 2×2 square $\scriptstyle{\begin{array}{cc}\square&\square\\
\...

**2**

votes

**1**answer

127 views

### Average number of elements of a subset S of a matrix A after inducing the rows and columns of m randomly selected elements from subset S

Let $A_{N{\times}N}$ be an $N{\times}N$ matrix and $\mathcal{S_{k}}$ be a subset of elements in $A$ such that exactly $k$ elements from every row and column in $A$ are in $\mathcal{S_{k}}$. Thus, $\...

**0**

votes

**0**answers

89 views

### How many Shapes are possible to create using Voxels?

Let's suppose I have Big Cube of x cm by y cm by z cm, simmilar to this one:
This big cube is made of tiny little cubes of t cm.
All of this little cubes are transparent, but some of them are red
...

**4**

votes

**0**answers

80 views

### What is a fast way to multiply a Schubert polynomial by an elementary symmetric polynomial (specifically $x_1\cdots x_k$)?

What is a computationally fast way to get the coefficients of Schubert polynomials in the expansion of the product of a Schubert polynomial and an elementary symmetric polynomial? I know "fast" is ...