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

**3**

votes

**2**answers

321 views

### Distance between primes that are quadratic residues modulo an other prime

Question: Is there an infinite sequence of primes $\{q_i\}_{i=1}^{\infty}$ that is not too sparse ( $q_n =O(poly(n))$ for a fixed polynomial) for which it is true that for every $k$ there is an $N(k)$ ...

**4**

votes

**1**answer

106 views

### Bounds for the size of arrays with distinct subarray sums

Consider an array $A$ of length $n$ with $A_i \in \{1,\dots,s\}$ for some $s\geq 1$. For example take $s = 6$, $n = 5$ and $A = (2, 5, 6, 3, 1)$. Let us define $g(A)$ as the collection of sums of all ...

**7**

votes

**1**answer

454 views

### Given any finite relation $R$ what is the cardinality of $\langle R\rangle=\{\underbrace{R\circ R\cdots \circ R}_{n\text{ times}}:n\in\mathbb{N}\}$?

Given any finite relation $R$ if we let $\circ$ denote relation composition and define $R^n=\underbrace{R\circ R\cdots \circ R}_{n\text{ times}}$ then does there exist an explicit formula for the ...

**8**

votes

**3**answers

205 views

### Determinant of a block matrix with many $-1$'s

For an array $(n_1,...,n_k)$ of non-negative integers and non-zero reals $a_1,...,a_k$, define a block matrix $M$ of size $n=n_1+\cdots+n_k$ as follows:
The main diagonal has blocks of sizes $n_i$ and ...

**6**

votes

**1**answer

339 views

### Interesting behaviour of binomial coefficients

Let $\binom{n}{k}:=\frac{\Gamma(n+1)}{\Gamma(k+1)\Gamma(1-k+n)}$ be the generalized binomial coefficient then I noticed by playing around with Mathematica that the function $f:[0,n/2] \rightarrow \...

**2**

votes

**0**answers

57 views

### 4-tuples with close sums

Some $4$-tuples of positive real numbers $(a_1,b_1,c_1,d_1),\dots,(a_n,b_n,c_n,d_n)$ are given, with all $a_i,b_i,c_i,d_i\leq 1$. Is it always possible to partition $\{1,2,\dots,n\}$ into two subsets $...

**3**

votes

**0**answers

134 views

### A permutation group acting on subsets

Consider the the set
$$X = \prod_{1 \leq k \leq n-2} \binom{ \bf{n}}{k} $$
where $\binom{ \bf{n}}{k}$ denotes the set of subsets with $k$ elements of the set ${\bf n} = \{1, \cdots , n\}$.
For ...

**2**

votes

**0**answers

273 views

### Counting / characterizing the isolated points of a particular algebraic variety

I'm not a professional geometer / topologist, so please thanks for your patience :)
Setup
The following questions are the first in a series of steps I'm undertaking in an attempt to break down a ...

**4**

votes

**2**answers

171 views

### The maximal size of intersection of two sets

