Tagged Questions

2
votes
1answer
53 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
vote
1answer
49 views

to find disconnected graphs

We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
1
vote
0answers
27 views

is the $d$-dimensional arrangement of Trees still $NP$-hard?

The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
7
votes
2answers
179 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
1
vote
2answers
37 views

Could graph theory aid in the understanding of comparison sorting algorithms?

I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article. Up to $n=15$, we know how many comparisons between elements one must make to ...
3
votes
1answer
130 views

diameter and radius of a regular graph

I am trying to find the radius and diameter of a regular graph $G$ with $d(v_i) < (n-1)/2$. I know for $d(v) \geq (n-1)/2$, $\rm{diam}(G) \leq 2$ and $\rm{radius}(G)=\rm{diam}(G).$ If we are not ...
2
votes
1answer
46 views

Unique sequences from different sets

I am given $n$ sets with a selection of $m$ elements, such as: $$S = \{\{0\}, \{1, 2, 3\}, \{1, 2, 3\}, \{3\}\}$$ I am trying to calculate the number of unique sequences that contain all elements ...
2
votes
2answers
52 views

eccentricity in vertex transitive graphs

I am trying to prove the following.. If $G$ is a veretx transitive graph, then how can we prove that eccentricity of every vertex is same? Getting no idea from where to start? How to prove the same ...
1
vote
1answer
29 views

Why no cut-vertices or cut edges in a graph where eccentricity is same for all vertices

I need help to prove the following statement. There are no cut-vertices or cut-edges(bridges) in a graph where eccentricity is same for all vertices. I am getting that if the graph contains a ...
2
votes
1answer
44 views

self-centered property of complement of a self-centered graph

I was working out on a problem. Came out with a result that $C_n$ is self centered graph, its complement is also self centered, infact 2-self-centered. Worked out on other few graphs which are self ...
2
votes
1answer
62 views

Eccentricity of vertices in a graph

This question is related to my last question about regular graphs Eccentricity of vertices in a regular graph. I got the required answer but I am having a doubt. Can we put restriction on number of ...
3
votes
0answers
65 views

Binomial Coefficients optimization

Given n and R, I have to find the minimum value of k such that: $${(2^n)-1 \choose k}\bmod(2^n)==R$$ Where $k = \{0, 1, 2, \dots, 2^n-1\}$ Here ${n \choose k}$ is the binomial coefficient ...
3
votes
2answers
76 views

Eccentricity of vertices in a regular graph

I was just trying to find out the eccentricity of the vertices in regular graphs, given in the link http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html#CRG. Surprisingly, eccentricity is the same ...
0
votes
0answers
46 views

Is the choose function polynomial?

I have this problem which is described as follows: Input: You are given a multi-set M (a set that can contain duplicates), and two numbers P and T. $ M = {(x_1,y_1), (x_2,y_2), ..., ...
6
votes
2answers
155 views

Simplifying Catalan number recurrence relation

While solving a problem, I reduced it in the form of the following recurrence relation. $ C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1} $ However ...
3
votes
1answer
125 views

to check the minimal self-centered property of graphs

While working out on a problem, I found that cycles $C_n$ are minimally self-centered graphs, as if we remove any edge then it is paths $P_n$ and $P_n$ are not self-centered graphs. My question is ...
2
votes
1answer
30 views

to check the self-centered property of a given graph.

Can a graph be self-centered if it contains a vertex of degree one. The simplest counter example that came to my mind is Path. But how to prove the statement if we consider any graph with a vertex of ...
3
votes
1answer
71 views

Is the square of a self-centered graph also self-centered?

I am trying to work out a problem. Given a self-centered graph, is the square of the graph also a self-centered graph? I tried numerically on few graphs given in ...
1
vote
2answers
79 views

Enumerating Rooted labeled trees without Langrange inversion formula

I am wondering how to enumerate rooted labeled trees without the Langrange inversion formula. Because each tree is a collection of other trees, the recursive generating function becomes $$C(x) = x + ...
11
votes
1answer
239 views

