# Tagged Questions

**0**

votes

**4**answers

108 views

### about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...

**0**

votes

**0**answers

69 views

### Rank function and closure operator for a set system

I would like to trace the concepts "rank function" and "closure operator" back to some structures as primitive as possible.
For a set system $(E,F)$ which is an independence system or a greedoid, I ...

**2**

votes

**1**answer

106 views

### Family of sets with unique subsets

I am given a set $M\subseteq\{1,\dots,n\},\,|M|=m$ and a famliy of $k$-sets ($k<m$) $\mathcal{U}=\{U_1,\dots,U_p\},\,U_{i}\subset M$. For this family, I would like to check one of the following ...

**14**

votes

**7**answers

1k views

### Two questions from combinatorics on words

Question 1. Assume that an infinite word $u\in\{0,1\}^{\mathbb Z}$ is not balanced. Is it true that there exists a finite 0-1 word $w$ such that $0w01w1$ or $1w10w0$ is a factor of $u$? Is it true ...

**3**

votes

**2**answers

227 views

### Cardinality of intersection of a random subset with a fixed subset

How can I simply prove the following fact:
Let $A := \{1, \dots n \}$ and $B := \{1, \dots, \lfloor \frac{n}{4} \rfloor \}$. Let $d \in (0,1)$ and let $R$ be a randomly choosen (with uniform ...

**2**

votes

**2**answers

242 views

### Computing the lexicographic indices of integer partition

If we order all the partitions of a integer in a lexicographic order, how can we compute the position of each partition in this order without having to explicitly list all other partitions that ...

**0**

votes

**1**answer

201 views

### Indexing combinations with repetition

Let $\Sigma$ be a finite set of symbols with total order. Let $C_k$ be the set of all $k$-multiset (unordered collection of $k$ elements from $S$, with repetition allowed). We can order all the ...

**3**

votes

**1**answer

102 views

### Obtaining each set (hyperedge) in a set system (hypergraph) as a union of sets in a smaller set sytem

Let $V$ be a set and $E$ a set of subsets of $V$. I'd like to know the proper terminology for the following concept.
Let me call it "generator". A generator is a set $F$ of subsets of $V$ such that ...

**3**

votes

**1**answer

122 views

### Reference for partial Hadamard matrices

Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...

**3**

votes

**2**answers

173 views

### Question on weights and minimal degree

Edit: question has been changed from 'lexicographic' (cf. "D K"'s answer below) to 'degree' minimality.
Let $x_1,x_2,x_3$ be indeterminates. Fix an integer $k> 3$. Consider the set $M$ of all ...

**6**

votes

**1**answer

551 views

### Integer solution to special system of linear equations

This problem appear in my research, but I am unable to solve it.
There should be an easy argument, but I have not yet found it.
Informal version
An integer $k\geq 2$ is fixed.
We are given a matrix ...

**1**

vote

**1**answer

249 views

### Distance between vertices in a vertex transitive graphs. [closed]

Can anybody help me in finding out the distances between vertices in a vertex transitive graphs. Is there any specific formula to calculate distance between vertices in this graph. Thanks for your ...

**6**

votes

**3**answers

526 views

### References on techniques for solving equations with discontinuous functions such as floor and ceiling?

Here I describe the sort of reference I'm after with a motivating example. I am not seeking solutions to my equations on this forum; I'm quite happy to do that myself. Rather, I'm asking for some good ...

**3**

votes

**0**answers

121 views

### Citation for subset complement result

Let $S=\lbrace s_1,\ldots,s_n \rbrace \subset \lbrace1,\ldots,2n\rbrace$. Consider two operations on $S$: the complement $C(S)=\lbrace 1,\ldots,2n \rbrace \setminus S$ and a reflection* ...

**13**

votes

**1**answer

441 views

### Does erosion mix faster than a riffle shuffle?

It is a famous result of Aldous and Diaconis1 that
seven shuffles are necessary and suffice to approximately
randomize 52 cards.2
Here the shuffles are the standard riffle shuffle, where the ...

**0**

votes

**0**answers

127 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$ ...

**0**

votes

**1**answer

116 views

### expected size of unbalanced biclique in random bipartite graph

I am discovering random graph and I am trying to prove the following result. This is a follow-up on a previous question of mine
what's an upper bound on the size of the largest biclique in random ...

**3**

votes

**1**answer

134 views

### what's an upper bound on the size of the largest biclique in random bipartite graph?

I am not an expert in random graph but I need the following result and I couldn't find any reference on this.
Let $G(X \cup Y,p)$ be a random bipartite graph where the set of edges is $X \cup Y$, $X$ ...

**4**

votes

**2**answers

313 views

### Looking for construction related to Erdos-Szekeres theorem

The Erdos-Szekeres theorem says that every $n$-permutation $p(1), p(2), \ldots, p(n)$ has either an increasing run or a decreasing run of length $\sqrt n$, where an increasing run is
$p(i_1) < ...

**4**

votes

**1**answer

193 views

### Best upper bound on rate for q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch which states that the rate $R(\delta)$ corresponding to ...

**24**

votes

**5**answers

2k views

### How many binary operations are associative?

Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each
be ...

**3**

votes

**2**answers

344 views

### The cycle structure of twisted wires, connected

Suppose you have $n$ (blue) wires linearly arrayed at junction box $A$,
connected to a remote junction box $B$, where the wires are now
arrayed
along a line in a randomly permuted order, i.e.,
each ...

**12**

votes

**4**answers

1k views

### Has any attempt been made to classify finite groupoids?

I recently stumbled upon the Mathieu groupoid and I found them fascinating.
It appears as a subset of $S_{13}$ which is not closed under multiplication, but it turns out to be a groupoid with 13 ...

**8**

votes

**2**answers

464 views

### Three half circles on the plane may not meet nicely

Let $H$ denote the union of the northen hemisphere of the unit circle $S^{1}$ with the interval $[-1,1]$ on the $x$-axis. That is, $H=\{(x,\sqrt{1-x^{2}}):-1\le x\le 1\}\cup\{(x,0):-1\le x\le 1\}$
...

**6**

votes

**3**answers

483 views

### Cylinders dividing $\mathbb{R}^{3}$

Consider $n$ affine copies of a compact cylinder, say $S^{1}\times [-3,3]$ with top and botom, sitting inside $\mathbb{R}^{3}$.
For each $n$ we may ask ourselves how to arrange the $n$ cylinders so ...

**5**

votes

**0**answers

645 views

### On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...

**8**

votes

**12**answers

949 views

### Continuous notions with compelling discrete analogues

Following up on the previous MO question "Are there any important mathematical concepts without discrete analogue?", I'd like to ask the opposite: what are examples of notions in math that were not ...

**-1**

votes

**1**answer

298 views

### Number of blocks in a t-(v,k,l) design with empty intersection with a given set U [closed]

Question
Given a $t-(v,k,\lambda)$ design $(X,\mathcal{B})$ and a set $U\subset X$ with $|U|=u\leq t$, what is the number of blocks $B\in\mathcal{B}$ such that $B\cap U=\emptyset$?
The answer is: ...

**3**

votes

**0**answers

100 views

### Are there existing resources on modular-esque recurrence relations?

Does anyone know where I would be able to get information on analyzing a class of polynomial recurrence relations of a form like this?
$\begin{align*}
f_{n,k}(x) & ...

**2**

votes

**3**answers

581 views

### how to cover a set in a grid with as few rectangles as possible

In calculus, when estimating a area of a set in a 2-dimensional space, we use rectangles to approximate. To get sufficient precision, how many rectangles are needed if the shape of the set is close ...

**2**

votes

**1**answer

611 views

### Decomposition of a complete graph into maximal matching subgraphs

Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge?
For example, consider $K_4$ with vertices ...

**2**

votes

**4**answers

434 views

### Statistical computation in matrix. Rows before columns? riddle..

First I'll phrase the question as a riddle, and than as a general math problem.
We have 12 lettered vases $(A,B,...,L)$, in each vase there are 30 numbered balls (1-30). In each ball there is some ...

**3**

votes

**0**answers

668 views

### Method for variable substitution in multiple summation

I want to ask: is there any general method for variable substitution in multiple summation?
For example in the following equation a new variable $\lambda=n+m-2\mu$ is introduced to transform the LHS ...

**8**

votes

**2**answers

995 views

### palindromic subsequences

I'd like any insight or references to the following two conjectures (see the glossary below for definitions):
Conjecture 1: For any string $x$, there exists a longest common subsequence of $x$ and ...

**0**

votes

**0**answers

401 views

### Covering a set of intervals

EDIT: I posted this question to http://cstheory.stackexchange.com/questions/4358/covering-a-set-of-intervals , which looks like a more appropriate venue for such a question.
Hello,
I'm trying to ...

**7**

votes

**9**answers

429 views

### What are some early examples of creation of lists / catalogues of (particularly) combinatorial objects?

A lot of effort in discrete maths / combinatorics is expended in the construction of lists, catalogues or census [sic] of combinatorial objects such as groups, graphs, designs etc. These catalogues ...

**7**

votes

**3**answers

952 views

### How to characterize a Self-avoiding path.

I cannot find any answer to that apparently simple problem :
On a square lattice, a path is given by a sequence of relative moves in {"move forward", "turn right" and "turn left"}.
Is there a rule ...