All Questions
Tagged with combinatorics or co.combinatorics
3,204 questions with no upvoted or accepted answers
0
votes
0
answers
143
views
Monotone graph parameters under vertex deletion
Let $f(G)$ denote any parameter of a graph $G$ for which $f(G) \geq f(G - \{v \})$, where $v$ is any vertex in $G$. We could describe such parameters as being monotone under vertex deletion. Does ...
0
votes
0
answers
87
views
maximum weight k-edge problem
Given positive integer $k$ and an undirected graph $(V,E)$, with nonnegative (non-uniform) weights on the nodes. Find $k$ edges whose spanning nodes have the maximum weight.
Is this in P or NP? I ...
- 101
0
votes
0
answers
266
views
Finding the effective maximum number of subspaces in a finite dimensional vector space
Hi mathoverflow community, may be some one may give me a hint on the following problem before I spend much time on brute force search.
For $q$ a prime number and $n=6$, let $\mathbb {F}_{q}^{n}$ be ...
0
votes
0
answers
125
views
An easy-to-state elusive combinatorial problem (revisited)
The following question is tackled with based completely on David Speyer's argument on a related problem:
Let $x,y,z\in \mathbb{Q}:x\ge1,y\ge1,z\ge1$. What should be the minimum value of $s\in \mathbb{...
- 296
0
votes
0
answers
347
views
An interesting version of the problem “balls into bins”
Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...
- 1
0
votes
0
answers
88
views
Approximate closed-form solution for a recurrence
Find an (approximate) closed-form solution for $S(m, b)$.
$$S(m,b)=\sum_{i=0}^{\lfloor (e-1)/2\rfloor}{e \choose i}S(m-1, b-i) \quad +
\sum_{i=\lfloor (e-1)/2\rfloor+1}^{\min(b,e)}{e\choose i}{(...
- 111
0
votes
0
answers
91
views
Pruning copies of an element from a multiset via a uniform random selection process - does vigilance matter?
This is an extension of a previous question of mine (nicely answered by Douglas Zare): Filling a bin with one type of element when uniformly selecting from a set of two (with bias)
Say I fill a ...
- 43
0
votes
0
answers
142
views
Notation for substructure, especially for permutations?
Is there a standard notation that expresses substructure?
The specific case that I care about is the following:
Suppose $\sigma,\tau$ are permutations such that $$\sigma(x)\not=x\implies \sigma(x)=\...
- 1,329
0
votes
0
answers
169
views
Using extended group rings for combinatorial generating functions
In work of mine recently, I have come to investigate generalised recurrence relations. The generalisation I have in mind is where, instead of natural numbers or integers, the recurrence is over some ...
- 170
0
votes
0
answers
74
views
Number of subgroups of finite abelian p-groups with a certain cotype.
Given a finite abelian $p$-group $G$ of rank $r$ I'm looking for the number of elements in a group $H$ with $\mathrm{rk}(H)=r$, such that $H/\langle y\rangle\cong G$.
- 23
0
votes
0
answers
325
views
Number of graphs with a cycle
I need to compute the number $f(n,k)$ of graphs on $n$ vertives having a cycle of length $k$.
We can consider the graphs are labelled or not.
- 1
0
votes
0
answers
102
views
Efficient algorithm for computing the mixed moments of sums of random variables
Let $X_1,\dots,X_m$ be dependent random variables. We are interested in efficient algorithms for computing the following quantity:
$$E\Big[\Big(\sum_{i=1}^m X_i\Big)^k\Big],$$
where $k\in\mathbb{N}$ ...
- 1
0
votes
0
answers
39
views
Minimum number of solutions in a system of equalities and non-equalities
Let $k<N$ and $P_1, ..., P_{2k+1}, \lambda_1, ..., \lambda_k$ be elements of a finite group $G$ of size $N$.
Find the minimum number of solution of the system
$$P_{2i} + P_{2i+1} = \lambda_i, \...
- 43
0
votes
0
answers
99
views
Laplacian using SDP
Is there any suggestion about how could one construct a model that uses semidefinite programming that minimizes sum of k smallest eigenvalues of Laplacian matrix?
I found two papers that have done ...
- 161
0
votes
0
answers
141
views
Reference Request: a paper by Yoseloff about a proof of Sperner's Lemma
Dear Overflow,
Apologies in advance if I'm posting this in the bad place, but I was hoping some of you could point out to me a place where I could read online the following paper by Yoseloff, where ...
- 625
0
votes
0
answers
147
views
A good upper bound on the size of k-biclique in random bipartite graphs.
Let $G = (X \cup Y, E)$ be a random bipartite graph, where $X$ and $Y$ are the set of vertices and $E$ the set of edges. I want to find an upper bound of the largest biclique in which exactly $k$ ...
- 1
0
votes
0
answers
71
views
products/factoring of two hypergraphs with same vertex set?
all the basic products for graphs have been extended to hypergraphs[1].
is there a concept of a product of hypergraphs with the same vertex set? has this been studied?
normally the hypergraph ...
- 529
0
votes
0
answers
1k
views
Calculating the Shapley value in a weighted voting game.
Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
- 101
0
votes
0
answers
555
views
VC dimension and boolean hypercube subgraphs
Are there any well studied graph theoretic properties that are common to all subgraphs of the boolean hypercubes that have a given VC dimension d.
- 11
0
votes
0
answers
241
views
A closed formula for a sequence of integers
Let $(a_n)$ be the sequence of minimum values of the expression (depending on $\ell$):
\begin{equation*}
a_n=\min \bigg\lbrace ((\ell+1)j-n)!\,(n-\ell j)!\quad \text{for}\; \\,\bigg\lceil\frac{n}{\...
0
votes
0
answers
266
views
In a transportation problem, given a northwestern corner rule solution, how many row and column permutations correspond to that solution?
Consider a $n,n$ transportation problem with two $d$ dimensional integral vectors $r$ and $c$ with the same total sum.
The Northwestern corner rule is a simple way to create a basic feasible solution ...
- 73
0
votes
0
answers
394
views
Kakeya problem and arithmetic progressions
Here's something I also posted on Stackexchange recently. It's very related to the Kakeya problem, yet I fail to see why this is true. It goes like this:
Let $r > 2$ be an integer parameter. Let $...
0
votes
0
answers
613
views
Examples of Hamiltonian Cycle Problem / Traveling Salesman Problem in general grid graph form
I understand that there is a polynomial algorithm to solve TSPs that are in solid grid graph form (grid graphs without holes).
I am particularly interested in the non-solid grid graph form of the ...
- 45
0
votes
0
answers
127
views
A problem about partial sum of random number composition
Consider the strong random number composition,
$x_1 + x_2 + \cdots + x_n = m$, with $x_i > 0$ and all possible compositions have the same probability.
Let random variable $S_i = \sum_{j=1}^i x_j$...
- 177
0
votes
0
answers
103
views
An upperbound related to inductively reducing a set by adding the two least elements
I hope this is not too trivial to be asked here, but here it goes anyway. This is just out of curiosity (regarding a problem with graphs but I have "reduced" it to the problem below:)
Let $S_0={\{a_1,...
- 443
0
votes
0
answers
346
views
A pairing problem (mb related to Wick theorem)
Hi,
My question is : is there a known method to count how many couple can we make out of $2n$ three members family ?
To be more precise, let's say that we have $6n$ individuals grouped three by ...
- 244
0
votes
0
answers
113
views
Question regarding contiguous forms
I read about contiguous forms in Achill Scürmann's thesis on positive quadratic forms. I am wondering about one aspect of the Voronoi algorithm presented in there, that enumerates all arithmetically ...
- 149
0
votes
0
answers
291
views
5 player round-robin tournaments
Is there any literature on the order structure coming from round-robin tournaments? I play games on littlegolem and the tournaments are mostly 5x5 round-robins. I noticed at the end, after sorting ...
- 22.8k
0
votes
0
answers
727
views
Decomposing max-convolution of sum of functions ?
Hello.
$R, F_1, F_2, F_3$ are random (not-convex, not-concave) 2D matrices of size 100x100.
$R$ is a linear combination of $F_1, F_2, F_3$.
Explicitly, $R = w_1 F_1 + w_2 F_2 + w_3 F_3$
where $w_1,...
0
votes
0
answers
120
views
A search for optimal order ideals
At the behest of Gerhard Paseman I'll describe the problem that I alluded to in
name for a partial order.
Let $M = M(\infty)$ denote the set of all finite subsets of the positive integers $\mathbb{N}$...
- 4,636
0
votes
0
answers
379
views
Showing that Paley Graphs are Edge-Transitive
I would like to show that Paley graph are rank $3$ graphs (i.e. Vertex-Transitive, Edge-Transitive and Non-Edge-Transitive).
Showing that they are vertex transitive is easy - every $x \mapsto x+k$ is ...
- 163
0
votes
0
answers
192
views
Generate combinations with repeated symbols?
I would like to generate fixed size sequences contained a fixed number of repeated symbols.
For example how to generate sequences of size N containing exactly p symbols of one type q symbols of ...
- 121
0
votes
0
answers
261
views
Fast removal of weighted edges in a graph in a way such that all shortest paths are preserved
This problem is analogous to fast removal of the minimum number of edges in a weighted graph such that if the graph were to be drawn on paper with edge lengths linear in proportion to their weights, ...
- 1
0
votes
0
answers
572
views
Proof of Upper bound of price of anarchy in local connection game
I am looking at the work by Fabrikant "On a Network Connection Game" (http://webcourse.cs.technion.ac.il/236620/Spring2005/ho/WCFiles/FLMPS_netDesign.pdf). This work presents a game-theoretic ...
- 599
0
votes
0
answers
286
views
12 and 13-bit balanced Gray codes
I am trying to find a transition sequence for both 12 and 13 bit balanced Gray codes. I know there are some excellent papers on the topic of deriving these sequences available on the internet, but I ...
- 425
0
votes
0
answers
319
views
Estimating a multinomial sum
I have the following sum
\begin{equation}
\sum_{r_1=q+1}^{\tau}\dots\sum_{r_\lambda=q+1}^{\tau}{\tau\choose r_1,\dots,r_\lambda,\tau-r_1-\dots -r_\lambda} (\Lambda-\lambda)^{\tau-r_1-\dots-r_\lambda}
\...
0
votes
0
answers
154
views
Finding the bottleneck in a chain of functions
I have a problem that involves finding a bottleneck. It appears to me to be a linear bottleneck assignment problem, but recognizing (and solving) such problems is far outside my area of expertise. If ...
- 1
0
votes
0
answers
189
views
Packing Icons Onto A screen
You are trying to pack icons onto a screen that is divided into n horizontal rows of uniformly varying size. The rows narrow by a fixed ratio as one goes up the screen from the bottom. Since the icons ...
0
votes
1
answer
349
views
Log associahedra and log noncrossing partitions--raising ops and symmetric function theory for $A_n$ (references)
Where do the following three sets $[LA]$, $[ILA]$, and $[LN]$ of partition polynomials appear in the literature?
There are two sets of partition polynomials, not in the OEIS, that serve as the ...
- 10.5k
0
votes
1
answer
123
views
Recognizing perfect Cayley graphs as tensor products
It is known (and can easily be seen) that a unitary Cayley graph on $n=\prod_ip_i$, ($p_i$ distinct primes) vertices with $n$ square-free can be recognized as the tensor product of the graphs $K_{p_i}$...
- 2,089
0
votes
1
answer
431
views
Efficient isomorphic subgraph matching with similarity scores
I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
- 223
0
votes
2
answers
747
views
Number of Dyck paths with k returns and b peaks
The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by
$$\frac{k}{2n-k}{2n-k \choose n}.$$
The number of Dyck paths from the ...
- 21
-1
votes
1
answer
825
views
How to calculate determinants of such types?
Consider next determinant that we want to expand around $h=1$
\begin{eqnarray}
Z_q \ = \ h^{N N_f} \ \ \left ( \prod_{n=1}^{N} \ \sum_{l_n=0}^{N_f -q} \ h^{2l_n+q} \ \binom{N_f}{l_n} \right ) \ \...
-1
votes
1
answer
65
views
A follow-up question in a proof in a paper on complete multipartite graphs
A follow-up question from the following article/paper:
"Proof of a conjecture on distance energy change of complete multipartite graph due to edge deletion"
by Shaowei Sun and Kinkar Chandra ...
- 199
-1
votes
1
answer
215
views
Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques
Let $G$ be a perfect/ weakly perfect Cayley graph on an abelian group with respect to a symmetric generating set. In addition let the clique number be $\omega$ which divides the order of graph $n$. ...
- 2,089
-1
votes
1
answer
98
views
Tuza theorem to prove vizing theorem
The Tuza theorem states that every graph with no cycle congruent to 1 mod $k$ is $k$ colorable. Now, the line graph of any simple graph of maximum degree $d$ is seen to posess the property that it has ...
- 2,089
-1
votes
1
answer
395
views
Odd & even permutations and unit fractions
One more motivated by recent questions of Zhi-Wei Sun.
Let $S_n$ be the group of permutations of $\{1,2,\ldots, n\}$.
Is it true that, for every $n \ge 8$, there is at least one even permutation $\...
- 4,589
-1
votes
1
answer
76
views
Transforming random variables for having good property?
For arbitrary functions $A$ and $B$ and independent random variables $X$ and $Y$, assume that
\begin{align}
\Omega&\triangleq \{(x,y): A(x,y)=1\},\\
\Lambda&\triangleq \{x: B(x)=1\}.
\end{...
- 287
-1
votes
1
answer
105
views
What type of graph is this? (Edges that are valid / invalid depending on route to node)
I'm trying to model a questionnaire where the flow between questions depends on the answers given in previous questions.
Example. (Node represent questions, edges represent answers).
As you can see ...
- 1