Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
2answers
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
1answer
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
1answer
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
3answers
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
3answers
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
0answers
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
1answer
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
1answer
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
2answers
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
4answers
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
1answer
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
2answers
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
2answers
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
2answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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 \...