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.

Filter by
Sorted by
Tagged with
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 ...
Connor's user avatar
  • 251
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 ...
T. Amdeberhan's user avatar
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 ...
user136454's user avatar
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 ...
kodlu's user avatar
  • 10.1k
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 @...
kodlu's user avatar
  • 10.1k
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 ...
Avi Steiner's user avatar
  • 3,031
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, ...
Y. Malcolm's user avatar
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 ...
Jianrong Li's user avatar
  • 6,101
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$. ...
DavitS's user avatar
  • 205
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 ...
neverevernever's user avatar
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 ...
Đào Thanh Oai's user avatar
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-...
Bazin's user avatar
  • 15.1k
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 ...
Fan Zheng's user avatar
  • 5,119
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 ...
Shivin Srivastava's user avatar
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 $...
RFZ's user avatar
  • 298
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+...
Robert A. Russell's user avatar
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 ...
user avatar
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 ...
Moshe's user avatar
  • 31
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 ...
NatNgs's user avatar
  • 113
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" ...
public satanic void's user avatar
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 ...
koalo's user avatar
  • 195
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 ...
C.F.G's user avatar
  • 4,165
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 ...
Igor Rivin's user avatar
  • 95.5k
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 ...
Mare's user avatar
  • 25.8k
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}...
Lwins's user avatar
  • 1,531
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] :=...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
user3399994's user avatar
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 ...
Kuifje's user avatar
  • 225
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 ...
Dominic van der Zypen's user avatar
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 ...
Victor's user avatar
  • 655
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 ...
emme's user avatar
  • 23
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 ...
Jianrong Li's user avatar
  • 6,101
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, ...
snaleimath's user avatar
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\{...
kodlu's user avatar
  • 10.1k
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?
user1099798's user avatar
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(...
Connor's user avatar
  • 251
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 ...
Meysam Ghahramani's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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 ...
f10w's user avatar
  • 163
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 ...
user82111's user avatar
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}{...
VT Jeffo's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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 ...
snaleimath's user avatar
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 ...
Stijn's user avatar
  • 338
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|]...
jsliyuan's user avatar
  • 651
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$...
Dominic van der Zypen's user avatar
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) ≤ ...
murv's user avatar
  • 75
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,$ ...
Jernej's user avatar
  • 3,433

1
172 173
174
175 176
211