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,030
questions with no upvoted or accepted answers
2
votes
0
answers
37
views
Maximum number of 1-factors in a color class
Consider any graph with $n$ vertices and maximum degree $\Delta$. By Vizing's theorem, the graph could be edge colored(properly) with at most $\Delta+1$ colors.
My question pertains as to what the ...
- 2,027
2
votes
0
answers
56
views
Bounds for $\sum_{t=1}^Tn_t(s_t)^{-\alpha}\mu(s_t)$ where $n_t(s) = \sum_{1 \le t' \le t} 1_{\{s_{t'}=s\}}$ for $s \in [k]$ and $\mu \in \Delta_k$
Disclaimer: I'm not certain this is the right venue for this post, but I'll give it a try...
So trying prove some bounds in my ongoing work in theoretical reinforcement learning, I encountered the ...
- 6,726
2
votes
0
answers
252
views
Understanding the geometry of $H_{n}=\{\vec{x} \in [-N,N]^n:\sum_{i=1}^n x_i = 0\}$
I am not an expert in convex geometry but if we define $a_i \sim \mathcal{U}([-N,N])$ where $[-N,N] \subset \mathbb{R}$ and $S_n = \sum_{i=1}^n a_i$ I suspect that for arbitrary $N \in [1, \infty) $:
...
- 3,827
2
votes
0
answers
83
views
Distributive generators of a lattice
Given a finite lattice $L$, suppose $L$ is generated by a set $X$ such that the distributive law holds for all $a,b,c\in X$ i.e. $a\lor (b \wedge c) = (a\lor b)\wedge (a \lor c)$.
Is $L$ ...
- 21
2
votes
0
answers
100
views
Is there an example of two graphs with the same Dichromatic Symmetric Function?
There are examples of two graphs with the same Symmetric Chromatic Function. I was wondering if there was an example that held for the Dichromatic Symmetric Chromatic Function.
EDIT :
To define the ...
- 121
2
votes
0
answers
105
views
Difference set and structure of group
Let $G$ be a finite group and $D \subset G$ be a Hadamard difference set in $G$. If $D^{-1}=\{d^{-1}| d \in D\}$ is also a difference set in $G$ which is equivalent to $D$, then what can we say about ...
- 301
2
votes
0
answers
185
views
Infinite products from the fake Laver tables-Now with no set theory
We say that a sequence of algebras $(\{1,\dots,2^{n}\},*_{n})_{n\in\omega}$ is an inverse system of fake Laver tables if for $x\in\{1,\dots,2^{n}\}$, we have
$2^{n}*_{n}x=x$,
$x*_{n}1=x+1\mod 2^{n}$,...
- 27.8k
2
votes
0
answers
116
views
On covers of groups by cosets
Suppose that ${\cal A}=\{a_sG_s\}_{s=1}^k$ is a cover of a group $G$ by (finitely many) left cosets with $a_tG_t$ irredundant (where $1\le t\le k$). Then the index $[G:G_t]$ is known to be finite. In ...
- 14.5k
2
votes
0
answers
145
views
Proving that $\lambda\mapsto \chi^\lambda(C)/f^\lambda$ is a polynomial
Let $\lambda$ be a partition of $n$ and $\chi^\lambda$ be the character of $S_n$ associated to it. Given any conjugacy class $C$, I want to prove that
$$\lambda\mapsto \frac{\chi^\lambda(C)}{f^\lambda}...
- 995
2
votes
0
answers
169
views
A binomial coefficient identity
i'm unable to prove the following : $\forall n$ integer $\geq 3$,
$ \displaystyle \displaystyle \sum_{s=1}^n \sum_{j=n-s+1}^n \displaystyle \frac{ (\binom n j )^2 \binom {n+j} n }{s-n+j} ( \...
- 417
2
votes
0
answers
85
views
Schur function on unit circles
Define $T^d$ as following
$$ T^d = \left\{(t_1,\cdots,t_d)\in\mathbb{C}^{d}\mid |t_i|= 1 \mbox{ for all } i\right\}
$$
For any partition $\lambda\vdash n$,The Schur function is defined
$$
\...
- 1,493
2
votes
0
answers
98
views
Inverse theorems for Gowers norms for unbounded functions
The inverse theorem for Gowers norm over finite fields says that if a bounded function $f: V \to C$ where $V$ is a vector space over the finite field $\mathbb{F}$, has large Gowers uniformity norm $\|...
- 21
2
votes
0
answers
30
views
Graph vertex label dynamics, statistical model reference request
I am modeling some type of social interaction, and came up with the following natural question.
Let $K_n$ be the complete graph on $n$ vertices, with some initial edge labeling in some alphabet $A$.
...
- 15.6k
2
votes
0
answers
76
views
Confirming existence in polynomial time while solution finding is NP-complete
Assume P≠NP.
Say there's an NP-complete decision problem:
Does $P$ have a $Q$ ?
And we have a proposition $F$ computable in polynomial time, where $F(P)$ implies the existence of a solution in ...
- 9,421
2
votes
0
answers
91
views
Does the period of the first row in the odd size bad Laver tables grow without bound?
Does the length of the period of the first row in the odd bad laver tables grow without bound?
If $n$ is a natural number, then the $n$-th bad Laver table is the algebra $B_{n}=(\{1,...,n\},*)$ where
...
- 27.8k
2
votes
0
answers
172
views
On an exercise in The Probabilistic Method : random dilate of a set in a finite field
This is related to Problem $4.6$ in ``The Probabilistic Method'' by Alon and Spencer, where one essentially has to prove the following:
Let $p$ be a prime, and $A$ be any subset of $\mathbb{F}_p$. ...
- 21
2
votes
0
answers
86
views
Existence of a "generic enough" lattice point interior to a lattice triangle
Let $T$ be a lattice triangle in $\Bbb R^2$ (i.e. the convex hull of three noncolinear points in $\Bbb Z^2$), and assume it has at least one interior lattice point. Is it always possible to find a ...
- 3,029
2
votes
0
answers
156
views
Bivariate power series as rational function
Suppose we have a bivariate power series of the form
$$\sum_{i}\sum_j a_{i,j} t^i s^j,$$
where for every fixed value of $i$ the corresponding univariate power series in $s$ is a rational function. Are ...
- 21
2
votes
0
answers
125
views
Maximal number of $S_n$-conjugates living in a hyperplane
Let $v=(a_1,\dots,a_n)\in\mathbb{R}^n$ where the $a_i$ are distinct and positive. For $\sigma\in S_n$, let $\sigma(v)=(a_{\sigma(1)},\dots,a_{\sigma(n)})$. For any hyperplane $H$ through the origin, ...
- 21
2
votes
0
answers
213
views
Generating Subsets of a Multiset in Ascending Order of the Sums of the Elements of the Subset
I am trying to come up with an algorithm where you can generate combination from a set in a order such that their sums are in increasing order. This set has to be a multiset i.e. repetition allowed.
...
- 21
2
votes
0
answers
244
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 $\...
- 31
2
votes
0
answers
131
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 ...
- 1,199
2
votes
0
answers
299
views
Proof of Hales-Jewett Theorem
I was studying the paper 'Set-polynomials and polynomial extension of the Hales-Jewett Theorem' by Bergelson & Leibman, and I'm having problem with the proof of 'Proposition L', which is (for the ...
- 73
2
votes
0
answers
48
views
2-dimensional smooth lattice polytopes with minimal edge lengths
For each integer $k \geq 3$, does there exist a full-dimensional, $2$-dimensional, smooth lattice polytope $P$ with $k$ edges, such that each edge contains only two lattice points (i.e. only its ...
- 197
2
votes
0
answers
209
views
Combinatorial and computational problem related to Weyl groups and the coroot lattice
Let $W$ be a Weyl group with root system $R$ and with set of positive roots $R^+$. Let $\tilde{R}^+$ be the set of $B$-cosmall roots, i.e. positive roots $\alpha$ which satisfy $\ell(s_\alpha)=2\...
- 1,064
2
votes
0
answers
80
views
Largest number of sets $k$ among given $m$ sets that give union size lower than a given bound
Given $m$ sets $S_1, S_2, \dots, S_m$ and a bound $b$, find as many sets as possible among $m$ sets, says $S_{i_i}, S_{i_2}, \dots, S_{i_k}$ such that
$$\big| S_{i_i} \cup S_{i_2} \cup \cdots \cup S_{...
- 121
2
votes
0
answers
78
views
Width of symmetric groups
MSE crosspost
For any (finite) group $G$ its length $l(G)$ is the length of maximal chain of proper subgroups (it's known and pretty widely used invariant). But we can also define width function $w_G(...
- 4,436
2
votes
0
answers
124
views
Number of partitions of $\{1,2,\ldots,n\}$ whose blocks are arithmetic progressions of length $t$ or more
This question was inspired by the earlier question here,where no lower bound on arithmetic progression size was given. In particular, $t\geq 3,$ is assumed here.
The set $\{1,\ldots,n\}$ has $2^n$ ...
- 10.1k
2
votes
0
answers
86
views
A system of homogeneous linear equations
This is the "real-life" (but slightly more technical) version of a question I have asked recently.
For a prime $p>10$, let $\mathcal L_X$, $\mathcal L_Y$, and $\mathcal L_Z$ denote the pencils of ...
- 22.8k
2
votes
0
answers
204
views
Real-rooted polynomials with coefficient constraints
My question is whether there exists $(a_0, a_1, \ldots, a_{2n-1}) \in \mathbb{R}_{+}^{2n}$ such that
(1). $a_{2k} + a_{2k+1} = \binom{3n-1}{3k} + \binom{3n-1}{3k+1} + \binom{3n-1}{3k+2}$ for all $0 \...
- 151
2
votes
0
answers
49
views
Size of the last non-empty $k$-core of a random graph
Given $n$ and $p$ for $G(n,p)$, how to find the distribution of the size of the non-empty $k$-core with largest $k$?
In particular, what is the probability (for any $n$ and $p$) that only $c$ ...
- 21
2
votes
0
answers
40
views
Efficient $H$ representation of matrices with distinct cyclic shift permuted entries
Given points $v_1,\dots,v_n\in\mathbb Z^n$ in codimesion $1$ hyperplane $x_1+\dots+x_n=t$ with $0\leq x_{i}$ and a cyclic shift permutation $\sigma$ where
$v_1,\dots,v_n$ when written as columns of ...
- 13.7k
2
votes
0
answers
114
views
Does each odd prime $p$ have a primitive root $g < p$ which is the sum of two central binomial coefficients?
The central binomial coefficients are those integers
$$\binom{2n}n=\frac{(2n)!}{(n!)^2}\ \ \ (n=0,1,2,\ldots).$$
QUESTION: Does each odd prime $p$ have a primitive root $g<p$ which is the sum of ...
- 14.5k
2
votes
0
answers
108
views
dividing a square into unique rectangles with the same perimeter
There's a solution for dividing a square into unique rectangles with the same area which is the blanche dissection.
There's also a solution for dividing a square into unique rectangles with the same ...
- 21
2
votes
0
answers
62
views
Twisted graph duplication
I want to know if the following operation on graphs is already studied or considered somewhere, and if so what it is used for and what it's called.
Let $G = (V, E)$ be a directed graph. Define $d(G)$ ...
- 105
2
votes
0
answers
124
views
Can this sum be majorized?
Suppose that, we have some real numbers $r_1,r_2,\dots,r_m \in [0,1]$; and we study a sum,
$$
S_1= \sum_{i=1}^m \binom{m}{i}(-1)^{i-1}f(r_i),
$$
for $f:[0,1]\to[0,1]$ a concave bijection. Now, take ...
2
votes
0
answers
96
views
An extremal sum for hypergraph degrees
Consider a rank-$r$ hypergraph $H = (V,E)$. I would a lower-bound of the following form:
$$
\sum_{e \in E} \frac{ \sum_{v \in e} \text{deg}(v) }{\max_{v \in e} \text{deg}(v)} \geq c \sum_{v \in V} \...
- 3,407
2
votes
0
answers
82
views
A lattice ordered by inclusion and isomorphic to the lattice of quotient groups of a finite group
Let $G$ be a finite group. Consider the lattice $$L=\{ G/N:\text{$ N $ is a normal subgroup of $G $}\},$$ where $G/N \leq G/K$ if and only if $K\leq N$. The lattice operations ∧ and ∨ on quotient ...
2
votes
0
answers
190
views
Full-rank factorization property of integer-valued matrices
$\newcommand{\al}{\alpha}
\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\ep}{\varepsilon}
\newcommand{\ga}{\gamma}
\newcommand{\Ga}{\Gamma}
\newcommand{\la}{\lambda}
\newcommand{\Si}{\...
- 118k
2
votes
0
answers
84
views
Combinatorial model for twisted involutions in $S_n$
Let $(W,S)$ be a Coxeter group and $*:S \to S$ be an automorphism of the Dynkin diagram of $W$ so that $*^2$ is the identity.
This induces a bijection $*:W \to W$ mapping $w = s_1 \dots s_n$ to $w^* = ...
- 1,899
2
votes
0
answers
90
views
Proving that a series converges to zero (involves combinatorial and an alternating sum)
I'm working on this series:
$$\lim_{i\rightarrow\infty}\sum_{l=0}^{i-1}\left|\sum_{k=0}^l(-1)^{k+1}\binom{p+q+i+2}{k}\binom{p+q+l-k+1}{p+q}
\frac{(p+1+l-k)^i}{(p+q+i+1)!}\right|$$
where $(p,q)$ are ...
user123077
2
votes
0
answers
90
views
Representable integer matrices
Let $C, R \in \mathbb{Z}^n$. If there is an $n \times n$-matrix $M$ with all entries being integers such that the sum of the entries of column $k$ equals $C(k)$, and the sum of the entries of row $k$ ...
- 45.5k
2
votes
0
answers
84
views
Permutation factorizations according to number of generated orbits
Let $\pi$ be a permutation in $S_n$ with cycle type $\lambda$.
How many factorizations into two factors $\pi=\sigma_1\sigma_2$ are there, such that the subgroup $\langle \sigma_1,\sigma_2\rangle$ ...
- 2,542
2
votes
0
answers
77
views
Question on a generalized Dirichlet series
Given the generalized Dirichlet series
$$S(x) =\sum_{(n,m)\in \mathbb{Z}^2}e^{-x\sqrt{n^2+m^2}} $$
is there any way to solve the equation
$$2S(2x)=S(x)$$
for $x\in\mathbb{R}$? I am only interested in ...
- 501
2
votes
0
answers
104
views
Expected value of maximal accumulation of functions $f:\{1,\ldots,n\} \to \{1,\ldots,n\}$
For any positive integer $n$, let $[n] = \{1,\ldots,n\}$. Let $[n]^{[n]}$ denote the set of functions $f:[n]\to [n]$. For $f\in[n]^{[n]}$, we define the maximum accumulation $\text{macc}(f)$ by $$\...
- 45.5k
2
votes
0
answers
59
views
Maximum number of edges on $2^{k-1}+s$ vertices of a $k$-dimensional cube?
Let $k$ be an even number. For a $k$-dimensional cube (http://mathworld.wolfram.com/HypercubeGraph.html) $Q_k$, let $G$ be a subgraph of $Q_k$ with $2^{k-1}+s$ vertices, for $1\le s\le 2^{k-1}-1$. I ...
- 251
2
votes
0
answers
218
views
Ideals with the same Hilbert series
Consider a polynomial ring $\mathbb C[x_1,\ldots,x_n]$ that is $\mathbb Z_{\ge 0}$-graded by degree. Let $I$ and $J$ be two homogeneous ideals therein with the same Hilbert series, i.e. with their ...
- 3,493
2
votes
0
answers
94
views
Publicly Accessible TSPLib95 Solutions
I have asked this question on MSE, but besides earning a TumbleWeed award, there was no feedback.
My question is, where I can download all optimal tours of the TSPLib95 library? I already did a lot ...
- 12.7k
2
votes
0
answers
180
views
Sum of reciprocals in finite fields
Let $p$ be an odd prime number which large enough. I am interested in the study of the sums of reciprocals in the field $\mathbb{F}_p$.
In particular, I have the following question:
which primes $p$ ...
- 337
2
votes
0
answers
120
views
Number of distinct rows and columns in a matrix with bounded number of entries
How many distinct rows and columns a real square matrix can have (at least in symmetric case) such that rank of matrix is $r$ and entries:
are from $\{-b,-b+1,\dots,0,\dots,b-1,b\}$?
are from $\{-b,-...
- 13.7k