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.
10,511
questions
1
vote
1
answer
120
views
Find large "induced" bipartite graph in a dense graph?
Do there exist constants $d>0$, $0<c<1$, $\delta>0$ so that for all large $n$, there exists a graph $H$ satisfying $$e_H\ge dn^2,$$ and then no matter how we remove some edges from $H$ to ...
1
vote
1
answer
152
views
$q$-plane partitions & specialization & interlinks
MacMahon's enumeration of all plane partions (PP) inside an $n$-cube generalizes to
$${\tt PP_n}(q)=\prod_{i,j,k=1}^n\frac{1-q^{i+j+k-1}}{1-q^{i+j+k-2}}.$$
A $q$-analogue of symmetric plane partitions ...
1
vote
1
answer
226
views
Three edges in a path
Given a finite connected graph, let $A$ be a set of edges such that each edge in $A$ is not part of a cycle. Suppose that no path contains all edges in $A$. Must it be true that for some three edges ...
1
vote
1
answer
878
views
Concentration of the load of the maximally loaded bin ($m$ balls $n$ bins) with nonuniform bin probabilities
There is a common argument used when investigating the concentration of the maximally loaded bin (say $X$ is the maximum load) when $m$ balls are thrown into $n$ bins under the uniform distribution. I ...
1
vote
1
answer
249
views
Largest cardinality $n$ of a subset $A$ of $\{1,2,\ldots,M\}$ such that $(A+A) \cap A$ is empty
Assume that the set $A$ does not have simple structures (such as the case that when all elements are odd numbers in $[1,M/2]$ then all sums are even thus there are no solutions, as pointed out by @...
1
vote
1
answer
106
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 ...
1
vote
1
answer
393
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, ...
1
vote
1
answer
294
views
Reference request: Catalan number of type B
Are there some generalized Catalan number of type $B$ such that the sequence of the numbers is $3,9,29,97,333$ for $n=2,3,4,5,6$?
As discussed in this previous question, there are at least two types ...
1
vote
1
answer
120
views
$k$-substrings of a binary string
Let $k > 1,$ and $a=a_1a_2...a_{2k-1}$ be a binary string, i.e. $a_i\in \{0,1\}$. Consider contiguous substrings of $a$ of length $k (k-$substrings$): b_i := a_ia_{i+1}...a_{i+k-1}, 1\leq i\leq k$. ...
1
vote
1
answer
134
views
The number of permutations with a special condition
Suppose we are considering $S_n$. For any permutation, let $h$ be the number of derangement and $N$ be the number of cycles with length no less than 2.
I'm interested in the number of permutations ...
1
vote
1
answer
163
views
How many points appear in the plane when the chain of n-gons is close?
Let $A_{11}A_{12}\cdots A_{1n}$ be a regular $n$ polygon, we call $A_{11}A_{12}\cdots A_{1n}$ is the $1st-n-gons$. Now we construct the $2nd-n-gon$ based two condition as follows:
$2nd-n-gons$ is ...
1
vote
3
answers
320
views
Estimate for the binomial coefficients and bounds from below for the Beta function
Let $n\ge p\in \mathbb N$ and let $\binom{n}{p}$ be the binomial coefficient. I believe that
$$
\binom{n}{p}\le 2^n\sqrt\frac{2}{π n}.
$$
Question: is that true? Of course I would like it as a non-...
1
vote
1
answer
114
views
Probability for a group of stones to live on an infinite Go board
Suppose on an infinite two dimensional Go board the tengen is occupied by a black stone, and every other grid point is occupied by a black stone, or a white stone, or nothing, with probability 1/3 ...
1
vote
1
answer
128
views
Number of distinct points in an n-dimensional tetrahedron
Consider an n-dimensional tetrahedron with $n+1$ vertices $\langle v_0, v_1, \dots,v_n\rangle$. $v_0$ is the origin while $v_i$ lies on $e_i$ (the $i^{th}$ coordinate axis) at a distance $D$ from the ...
1
vote
1
answer
128
views
Existence of Arithmetic Progression from density inequality
Let $A\subset \{0,1,\dots, N-1\}$ such that $$|A\cap [0,N/3)|\geq \left(\delta+\dfrac{\delta}{8}\right)\cdot \dfrac{N}{3},$$ where $\delta\in (0,1]$. Prove that exists arithmetic progression $P$ with $...
1
vote
1
answer
258
views
Ordinary Generating Function for OEIS A056296?
The sequence OEIS A056296 can be obtained using
$
a(n)={1\over n}\sum_{d\backslash n}\varphi(d)\begin{cases}
{n/d+2\brace3}-{n/d+1\brace3}, & \text{$6\backslash d$;} \\
{n/d+2\brace3}-3{n/d+...
1
vote
1
answer
476
views
The combinations of a finite multiset [closed]
Suppose there is a basket $S$ containing $3\ \color{blue}{blue}$, $2\ \color{green}{green}$ and $1\ \color{red}{red}$ balls. A subject can extract any $k$ number of balls (including $0$) at random ...
1
vote
2
answers
349
views
A variation of longest paths in directed acyclic graph
Let $D=(V,A)$ be a simple directed acyclic graph, where $A$ is a set of arcs. Let $S$ be a subset of $\{(u,v)| \text{there is a directed path from $u$ to $v$}\}$. The $S$-length of a path $P$ is ...
1
vote
1
answer
113
views
Number of combinations of combinations depending on set and element sizes
Since some days, I'm trying to simplify a recursive and long algorithm into a fast (non recursive) equation taking 3 parameters into account.
I want to precise that I don't know really how to specify ...
1
vote
1
answer
115
views
Number of iterations required for a transposition cipher to yield the original input
I have asked this question on math.stackexchange.com but received no response; hoping someone on here can help.
Suppose a function $f$, representing what I call a "dynamic transposition cipher" ...
1
vote
1
answer
132
views
Term for the maximum number of vertices per depth of a rooted tree
I am searching for a term that describes the following property of a rooted tree (or actually a DODAG, but that should not make a difference) and preferably for a publication that uses/introduces this ...
1
vote
1
answer
142
views
Edges of every simple graph can be colored with at most $s+1$ color
This question is related to my previous post: New edge coloring problem in graph theory.
Added: Let $G$ be a simple graph. Consider the following edge coloring:
We are allowed to use repetitive ...
1
vote
1
answer
155
views
counting ball in bin placements of a certain kind
In Miklos Bona's very nice "A Walk through Combinatorics", a following question is asked:
Suppose you have two hundred balls placed in 100 urns, so that each
urn contains at least one ball, and ...
1
vote
1
answer
94
views
Realising matrices as Cartan matrices
Given a matrix with natural numbers $\geq 0$ as entries and having determinant equal to one and positive diagonal entries. Is it the Cartan matrix of a finite dimensional algebra of finite global ...
1
vote
1
answer
153
views
Minimize average bitwise entropy with given pairwise hamming distance
Suppose we have $n$ strings (or vectors) $a_1, a_2, \dots, a_n \in A^m$, where $A$ is an arbitrary set satisfies $|A| \geq n$. And we limit their pairwise hamming distance by
$$ d(a_i, a_j) \geq d_{ij}...
1
vote
1
answer
100
views
$k$ tasks on $n$ machines
Suppose I have $k$ tasks that I can run independently on $n$ machines where $k\geq n$. Let $t_i\in\mathbb{N}$ be the number of seconds that task $i$ takes to be done on any machine (for any $i\in[k] :=...
1
vote
1
answer
237
views
Sparse subset of $\mathbb{N}$ with a summation property
For $A\subseteq \mathbb{N}$ and an integer $k\geq 1$ we set $S_A(k) = \{B\subseteq A: B\text{ is finite and } \sum_{b\in B} b = k\}.$
We say that a set $A\subseteq \mathbb{N}$ is sparse if $$\text{lim ...
1
vote
1
answer
189
views
Algorithm for Removing Inverted Elements from a Permutation
I currently have a problem, whose solution requires to remove from a permutation of $\lbrace 1,\ \dots,\ n\rbrace$ those values that are to the left of a smaller one.
My idea was to remove the ...
1
vote
2
answers
1k
views
Rank adjacency matrix bipartite graph
I am interested to know what kind of characterizations are known of the rank of bipartite graphs $G(n,m)$ ($n$ vertices on one side, $m$ on the other, $n \leq m$).
When is the incidence matrix full ...
1
vote
1
answer
196
views
Show $0-1$ Knapsack is polynomially reducible to this problem
I have already posted this question here but have not received an answer so I am cross-posting with hope to reach a larger amount of mathematicians:
Let $T=\{1,\cdots,n\}$ and consider the ...
1
vote
1
answer
69
views
Clique decompositions that are maximal with respect to refinement
If $X$ is a non-empty set and ${\cal A}, {\cal B}$ are covers, then we say that ${\cal A} \leq_{\text{fin}} {\cal B}$ if for all $A\in {\cal A}$ there is $B\in{\cal B}$ such that $A\subseteq B$ and we ...
1
vote
1
answer
198
views
Maximum/minimum intersection of two graphs
I wonder if the following graph problems have been studied and have names.
Problem(s).
Given two $n$-vertex unlabeled graphs $G_1$ and $G_2$, find their maximum/minimum edge intersection. That is ...
1
vote
1
answer
199
views
Random walks cover time in random regular graphs
Let $G=(V,E)$ be a random $r$-regular graph on $n$ nodes. Perform a random walk on $G$, starting from a node chosen according to the walk stationary distribution (i.e. chosen uar from $V$).
Claim. If ...
1
vote
1
answer
103
views
How to draw a quiver for a pseudoline arragement?
In the lecture notes, on page 24, there is an example of drawing a quiver for a pseudoline arragement. What is the rule to draw a quiver for a pseudoline arragement? I don't know how to put the ...
1
vote
1
answer
200
views
Hyperplane generic to a given arrangement
At the moment, I am reading the paper "on the connectivity of the realization spaces of line arrangements" of Nazir and Yoshinaga.
I would like to extend their Lemma 3.2 to higher dimension. However, ...
1
vote
1
answer
95
views
Reference for a local density theorem for binary vectors
I have the following theorem written on my whiteboard, but have misplaced the reference. I believe the probabilistic method may be involved in the proof. Any pointers appreciated.
Theorem Let $v\in\{...
1
vote
1
answer
583
views
If the two smallest eigenvalues of the Laplacian matrix of a network are equal to zero, then does it mean that the network is not connected? [closed]
What does it mean if the two smallest eigenvalues of the Laplacian matrix of a graph are equal to zero?
1
vote
2
answers
329
views
Tight bound of Turan number for K_{1,t,t}
I'm looking for a tight bound for Turan number $ex_2(n,K_{1,t,t})$, where $K_{1,t,t}$ is the complete 3-partite graph with parts of size 1, t, and t.
The motivation is that we now $ex_2(n,K_{t,t})=O(...
1
vote
1
answer
131
views
Reduced echelon form of sparce matrices and constructing hash function
Let $G$ be a $d$-regular graph, and $A$ be the incidence matrix of $G$. Also suppose $B$ is a reduced echelon form of $A$ such that computations are in $\mathbb F_2$. Given matrix $B$, can we find ...
1
vote
1
answer
462
views
Some divisibility constraints in Frobenius coin problem
Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$.
Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ excellent if linear form ...
1
vote
2
answers
191
views
The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)
In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$).
This is what I observed from some books (e.g. "Combinatorial ...
1
vote
2
answers
86
views
Position likelihood in a 2D graph [closed]
I am looking for general principles or specific answers to this generic example.
Assume a 2d grid with no boundaries and a roving dot (ant/drunk guy/particle) that is initially located at some ...
1
vote
1
answer
304
views
How do powers affect asymptotics in generating functions?
Let $a_n$ be a sequence of non-negative real numbers, and $A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$ its exponential generating function. Also, suppose $B(x) = \sum_{n=0}^{\infty} b_n \frac{x^n}{...
1
vote
2
answers
465
views
Worst case difference in rank by column-row swapping
Given a matrix $m\in\{-1,+1\}^{n\times n}$. Consider $m^\sigma$ to be collection of all matrices obtained from $m$ by permuting rows and columns.
Consider $\mathscr{M}[m^\sigma]$ to be collection of ...
1
vote
1
answer
196
views
Singular homology of the zero loci of polynomials
I am very sorry but apparently I am really weak in cohomology flavored questions. I try to reformulate my problem in a very simple and hopefully clear way. This question is related with a problem in ...
1
vote
1
answer
283
views
Random graphs with boundary in a game (Tsuro)
Suppose we have an $n \times n$ board and we have $n^2 - 1$ square tiles. These tiles consist of a 8 vertices, two on each edge, and every vertex is connected to precisely one other vertex. These ...
1
vote
1
answer
135
views
Balls from bin with replacement, distinct elements, concentration inequality
Draw $n$ numbers, denoted by $a_1, a_2, \ldots, a_n$, from set $[n]$, that is, for each $i$, $a_i$ is a uniformly random number from $[n]$.
Let $A = \{a_1, a_2, \ldots, a_n\}$. Then
$$
\mathbb{E}[|A|]...
1
vote
1
answer
120
views
Minimality condition in a certain class of hypergraphs
A hypergraph is a pair $H=(V,E)$ such that $V$ is a (possibly infinite) set and $E\subseteq \mathcal{P}(V)$. $C\subseteq E$ is said to be a cover if $\bigcup C = V$ and $C$is minimal if $C'\subseteq C$...
1
vote
1
answer
329
views
Probability of connected graph on torus
Let $G = (V, E)$ be a graph on n vertices constructed in the following way:
Each vertex $v \in V$ is positioned uniform randomly in $[0, 1] × [0, 1]$.
Connect two vertices $u, v \in V$ if $d(v,u) ≤ ...
1
vote
1
answer
183
views
A generalisation of Narayana-like numbers (walks on the 2D lattice)
I apologize in advance if this question has a trivial answer. I am pretty sure this kind of problem was already studied and I am mostly asking for good references.
Given integers $0 < k \le n+1,$ ...