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.

Filter by
Sorted by
Tagged with
3
votes
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
4answers
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
0answers
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
1answer
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
1answer
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
5answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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 ...

1
2 3 4 5
152