Let $S=\{1,2,\cdots,2n\}$, and $S_i \subseteq S(i=1,2,\cdots,n+1)$ be $n+1$ subsets, each of which contains half of the $2n$ elements, namely $|S_i|=n$. Consider the following expression:
$$M=\max_{1\...

**2**

votes

**1**answer

221 views

### On triangular numbers modulo primes

Let $p$ be an odd prime. For $a\in\mathbb Z$ let $\{a\}_p$ denote the least nonnegative residue of $a$ modulo $p$. The list $\{1^2\}_p,\ldots,\{((p-1)/2)^2\}_p$ is a permutation of all the quadratic ...

**7**

votes

**1**answer

287 views

### Simplicial set are to cubical sets what simplicial complexes are to …?

Simplicial sets and cubical sets (with or without connections) are defined as presheaves over some indexing categories. There is a full subcategory of simplicial sets that we can identify with the ...

**6**

votes

**0**answers

160 views

### A conjecture on the coefficient of a special term in the expansion of the graph polynomial?

Recently, I am interested in the polynomial polynomial of the product of cycles.
Let $G = (V , E)$ be an undirected multi-graph with vertex set $\{1,\cdots,n\}$. The graph polynomial of $G$
is ...

**3**

votes

**0**answers

194 views

### Matrix Inequality: Traces of $n$th powers

Let $A, B$ be matrices over $\mathbb{C}$ of the same dimensions (not necessarily square). With $'$ denoting conjugate-transpose, and tr the trace, show for $n\in\mathbb{N}$ that
$ 2\,\mathrm{Re}\, \...

**1**

vote

**1**answer

61 views

### Linear relations between volume of a polytope and its faces

Let $P$ be a polytope. Is anything known about the set of linear relations that hold between the volumes of the (not-necessarily proper) faces of $P$ as $P$ “varies slightly”? By varies slightly I ...

**0**

votes

**0**answers

28 views

### find the smallest number of lists that contain the largest amount of different numbers

I have a list of lists, in each list, there are numbers from 1-100
for example
[[1,2,3],[3,4,2],[23,2,22,12],[2,1,3,4,6]...]
How can I find the smallest number ...

**1**

vote

**1**answer

68 views

### Degree sequence along an Eulerian cycle

I would like to know if there exists a result saying that for a fixed undirected rooted Eulerian graph, up to some permutation, along any Eulerian cycle, there exists a unique sequence of degrees, ...

**3**

votes

**1**answer

73 views

### Typical labelled vs. unlabelled trees properties

Consider two random tree models $T_1(n)$ and $T_2(n)$, chosen equiprobably among labelled and unlabelled trees on $n$ vertices respectively. I'm wondering if there are properties that are vastly more ...

**5**

votes

**1**answer

109 views

### Length minimizing graphs between a finite set of points

Consider a set of $n$ points in the plane. Among all the connected graphs (trees) $T$ in the plane that have these $n$ points among their vertices, I am looking to find one such that the sum of its ...

**4**

votes

**0**answers

105 views

### The set of homogeneous solutions of a clopen contains an hyperarithmetical set

In the context of Galvin-Prikry generalization of Ramsey's theorem, I read in a couple of papers ([1],[2]) that Solovay [3] proved that if $P$ is a clopen of $[\mathbb{N}]^{\mathbb{N}}$ then the set ...

**2**

votes

**0**answers

96 views

### About relation between Kostka numbers and Littlewood-Richardson coefficient

The fact that Kostka numbers equals to Littlewood-Richardson coefficients for some partitions is already known $\colon$
\begin{align}
K_{\lambda \mu} = c_{\sigma \lambda}^\tau
\end{align}
where $\...

**6**

votes

**0**answers

73 views

### Numbers where there is a unique group with integral character table

Call a number $n$ special in case there is a unique group of order n whose character table consists of only integers. This should be equivalent to the condition that the number of conjugacy classes ...

**29**

votes

**1**answer

688 views

### Number of irreducible representations of a finite group over a field of characteristic 0

Let $G$ be a finite group and $K$ a field with $\mathbb{Q} \subseteq K \subseteq \mathbb{C}$.
For $K=\mathbb{C}$ the number of irreducible representations of $KG$ is equal to the number of conjugacy ...

**12**

votes

**3**answers

490 views

### Which partitions realise group algebras of finite groups?

Fix an algebraically closed field $K$ (maybe of characteristic zero first for simplicity, like $\mathbb{C}$).
Given a partition $p=[a_1,...,a_m]$ of an integer $n$. We can identify $p$ with the ...

**3**

votes

**0**answers

32 views

### Maximal number of sets, obtained as intersections of semiintervals of $k$ linear orders

Given a finite set $S$ with $n$ elements, and a fixed small $k$ (say $k=3$), how to find $k$ linear orders $\leq_1, \dots, \leq_k$ on $S$, such that the number of feasible subsets of $S$ is ...

**7**

votes

**1**answer

93 views

### How many maximal length Bruhat paths from $u$ to $w$ can there be?

I've been doing some work with saturated Bruhat paths in a Coxeter group between two elements $u\leq w$. It seems to me that if $\ell(u) =0$, then there are at most $\ell(w)! $. I haven't tried to ...

**0**

votes

**1**answer

60 views

### Expected sum of chosen coordinates in a random subset of a Hamming hypercube

Let $S$ = $\{v_1, v_2, ..., v_n\}$ denote a random subset of a Hamming hypercube of dimension $d$, where $n = |S|$ and $n \leq 2^d$. If $v_i$ = $\langle x^i_1x^i_2... x^i_d\rangle$ for all $i \in [1,n]...

**6**

votes

**2**answers

181 views

### Nonlinear boolean functions

Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements. I wonder if there is any known algorithm/construction that, given any $n\geq 1$, returns a boolean function $f:\mathbb{F}^n_2\rightarrow \...

**3**

votes

**4**answers

467 views

### A generalization of Landau's function

For a given $n > 0$ Landau's function is defined as $$g(n) := \max\{ \operatorname{lcm}(n_1, \ldots, n_k) \mid n = n_1 + \ldots + n_k \mbox{ for some $k$}\},$$
the least common multiple of all ...

**2**

votes

**1**answer

88 views

### Why Triangle of Mahonian numbers T(n,k) forms the rank of the vector space?

I am looking for an explanation of why Triangle of Mahonian numbers T(n,k) form the rank of the vector space $H^k(GL_n/B)$?
With respect to the property of Kendall-Mann numbers where the statement ...

**9**

votes

**2**answers

208 views

### Reference Request: Length of a reflection in a Coxeter group can be achieved by symmetric word

In a given coxeter group $(W,S)$, a reflection is an element of $W$ that can be written with a symmetric word in the generators $S$.
In multiple sources, I found the following formula:
$$
\mathrm{...

**10**

votes

**2**answers

290 views

### Almost graceful tree conjecture

The graceful tree conjecture is the following statement: for any tree $T = (V, E)$ with $|V| = n$ there is a bijective map $f: V \to [n]$ such that $D = \{|f(x) - f(y)| \mid xy \in E\} = [n - 1]$.
...

**10**

votes

**2**answers

402 views

### Find the tight upper bound of $\sum_{i=1}^n \frac{i}{i+x_i}$, where the $x_i$'s are distinct in $\{1,2,…,n\}$

What is the tight upper bound of $\sum_{i=1}^n \frac{i}{i+x_i}$, where the $x_i$'s are distinct integers in $\{1,2,...,n\}$?

**6**

votes

**0**answers

203 views

### Legendre's three-square theorem and squared norm of integer matrices

Let $\mathbb{N}$ be the set of non-negative integers. Let $E_n$ be the set of integers which are the sum of $n$ squares. Let $F_n$ be the set of integers of the form $\Vert A \Vert^2$ with $A \in M_n(...

**-1**

votes

**1**answer

77 views

### Existence of a graph with strong restrictions

Given a maximal degree $k$ and maximal diameter $d$. We identify 3 nodes, $i$, $j$, and $v$. Can an undirected graph exist, such that:
all nodes but $v$ have full degree $k$ ($v$ having a lower ...

**4**

votes

**0**answers

115 views

### Tiling squares with oblongs

An oblong is a rectangle whose width and length are consecutive integers: 1x2, 2x3, 3x4, etc. Does N exist such that it is possible to split the first N oblongs into 2 or more non-intersecting sets so ...

**6**

votes

**0**answers

100 views

### Collecting proofs of the birth of the giant component

I want to collect different proofs of Erdös-Rényi result on the double jump of the largest connected component on $G(n,p)$ (or in $G(n,M)$.
I know the original proof of Erdös-Rényi, the proof that ...

**3**

votes

**1**answer

148 views

### Greedy simplices in an ultrametric space (generalized Bhargava $p$-orderings)

Let $\left(U, d\right)$ be a finite ultrametric space -- that is, $U$ is a finite set, and $d : U \times U \to \mathbb{R}_{\geq 0}$ is a metric on $U$ such that every $x, y, z \in U$ satisfy $d\left(x,...

**7**

votes

**1**answer

146 views

### Representability of matroids over finite fields

I have several questions regarding representability of matroids.
Question 1. Does there exist a finite matroid that is representable over an infinite field, but is not representable over any finite ...

**6**

votes

**1**answer

226 views

### Subsets of a group with special property

Let $G$ be a finite group. We say a subset $A$ of $G$, $|A|=m$, is $(m,i)$-good, $m\geq 1$ and $0\leq i\leq m$, if there exist $g_A\in G$ such that we have $|gA\cap A|=m-i$.
I need some groups such ...

**2**

votes

**0**answers

109 views

### Tuples with same coordinate sum

Some $4$-tuples of positive real numbers $(a_1,b_1,c_1,d_1),\dots,(a_n,b_n,c_n,d_n)$ are given, with $$\sum_{i=1}^na_i=\sum_{i=1}^nb_i=\sum_{i=1}^nc_i=\sum_{i=1}^nd_i=3.$$ It is known that there ...

**8**

votes

**0**answers

174 views

### Does anyone know of this manifestation of the Littlewood-Richardson coefficients for the complete flag variety?

This is the culmination of about 11 years of research but after I discovered it I found a proof that was extremely trivial, so I'm wondering if it's already known.
Let $(a,b)$ with $a < b$ ...

**5**

votes

**1**answer

297 views

### Random pairs of commuting permutations

Let $\Omega_n \subseteq \mathrm{Sym}(n)^4$ be the set of all $4$-tuples $(\sigma_1,\sigma_2,\tau_1,\tau_2)$ of permutations of $\{1,\ldots,n\}$ such that $\sigma_j \tau_k = \tau_k \sigma_j$ for each ...

**1**

vote

**0**answers

34 views

### Possible volumes of lattice polytopes

All polytopes here are assumed to be convex lattice polytopes.
Given a polytope $P$, set $$v(P):= (\operatorname{vol}(F))_{F\text{ a face of }P},$$ where the volume of a $d$-dimensional polytope $P\...

**4**

votes

**1**answer

255 views

### A Conjecture about the integral related to Chebyshev polynomial

I am interested in the following integral related to the Chebyshev polynomials
$$I_{n,m}:= \int_0^\pi \left(\frac {\sin nx}{\sin x}\right)^{m} dx,$$
where $n,m\in \mathbb{Z}^+.$
It is easy to see ...

**4**

votes

**1**answer

120 views

### Is it possible to find the minimum or maximum value of $n$ average values must be an integer

Let $M$ be a positive integer greater than $1$. All integers from $1$ to $M$ were written on a board.
Each time we erase a positive integer on the board in a way that the average value of all ...

**-1**

votes

**1**answer

90 views

### Subgroup of the semidirect product of two subgroups with coprime orders [closed]

It is well known that if $\gcd (|H|,|K|)=1$ then all subgroups
of $H\times K$ are of the form $H^{\prime }\times K^{\prime }$ such that $H^{\prime}$ is a subgroup of $H$ and $K^{\prime}$ is a subgroup ...

**3**

votes

**0**answers

62 views

### Maximum spanning paths in a graph

Is there any research on the question of finding a spanning subgraph in the form of a collection of independent paths with a maximum number of edges? If the paths are simply edges we have the maximum ...

**7**

votes

**1**answer

173 views

### Counting spanning trees of a planar graph

I know through Kirchoff's Theorem, one can calculate the number of spanning trees via the determinant of a Laplacian. This has complexity $O(N^{2.373}$). I was wondering if anyone was aware of a ...

**3**

votes

**0**answers

51 views

### How likely is a matrix with exactly $n$ number $1$s per row to avoid a large wide empty submatrix?

Consider the finite collection $M(N,n)$ of all $N \times N$ matrices with exactly $n$ entries per row equal to $1$ and all other entries equal to zero $0$.
By an $a \times b$ submatrix of $M$ we ...

**11**

votes

**2**answers

367 views

### Extension of Dickson's theorem on integers of the form $a^2+b^2+2c^2$

Theorems V in this paper of L.E. Dickson states that the following two sets are equal. $$E=\{a^2+b^2+2c^2 \ | \ a,b,c \in \mathbb{Z}\} \ \text{ and } \ F=\mathbb{N} \setminus \{4^k(16n+14) \ | \ k,n \...