In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?

Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard? For example: $M = 2, N = 2$, ans $= 6$ $M = 3, ...
1
vote
1answer
77 views

Combinatorics question. Bit stuck.

Why can't there exist 5 5-digit binary numbers such that each pair has 1 or 2 digits in common? Another way to state the condition is that any pair has either 3 or 4 digits that are different.
3
votes
2answers
109 views

For a simple XML doc, how to find number of possible arrangements of elements (i.e open and close tags) when given maximum number of tags?

For a simple XML doc, how to find number of possible arrangements of elements (i.e open and close tags) when given maximum number of tags ? Let me rephrase the question by example, we have a set ...
4
votes
2answers
66 views

Finding N elements that are included in as many sets as possible

Say I have 20 sets, containing a variable amount of elements. How would I go about finding the 10 elements that cover the most number of sets? Imagine I could search for three terms at once on ...
1
vote
0answers
84 views

Question about the elementary divisors of a special matrix

I have the following question: Is there a closed formula for the elementary divisors of the Matrix $M={(m_{ij})}_{i=1,...,n,\ j=1,...,k}$, where ${m}_{ij}$ is the greates common divisor of $i$ and ...
1
vote
0answers
76 views

What was done to calculate the Ramsey numbers using a quantum computer?

I recently came across this paper titled Experimental determination of Ramsey numbers with quantum annealing I was wondering what exactly the gist of the paper, as I read it, it seems rather ...
1
vote
2answers
37 views

Finding the probability of a client getting the same token in two consecutive interactions.

I am trying to find the probability in the following real-world inspired scenario. If I have a finite set of whole numbers from 0 to 4 billion which I call tokens and $n$ clients. Each time a client ...
4
votes
0answers
93 views

Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?

Remark: I recently rewrote this post, hoping to get answers! I am analyzing the following experiment: Pick an $x \in \{0,\ldots,2k\}$ uniformly at random Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
1
vote
1answer
65 views

List number of moves to defeat the opponent

Given the position of chess board of two players, we have to find the minimum number of moves (and output them) so that only one player playing continuously and optimally defeat the other one ...
1
vote
1answer
53 views

zeros of linear recurence sequences

Given a linear recurrence sequence $\{a_n\}_{n\geq 0}$, how to decide whethere there are infinitely many zeros, or there are only finitely many ones?
0
votes
2answers
117 views

Help calculating combination of combinations

I have a problem which I thought was really easy to solve but now I am here =) I need to construct a final combination of a content based on combinations of various sub-contents. A sub content is a ...
0
votes
1answer
79 views

minimize collision of bit strings

I'm sorry, if I got the wrong expressions, I'm gonna describe it: I got bit-strings of n bits with k ones and want to minimize "collision" The collision count of two strings $a=(a_1,...,a_n), ...
8
votes
1answer
248 views

Throwing balls into $b$ buckets: when does some bucket overflow size $s$?

Suppose you throw balls one-by-one into $b$ buckets, uniformly at random. At what time does the size of some (any) bucket exceed size $s$? That is, consider the following random process. At each of ...
1
vote
1answer
93 views

A Measure for Number of Unique N-Tuples

Suppose I have a multiset of numbers. I'm interested in the number of unique n-tuples that can exist using the numbers from this multiset. Now of course a closed form is of interest here, but what I'm ...
2
votes
1answer
100 views

maximizing number of 4s times number of 7s in decimal representation

$F_4(X)$ be the number of digits 4 in the decimal representation of $X$, and $F_7(X)$ be the number of digits 7 in the decimal representation of $X$. We have to find largest product $F_4(X)\cdot ...
2
votes
1answer
77 views

Johnson-Cut Max-Cut Approximation

The Johnson-Cut is an $O(n^2)$ Max-Cut approximation with a factor of 2. I have these definitions for MC and none for JC so I assume they're the same: $G = (V,E,w)$ with $|V| = n$ and $w : E ...
1
vote
1answer
216 views

