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
0
votes
0answers
8 views

Bound on the number of unlabeled tree on n vertices

By the Cayley's Theorem, the number of labeled tree on n vertices is at most n^{n-2}. On the other hand, what is the bound on the number of unlabeled tree on n vertices?
0
votes
0answers
49 views

About a generalization of complete graphs

Does anyone know what are called (if there is any nomenclature for this class of graphs in the literature) the connected graphs such that each of their edge belongs to some triangle? For example, ...
0
votes
0answers
15 views

Additive graph/digraph invariants $f$ and $g$ such that if $f(G)=\min(g(D):D\text{ is an orientation of }G)$ then $f(G)=\min(f(G/uv),f(G+uv))$

If we let $\rho(D)$ be the number of arcs in any digraph $D$ minus the number of arcs in any minimum equivalent subdigraph of $D$, then for every $2$-edge connected graph $G$, is it true for all $u,v\...
1
vote
0answers
47 views

Does there exist a subset $E \in \mathbb{Z}_{p^2}^4$ such that $\Pi(E) \neq \mathbb{Z}_p$?

Denote $\mathbb{Z}_{p^2}$ be the ring residues modulo $p^2,$ i.e $$ \mathbb{Z}_{p^2} = \left\{ 0,1,2,\dots, p^2-1\right\}.$$ $$\mathbb{Z}_{p^2}^{d} = \underbrace{\mathbb{Z}_{p^2} \times \dots \times ...
3
votes
0answers
65 views

Counting self avoiding walks in a strip

Consider the strip $\{0,1,\ldots n\}\times\{0,1,2\}$ in $\mathbb{N}^2.$ Is a formula known for the total number of self avoiding walks in this strip starting at $(0,0)$ in terms of the parameter $n$? ...
1
vote
1answer
70 views

Find the largest subset of all binary arrays of length $n$ with $r$ ones which have pairwise distance greater than $m$

Let $\Omega = \left\lbrace x : |x| = r \, \text{for} \, x \in \mathbb{Z}_2^n \right\rbrace$ for $r \in \mathbb{N}$. We want to find the the biggest subset of $\Omega$, $\Gamma = \left\lbrace x \in \...
3
votes
0answers
49 views

Condition for non-existence of trivial matrix decomposition

Let $A_1,\dots,A_n$ be matrices, with no row or column of $0s$, and such that for every $i=1,\dots,n$ there does not exist a decomposition of $A_i$ of the form $$ A_i = \oplus_{j=1}^n B_j \qquad (\...
3
votes
1answer
108 views

Reference for Dedekind's problem

Dedekind's problem is about enumerating antichains in the Boolean lattice. Is there an explicit reference where Dedekind stated this problem? Is there a good motivation to study this problem except ...
2
votes
0answers
114 views

Sum of products of irreducible characters of the symmetric group over a subgroup

When trying to build a dual formulation for lattice gauge theories using Weingarten integration I am getting sums of the kind $$I^{m, n}_{\mu, \nu} (\sigma, \tau) = \sum_{\pi \in S_n} \chi_\mu (\pi \...
0
votes
0answers
21 views

hypergraph product that preserve expansion properties

I am looking for a hypergraphs product of hypergraph H1,H2 that preserves some expansion properties of H1,H2. The expansion property I am looking at is HD-random walk. The product I am looking for is ...
5
votes
4answers
314 views

Request for an exact formula related to a partition in number theory

The Frobenius equation is the Diophantine equation $$ a_1 x_1+\dots+a_n x_n=b,$$ where the $a_j$ are positive integers, $b$ is an integer, and a solution $$(x_1, \dots, x_n)$$ must consist of non-...
4
votes
0answers
86 views

program to compute hurwitz numbers

Is there a computer program available to compute Hurwitz numbers easily? In fact I only care about counting covers $C\to\mathbb{P}^1$ branched over $0,1,\infty$, and am even willing to restrict to the ...
1
vote
1answer
35 views

Vertex connectivity of join of two graphs

Does there exist any results on the vertex connectivity of join of two graphs? If $G_1$ and $G_2$ are two graphs what can we say about the vertex connectivity of $G_1\lor G_2$ where $G_1\lor G_2$ is ...
2
votes
0answers
60 views

On the proportion of simplicial $d$-polytopes on $n$-vertices

I have a question regarding estimates for the proportion of simplicial $d$-polytopes on $n$-vertices. Let $c_s(n,d)$ denote the number of combinatorial types of simplicial $d$-polytopes on $n$ ...
1
vote
0answers
130 views

Questions about a certain sequence of naturals generated by primorials

I'm working on the following sequence of naturals (which is NOT listed in OEIS) $$3,5,11,17,23,29,59,89,119,149,179,209,419,629,839,1049,1259,1469,1679,...$$ whose elements are generated this way $$3=(...
1
vote
2answers
191 views

Constructing a vector consisting of nonnegative entries

Consider constructing a vector $v=(a_1,a_2,\ldots,a_n)$ consisting of nonnegative integers such that $a_1=1$ and, if $a_j$'s are nonzero, then $a_j\equiv a_{n-j+2}+j-1 \pmod m\ \forall 1<j\le\frac{...
1
vote
0answers
30 views

Lower bound for the chromatic number in terms of minimum feedback vertex set

Let $MFVS(G)$ denote the size of minimum feedback vertex set of $G$. We believe we proved $\chi(G) \ge (|G| - MFVS(\overline{G}))/2$ and this bound is sharp. Is this known or trivial result? This ...
1
vote
0answers
42 views

Yet another graph characteristic

I wonder if the following graph-theoretical concepts have been considered before, and if so, under which name. Consider a directed graph $G$ with $n$ nodes. Let the cycle number $\gamma(\nu)$ be ...
5
votes
1answer
94 views

Parity of shuffle permutations

A $(p,q)$-shuffle is a permutation $\sigma$ of the set $\{1, \dots, p, p+1, \dots,p+q\}$ such that $$\sigma(1)<\dots<\sigma(p)$$ and $$\sigma(p+1) < \dots<\sigma(p+q)\,.$$ It is known ...
6
votes
0answers
177 views
+150

An extension of Erdos' distinct distances problem based on circles of various radii

Consider a collection $C_1,C_2, \dots, C_n$ of circles in the plane and suppose that the center of $C_i$ is $o_i$ and the radius of $C_i$ is $r_i$. We will define the relative distance between the ...
0
votes
0answers
25 views

pseudo-Hadamard matrix

What can one say about the matrices M with the following properties: 1) the rows and the columns are indexed by the elements of a finite field with an even number q of elements; 2) All the matrix ...
0
votes
1answer
85 views

Question of expected number of consecutive coin flip with increasing bias [closed]

This is a question I found on the book and I don't know how to tackle it. Thanks to any help or hint in advance. I have a coin that, I could get the head 100% at the first flip, $\frac{1}{3}$ at the ...
3
votes
0answers
130 views

A fusion ring identity

Fusion rings I'll more or less stick to the presentation given in this question: [1] We define a fusion ring as follows: consider a free $\mathbb{Z}$-module $\mathbb{Z}\mathcal{B}$ with finite basis ...
12
votes
1answer
313 views

Yet another real-rooted polynomial

In this entry I asked for the real-rootedness of a polynomial, and two very interesting answers were given: one using Malo's theorem and the other a clever rewriting of the expression using Jacobi ...
0
votes
0answers
41 views

A ballot-casting problem

For any set $X$ and cardinal $\kappa$ let $[X]^\kappa$ denote the collection of subsets of $X$ with cardinality $\kappa$. If $n$ is a positive integer, let $[n]:=\{1,\ldots,n\}$. Let $V$ and $K$ be ...
2
votes
0answers
91 views

Solving general two-dimensional recurrence relation

Any techniques for deriving a closed form solution for the following recurrence relation? Or bounds on asymptotic behavior for large $n$? $$a_{n+1,k} = \sum_{0 \le i \le n} \frac{n!}{i!} a_{i,k-1}$$ ...
5
votes
1answer
211 views

RSK correspondence

Up to now, what are the difference ways we know to define RSK correspondence? I already know: By insertion and recording tableau. Ball construction or Viennot's geometric construction. Growth diagram ...
1
vote
0answers
44 views

Partitionability and colorability of hypergraphs

Motivation. If $\kappa\neq\emptyset$ is a cardinal, then a simple, undirected graph $G=(V,E)$ is $\kappa$-colorable if and only if there is a partition of $V$ into at most $\kappa$ blocks such that ...
4
votes
2answers
282 views

Are $n \times n$ special orthogonal matrices, all the entries of which have the same absolute value, possible for $n \neq 4$?

As I noted in my preceding question https://math.stackexchange.com/questions/3510189/give-a-general-class-to-which-a-specific-4-times-4-special-orthogonal-matrix in equation (62) of their recent ...
0
votes
0answers
110 views

Reference for discrete Laplacian on $\mathbb{Z}$

For $x\in \mathbb{R}^\mathbb{Z}$, let the discrete Laplacian be defined as \begin{align*} (\Delta x)_k = 2x_k-x_{k+1}-x_{k-1}. \end{align*} I am looking for good references about its spectrum (or ...
0
votes
1answer
53 views

Matching book embedding of Cartesian products of graphs

In the book embedding of a graph $G$ , each vertex of $G$ is placed on the spine and each edge is placed in the pages without crossing each other edge. If vertices have degree at most one in each ...
17
votes
3answers
722 views

Cyclic action on Kreweras walks

A Kreweras walk of length $3n$ is a word consisting of $n$ $A$'s, $n$ $B$'s, and $n$ $C$'s such that in any prefix there are at least as many $A$'s as $B$'s, and at least as many $A$'s as $C$'s. For ...
7
votes
1answer
129 views

3 term van der Waerden with large step size

Let $P(n)$ be the statement "any $n$ coloring of $\mathbb{N}$ contains a monochromatic progression $a, a+d, a+2d$ such that $d>a$". For which $n$ is $P(n)$ true? It's easy to see that $P(2)$ is ...
5
votes
1answer
120 views

Using irreducible characters of the orthogonal group as basis for homogeneous symmetric polynomials

The irreducible characters of the orthogonal group $O(2N)$ are given by $$ o_\lambda(x_1,x_1^{-1},...x_N,x_N^{-1})=\frac{\det(x_j^{N+\lambda_i-i}+x_j^{-(N+\lambda_i-i)})}{\det(x_j^{N-i}+x_j^{-(N-i)})}...
2
votes
1answer
84 views

construct a bijective map between subsets of binary sequence

Consider the binary sequence $\{0,1\}^N$ where $N$ is an even integer (for simplicity). Let $M_k := \{\beta\in \{0,1\}^N \rvert \sum_{j=1}^N \beta_j = k\}$ (i.e., $M_k$ is the set that contains all ...
7
votes
2answers
189 views

Does minimal degree $n$ imply a $K_n$ minor

Is it true that any finite graph has a $K_n$ minor, where $n$ is a minimal vertex degree?
5
votes
0answers
58 views

Partitioning the set of Pauli words into abelian pieces

Let $\sigma_x,\sigma_y,\sigma_z$ be the Pauli matrices. A Pauli word of length $n$ is defined as the tensor product $\otimes_{i=1}^n\sigma_i$ of operators $\sigma_1,\dots,\sigma_n\in\{\mathbf 1,\...
18
votes
2answers
1k views

Real rootedness of a polynomial

Let's consider $m$ and $n$ arbitrary positive integers, with $m\leq n$, and the polynomial given by: $$ P_{m,n}(t) := \sum_{j=0}^m \binom{m}{j}\binom{n}{j} t^j$$ I've found with Sage that for every $...
3
votes
0answers
57 views

Relations between double coinvariants and affine Springer fibers

Diagonal coinvariants have an interpretation from https://arxiv.org/abs/math/0201148 in terms of the Hilbert scheme. There are two recent papers https://arxiv.org/pdf/1801.09033.pdf and https://arxiv....
0
votes
0answers
22 views

Tutte 1-factor theorem to prove total chromatic number of complete multipartite graphs

Consider a complete multipartite graph on $n$ vertices having maximum degree $\Delta$. Then, it is known that the total chromatic number of the graph is $\le\Delta+2$. The proof uses the fact that a ...
3
votes
1answer
71 views

Bounding number of k-cycles in a graph

Fix any $k \geq 3$, and suppose I have a simple undirected graph $G=(V,E)$. I want a bound on the number of $k$ cycles in $G$ as a function of $|E|$. In particular, I would like to prove the following ...
8
votes
3answers
418 views

Looking for a “cute” justification for a Catalan-type generating function

The Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$ have the generating function $$c(x)=\frac{1-\sqrt{1-4x}}{2x}.$$ Let $a\in\mathbb{R}^+$. It seems that the following holds true $$\frac{c(x)^a}{\sqrt{1-...
1
vote
0answers
80 views

Relation between the number of spanning trees and the chromatic number of a graph

The number of spanning trees $\tau(G)$ of a simple graph $G$ is seen to satisfy the deletion-contraction recurrence: $$\tau(G)=\tau(G-e)+\tau(G.e),$$ where $e$ is an edge of the graph $G$ and $G-e$ ...
4
votes
1answer
210 views

Does the lattice of partitions map onto the lattice of subsets?

Let $X\neq \emptyset$ be a set and let $X^X$ denote the collection of all functions $f:X\to X$. We put a binary relation (reflexive and transitive), the composition preorder on $X^X$ by setting for $f,...
16
votes
3answers
574 views

Plane partitions with equal margins

A plane partition of $n$ is an table of integers $A=(a_{ij})$ which add up to $n$ and non-increase in rows and columns. For example, $$A= \begin{matrix} 331 \\ 32 \ \ \\ 11 \ \ \end{matrix} $$ is a ...
2
votes
1answer
72 views

Nash equilibria for “presidential election” game

Suppose, in a country there are $m$ different social issues, positions on which are being indexed with numbers $[-1; 1]$, with radicals on the opposing ends and moderates in the center. In this ...
4
votes
0answers
56 views

Frobenius dimensions of Nakayama algebras

The Frobenius dimension $F(A)$ of an Artin algebra $A$ is given by the dimension of $Hom(D(A),A)$ (see the answer in On nearly Frobenius algebras ). Question 1: Is it true that $F(A) \geq gldim(A)$ ...
5
votes
3answers
568 views

Update on “Hopf algebras: their status and pervasiveness” by Hazewinkel

Hazewinkel wrote this article in 2005. Perhaps it's time for an update. For example, updating item 34: Ordinary differential equations much work has been done on the underlying Hopf algebra (HA) of ...
16
votes
4answers
967 views

Can I build infinitely many polytopes from only finitely many prescribed facets?

Given a finite set of convex $d$-dimensional polytopes $\mathcal P$, for some $d\ge 2$. Question: Is it true that there are only finitely many different convex $(d+1)$-dimensional polytopes whose ...
2
votes
1answer
129 views

How to show that $x_{k+1}+x_{k+2} + \cdots + x_n < 2m$?

Let $k \le n$ be positive integers and let $m$ be a positive integer. Assume that $x_1, \ldots, x_n$ are non-negative integers and \begin{align} & x_1^2 + x_2^2 + \cdots + x_n^2 - (k-2) m^2=2, \\ &...

1 2 3 4 5 145