# 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,207
questions

**0**

votes

**0**answers

53 views

### Differences of elements of a set of natural numbers (reference request)

Let $A$ be a subset of $[n] = \{1,2,\dots,n\}$.
Define $\overline A = \{(i,j) : i, j \in A \text{ and } i > j \}$ and define $(i_1,j_1) \sim (i_2,j_2) $ if $i_1 - j_1 = i_2 - j_2$.
This is ...

**5**

votes

**0**answers

118 views

### A “polar dual” for projective varieties?

Given a projective variety $X$ (over $\mathbb{C}$, say) with an affine paving $X=\sqcup_i C_i$, one can construct a poset $P_X$ on the set of cells $\{C_i\}$ by saying $C_i \leq C_j$ whenever $C_i \...

**15**

votes

**1**answer

263 views

### Geometric interpretation of the exceptional isomorphism $PSp(4,3)=PSU(4,2^2)$

It is well-known that there is an isomorphism between $PSp(4,3)$ (the symplectic group of dimension $4$ over $\mathbb F_3$) and $PSU(4,2^2)$ (the unitary group defined by $4\times4$ unitary matrices ...

**0**

votes

**1**answer

78 views

### Bound for Large deviations of sums of independent (not identical) variables

I am working with a sum of variables $X_i$; they are all independent, but not identically distributed. For any $i$, I can show the bound $$\Lambda^*_{X_i}(t) := \sup_t \langle t, x \rangle - \Lambda_X(...

**-1**

votes

**1**answer

73 views

### Tuza theorem to prove vizing theorem

The Tuza theorem states that every graph with no cycle congruent to 1 mod $k$ is $k$ colorable. Now, the line graph of any simple graph of maximum degree $d$ is seen to posess the property that it has ...

**8**

votes

**2**answers

232 views

### Two rows of bounded numbers

Given is an integer $n\ge 2$ and two rows of $n$ positive real numbers each, with each number not more than $n-0.5$, such that the numbers in each row sum to $n$. Is it always possible to choose some ...

**6**

votes

**2**answers

239 views

### Multivariate Lagrange inversion with zero powers

(Also asked on MSE)
The multivariate Lagrange inversion formula, which I found in a couple of papers (such as this and this), is as follows. If $f_i=t_ig_i(f)$, $1\le i\le k$, then
$$ [t^n]h(f(t))=\...

**2**

votes

**0**answers

61 views

### Representing graphs as induced subgraphs of $\text{Hom}(H,K)$

Let $H, K$ be simple, undirected graphs, and let $\text{Hom}(H,K)$ the collection of graph homomorphisms $f: H\to K$. (Note that $\text{Hom}(H,K)$ might be empty.) For $f,g\in \text{Hom}(H,K)$ we say ...

**5**

votes

**0**answers

95 views

### Cut norm versus $l_1$ norm

Let $K$ be the set of $n\times n$ matrices with zero diagonal entries and such that the sum of all entries is zero.
The cut norm of a $n\times n$ matrix $M$ is:
$$
cut(M) = \sup_{S, T, S\cap T = \...

**0**

votes

**2**answers

104 views

### Majority-driven manipulations of integer vectors

Motivation. Recently I was watching two people play a game that involved arranging sticks in a number of heaps and moving them around in certain allowed ways that I think I was able to infer from ...

**7**

votes

**3**answers

338 views

### Polygonal paths and polygons with prescribed set of vertices

Let $A$ be a finite set of points in the plane. How can we determine if there is a simple open polygonal path (i.e. without intersections), whose vertices are exactly $A$, with no straight angles ...

**1**

vote

**1**answer

95 views

### Distribution of non-overlapping words in randomly generated text

The question can be described in the following way:
Suppose I have a finite language $\mathcal{L}$ over alphabet $\Sigma$.
I have a string that is composed of a concatenated series of $n$ instances ...

**0**

votes

**1**answer

114 views

### Size of parities in counting partitions into odd parts

Let $p_{odd}(n)$ be the number of partitions of $n$ into odd parts (see here). For instance, one has the generating function
$$\prod_{k\geq1}\frac1{1-q^{2k-1}}.$$
QUESTION. What is the size of this ...

**2**

votes

**0**answers

86 views

### Lorentzian (=Minkowskian) Hadwiger-Nelson problem: is the chromatic number finite?

Background: Some years ago, I collected a number of thoughts and partial results (which, based on Soifer's Mathematical coloring book, I believed were new) on the Hadwiger-Nelson problem in a note ...

**4**

votes

**1**answer

81 views

### Complexity of graph 3 coloring and counting algorithm

3-coloring a graph $G$ is equivalent to partitioning the
vertices of $G$ in three independent sets.
The smallest independent set $A$ is at most $n/3$ where $n$
is the order of $G$.
We have $G \...

**11**

votes

**1**answer

324 views

### $q$-analogs of total positivity

A real matrix $M$ is called totally positive if all of its minors are positive; these matrices have been extensively studied, and there are generalizations to other Lie types, for example by Lusztig.
...

**0**

votes

**1**answer

78 views

### Terminology and approximation to logarithm of a sum of products of binomial coefficients

Denote $$T(m)=\sum_{1\leq n_m\leq n_{m-1}\leq\dots\leq n_2\leq n_1\leq m}\prod_{i=1}^{m}\binom{n_i}{n_{i+1}}.$$
Is there a name for this kind of summation and is there a good estimate for $\ln T(m)$ ...

**0**

votes

**2**answers

182 views

### Interpolating asymptotic expression for logarithm of middle binomial sums

Define $S(k,2n)=\sum_{i=-k}^k\binom{2n}{n+i}$ at every $k\in\{0,\dots,n\}$.
We know $$\ln(S(\gamma\mbox{ } n^\gamma,2n))\asymp(2n\ln2-\frac12\ln\pi-\frac12\ln n)$$ at $\gamma\rightarrow0$ and $$\ln(S(...

**1**

vote

**0**answers

69 views

### Relation between Betti Numbers and Chromatic Number of a simple graph

Is there a relation between the betti numbers of a graph considered as a simplicial complex and its chromatic number?
Typically the first Betti number is said to be the cyclomatic number of the graph....

**0**

votes

**0**answers

179 views

### A gap problem in elementary additive combinatorics

Given $a,b\in\mathbb N$ define the set $$\chi(a,b)=\{M\in\{0,1\}^{n^a\times n^b}:\mbox{ every row of }M\mbox{ is distinct}\}.$$
Also given ${\bf{x}}=(x_1,\dots,x_{n^b})\in\mathbb Z^{n^b}$ define the ...

**7**

votes

**2**answers

248 views

### Rank matrices for type $D$ Bruhat order

Roughly, this question asks how the Bruhat (strong) order in type $D$ can be understood like the Bruhat orders in types A and B=C. I'll review how types A and B work before asking my question. As a ...

**3**

votes

**0**answers

103 views

### Number of adjoint orbits containing a $(0,1)$-matrix

Motivated by this
question, what can be said about the number $f(n)$ of adjoint
orbits of $\mathrm{Mat}(n,\mathbb{C})$ (the ring of all $n\times n$
complex matrices) that contain a $(0,1)$-matrix? ...

**7**

votes

**0**answers

197 views

### Possible oversight in paper of Greene and Kleitman on chains in dominance order on partitions?

This question is about a possible lacuna in a paper of Greene and Kleitman which Zarathustra Brady made me aware of.
The paper in question is "Longest Chains in the Lattice of Integer Partitions ...

**7**

votes

**2**answers

231 views

### What makes skew characters of the symmetric group special?

For integer partitions $\mu\subset\lambda$ we can define the skew character $\chi^{\lambda/\mu}$ (for example?) via the Littlewood-Richardson rule.
Many combinatorial gadgets and algorithms extend in ...

**1**

vote

**1**answer

51 views

### Regions of hyperplane arrangements and their faces

Consider a finite hyperplane arrangement $\mathcal{A}$ over $\mathbb{R}^n$. Let the regions given by $\mathcal{A}$ be $\mathcal{R}(\mathcal{A})=\{A_1,\dots A_m\}$ for some $m$.
For any index set $I\...

**5**

votes

**1**answer

155 views

### Non-nesting matchings and Catalan numbers

It is well-known that the number of non-nesting perfect matchings on $2n$ points is given by the Catalan number $C_n$; see part (a) of the figure below. This is item e^5 in Stanley's list (http://www-...

**0**

votes

**1**answer

80 views

### Number of positive integer solutions with a lower bound

If $0\leq\gamma<\alpha<1$ and $t=\lceil n^\gamma\rceil$ hold then how many positive solutions to the linear diophantine equation
$$x_1+\dots+x_t=\lceil n^\alpha\rceil$$
have the property
$$n^\...

**4**

votes

**0**answers

116 views

### Overview of Combinatorial Technique of “Selberg’s Symmetry Formula”

In the paper entitled "A Computational History of Prime Numbers and Riemann Zeros" (on page 4, click here) it is written about "Selberg’s symmetry formula" that-
Until 1950 it was widely believed (...

**1**

vote

**1**answer

48 views

### Counting multisets satisfying a fixed property

Suppose $S$ is a infinite set and $R\subset S$ is also infinite. Now, we want to find the number of multisets $(M,\nu)$, with $M\subset S, |(M,\nu)|=n$, and having an additional property that for ...

**6**

votes

**1**answer

274 views

### How large a subset of $\mathbb{F}_q^d$ can determine all determinants?

Denote by $\mathbb{F}_q$ a finite field with $q$ elements. For $\mathcal{P}$ be arbitrary subset of $\mathbb{F}_q^d.$ We define the set
$$S:= \left\{ \det([x_1,x_2,\dots,x_d]): x_1,x_2,\dots,x_d \in ...

**1**

vote

**0**answers

97 views

### Asymptotics of the Steenrod algebra / $s$-partitions?

Recall that an $s$-partition is a partition of a natural number $n$ such that each part is of the form $2^r-1$. By a fundamental theorem of Milnor, the number $p_s(n)$ of $s$-partitions of $n$ counts ...

**1**

vote

**2**answers

154 views

### Bilinear recurrence relation between even Bernoulli numbers

Throughout this question $n$ is a positive integer greater than 1.
Consider the following well-known identity by Euler,
$$\sum_{k=1}^{n-1} \binom{2n}{2k}B_{2k}B_{2n-2k}=-(2n+1)B_{2n}.$$
Rather ...

**0**

votes

**0**answers

58 views

### Singular values and the chromatic number

What relation, if any, is there between the singular values of the adjacency matrix ( or possibly incidence matrix) of a simple graph and its chromatic number. Typically, do we have Hoffmann type, or ...

**3**

votes

**1**answer

126 views

### Map on class of all finite posets coming from maximal sized antichains

Let $P$ be a finite poset. Let $\mathcal{A}$ denote the set of antichains of $P$. Equip $\mathcal{A}$ with a partial order $\preceq$ whereby $X \preceq Y$ means for all $x \in X$ there exists $y \in Y$...

**3**

votes

**0**answers

71 views

### Arzela-Ascoli-analogue statement over a given cardinality of discrete space

(I think there would be better title for my question. If there is a good idea on the title, please let me know.)
Consider the following statement:
Let $A$ be a set (with the discrete topology, if ...

**2**

votes

**2**answers

164 views

### Cartan determinants of subsets

Let $n \geq 3$ be fixed.
We associate to every subset $S \subseteq \{1,...,n-1 \}$ a number, which we call Cartan determinant of $S$ (see the end of this post for a representation theoretic background)...

**5**

votes

**2**answers

190 views

### Nontrivial expansion in sumsets

Let $A \subset \mathbb{Z}/p$, let $f$ be a function on $\mathbb{Z}/p$ and let $B:=\{f(a): a \in A\}$.
Can we conclude that $|A+B|$ is large if $f$ is a sufficiently "nice" function? For instance say ...

**1**

vote

**0**answers

86 views

### Generating graphs of groups

Suppose $G$ is a group and $S \subset G$ is its finite subset. Let’s define the generating graph of $G$ in respect to $S$ as $Gen(G, S)$ - a graph $\Gamma(V, E)$, where $V = S$ and $E = \{(a, b) \in S ...

**3**

votes

**1**answer

238 views

### “Non-associative” standard polynomials

I saw somewhere (I appreciate if anyone has any references to proof of this fact) that if $A$ is a finite dimensional associative algebra such that $\textrm{dim}(A)<n$, then $A$ satisfies the ...

**1**

vote

**0**answers

72 views

### Flag $f$-vectors of CW-complexes

Hidden away in the appendix of this nice paper by Björner and Kalai, they give a clean description of $f$-vectors that can arise from regular CW-complexes in terms of truncations of the Euler-Poincaré ...

**2**

votes

**0**answers

129 views

### Tradeoffs in translation-invariant tilings of $\mathbb{R}^3$

Suppose I tile $\mathbb{R}^3$ in a ($\mathbb{Z}^3$-)translation-invariant manner. If we insist on the tiling being regular, then we are left with only the cubic tiling. However, suppose that we ...

**3**

votes

**0**answers

82 views

### Terminology for set systems: “trace” or “projection”?

Although the following question is not in itself mathematical, it is the expertise/breadth of the research community in mathematics that I wish to appeal to, beyond the filtered/trained search results ...

**4**

votes

**2**answers

169 views

### Number of nonequivalent weight functions on a set of $n$ elements

For a finite set $S$ of $n$ elements, say a weight function is a function $f \colon S \to \mathbb{R}$. For any subset $T \subseteq S$, define $f(T) = \sum _{x \in T} f(x)$. Define two weight functions ...

**1**

vote

**0**answers

58 views

### The degree of a (combinatorial) selfmap

If $f$ is a map from a finite set to itself, is there any widely accepted definition of the "degree" of $f$?
I would like to define deg $f$ as the quantity discussed in Quantifying the ...

**2**

votes

**1**answer

28 views

### Simple balance incomplete block design, (complete graph clique decomposition)

I am trying to find methods to construct a $(n,k,1)$-BIBD with large $n$ and $k$.
Basically, I'm wondering if there's an established method to create as many sets of size $k$ from elements $\{1, ..., ...

**2**

votes

**1**answer

154 views

### How to classify solutions to the following equations?

I would like to classify the sets of integers $a_{1},...,a_{n}$ that satisfy the following two equations.
$$\sum_{k=1}^{n}a_{k}\equiv 0\mod 2$$
$$\sum_{i\neq j}a_{i}a_{j}=0$$
For example, if $n=3$, I ...

**0**

votes

**1**answer

106 views

### Closed form solution for a binomial coefficient relation?

In following, $x_{n}$ is a set of given numbers, n = 0, 1, 2, ...,
$y_{n}$ is defined by the following recursive relation of $x_{n}$:
For example:
${\displaystyle {x_{1}=x_{0}y_{1} }}.$
${\...

**7**

votes

**3**answers

274 views

### Quantifying the noninvertibility of a function

Given a function $f$ from a finite set $X$ to itself, it seems natural to consider $\kappa_f := (\sum_{x \in X} |f^{-1}(x)|^2)/|X|$ as a measure of the non-invertibility of $f$: it equals 1 if $f$ is ...

**8**

votes

**0**answers

241 views

### When does a graph have a minimally strong orientation?

Given any asymmetric relation $A\subseteq V^2$ a digraph $D=(V,A)$ is minimally strong iff $D$ is strongly connected and for every arc $a\in A$ the digraph $D−a=(V,A\setminus\{a\})$ is not strongly ...

**1**

vote

**1**answer

130 views

### Finding Littlewood-Richardson coefficients without using identities

The Littlewood-Richardson coefficients $C^{R}_{QP}$ for some partitions $R, Q, P$ can usually be dealt with using identities like for example $$C^{R}_{QP} = 0 \quad \text{ if } \quad|R| \neq |Q| + |P|...