Properties of shortest addition chains for small numbers (e.g. up to 600)

Up to which values of $n$ do the following properties hold for strictly monotonically increasing, shortest addition chains (sac) $a=a_1,\dots,a_k$ (definitions below)? a) There exists a sac for $n$ ...
3
votes
2answers
96 views

List of the minimal addition chains

The question of finding the Minimal Addition Chain (MAC) for needed for Addition chain exponentiation seems to be NP-complete. As such, it would be nice to have a list for the small powers already ...
0
votes
1answer
162 views

Max flow Min cut Problem

I have this problem in my Question paper for the BE exam I appeared. I am not able to understand the problem statement and dont know how to use max flow min cut theorem to use it. Please guide me ...
1
vote
1answer
52 views

Algorithm for finding out whether x < y in Tamari lattice

The Tamari lattice is a poset whose objects are ways of bracketing a sequence into pairs - for example (a(bc))d - with the covering relation being rightward application of the associative law, ie ...
1
vote
1answer
349 views

Partitioning a set of integers into 4 subsets with equal subset sums

Given $n (n \leq 20)$ positive integers and each integer is $\leq 10,000$. Can they be partitioned into $4$ subsets such that sum of the subsets are pairwise equal to each other. I am interested in ...
1
vote
1answer
132 views

Formula to compute number of groups from given points (with overlap)

The problem is kind of easy to understand. Given is some points, say 10 points. (I am using numbering for understanding) 0 1 2 3 4 5 6 7 8 9 Now group these such that the group size is 5 and there ...
5
votes
0answers
82 views

$X^A \equiv B \pmod{2K + 1}$

I recently found this problem which asks you to find an algorithm to find all $X$ such that $X^A \equiv B \pmod{2K + 1}$. Is there something special about the modulus being odd that allows us to ...
2
votes
3answers
194 views

Calculate the number of strings without more than two succeeding occurrences of any character

Problem: Given an arbitrary, finite alphabet $\Sigma$ with $|\Sigma| > 1$, define the language $\qquad L = \{w \in \Sigma^* \mid w \text{ has no subword of the form } aaa, a \in \Sigma\}$. Let ...
2
votes
1answer
163 views

Over an alphabet of $n$ symbols, how many are the strings of length $k$ without consecutive symbols repeated?

From combinatorics, it's known that over an alphabet of $n$ symbols there are $n^k$ different strings of length $k$, of which $\frac{n!}{(n-k)!}$ (assuming $k \le n$) are those without any repeated ...
0
votes
1answer
77 views

Can every even natural number n be written as $\sum^N_{i=1}2^i\cdot f(i)$, where $f(i)$ is either zero or one?

This seems like something that should be trivial but I am having trouble showing it.
4
votes
1answer
201 views

Is there a simple algorithm to generate unlabeled graphs?

While working on some other problem I realized I need to generate (not only enumerate!) all unlabeled graph (or exactly ONE representative from each equivalence class of labeled graphs) with a certain ...
1
vote
2answers
170 views

How do I generate the set of binary strings with elements that are unique under reversal?

What is the most efficient way to generate the set $S$ of unique binary strings of a certain length, $L$, s.t. all strings are unique under the reversal operation? For example, if $L = 2$, the ...
1
vote
1answer
180 views

Optimizing a string to have the shortest possible unique substrings

I would like to construct a length $N$ string over a $k$-letter alphabet, $S$, such that any substring of $P$ sequential characters in $S$ is unique for as small a value of $P$ as possible. To ...
0
votes
2answers
115 views

Finding a sequence that has special properties

let $n \in \mathbb{N}$. Is is possible to find a sequence $S = \{ s_1, \dots, s_{n+k} \}$ ($k \leq n$) with a polynomial algorithm, so that for every pair $(x,y) \in S \times S$, the products $x \cdot ...
4
votes
3answers
221 views

How many cpus needed to check a 100 million digit prime number efficiently?

If I had access to potentially large number of CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the ...

1 2