The tag has no wiki summary.

learn more… | top users | synonyms

15
votes
8answers
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 ...
2
votes
2answers
299 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 ...
3
votes
1answer
273 views

Sequences with integral variances

This is a companion to my earlier question, Sequences with integral means. This new question is, frankly, not as interesting, but it feels necessary to complete the thought. Let $V(n)$ be the ...
21
votes
5answers
854 views

Sequences with integral means

Let $S(n)$ be the sequence whose first element is $n$, and from then onward, the next element is the smallest natural number ${\ge}1$ that ensures that the mean of all the numbers in the sequence is ...
19
votes
1answer
272 views

Hidden points in polygons

Let $h(n)$ be the largest number of mutually invisible points that can be located in a polygon $P$ of $n$ vertices. Two points $x$ and $y$ are mutually invisible if the segment $xy$ contains a point ...
1
vote
1answer
306 views

a conjecture about a specific subset of $S_n$

Let $n>3$ be a positive integer.We denote the symmetric group of $n$ elements by $S_n$ and the identity mapping by $id$. For every $f\in S_n$, $f(1,2,\ldots,n)=(a_1,a_2,\ldots,a_n)$, denote $a_n$ ...
1
vote
1answer
72 views

the “compact good array” in a “good $N^+$-cycle”

We use $N^+$ to denote the set of positive integers.For any finite array $A:(a_1,b_1),...,(a_k,b_k)$,where every $(a_i,b_i)\in N^+\times N^+$,we call $A$ is good if for every $i\in ...
6
votes
3answers
396 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 ...
1
vote
1answer
295 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 ...
1
vote
1answer
107 views

Transform $a\mathbf x+\mathbf b$, then make it $k$-sparse, resulting least modification?

Consider vector $\mathbf x = (x_1,x_2,\cdots,x_n)$, $a$ a scalar, $\mathbf b = (b_0,\cdots,b_0)$ and $k < n$. I want to transform $\mathbf x$ ($\mathbf y = a\mathbf x+\mathbf b$) such that if I ...
3
votes
1answer
110 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
1answer
156 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 ...
0
votes
0answers
142 views

Lattice basis reductions and finding minimal values

While reading several articles about lattice basis reduction I am left with a few questions. For one, I came across this piece of text Let $\alpha$ and $\beta \in \mathbb{R}$. Also let $X>0$ and ...
1
vote
1answer
717 views

Graph Theory and Subgraphs [closed]

Let T = (V , E) be a tree with |V | = n ≥ 2. How many distinct paths are there (as sub graphs) in T? I already have the answer to this question as (n/2). The problem that I'm having is finding ...
3
votes
2answers
174 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
1answer
695 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
1answer
164 views

How to determine the number of a cube within a bigger cube?

Hi all, I have a cube, sized 39 x 13 x 8. I need to find out how many of them can fit in a cube of 100 x 100 x 100. I need to find the highest number possible. Do you know of a way to do that ...
2
votes
1answer
229 views

On solution of a class of discrete-time Lyapunov equation

Hello members, let's consider the following equation $$X=F_{1}XF_{1}^{T}+...+F_{p}XF_{p}^{T}+C$$ where $p$ is an positive integer and $C$ is a known positive semidefinite matrix. If we augment ...
2
votes
1answer
131 views

On solution of a discrete-time equation

Hello, members. I have a problem for the following problem when I derive an optimization algorithm for stochastic singular systems $$S(k+1)=A(k)S(k)A^{T}(k)+R(k)+F(k)S(k+1)F^{T}(k)$$ where ...
1
vote
1answer
320 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
3answers
730 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
0answers
123 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
1answer
459 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
0answers
131 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
1answer
125 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
1answer
146 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
2answers
397 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
1answer
265 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
5answers
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 ...
1
vote
3answers
385 views

How do quantifiers limit scope?

I'm teaching a discrete math class at the high school level and realize that I'm fuzzier on a topic than I should be. In their last problem set, I asked my students to translate "There is a triangle ...
5
votes
0answers
479 views

Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and $b$ are natural numbers. For example, this set of ...
3
votes
2answers
348 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 ...
15
votes
5answers
2k 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 ...
6
votes
1answer
538 views

Calculating a specific joint probability involving sums of binomial distributions

The following might look like a simple problem - but the question has been unanswered for more than a week on math.stackexchange.com, and I have asked quite a few of the Ph.d. students at our ...
8
votes
2answers
481 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
3answers
526 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
0answers
734 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" ...
10
votes
12answers
993 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 ...
9
votes
5answers
513 views

Minimal blocking objects with shadows like a cube

This is a more geometric version of the previous question, "Lattice-cube minimal blocking sets". I will first specialize to $\mathbb{R}^3$, $d=3$. View an $n \times n \times n$ cube $C_3(n)$ as ...
5
votes
2answers
265 views

Lattice-cube minimal blocking sets

Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$. Define a blocking set for a lattice cube to be a set of points in ...
7
votes
6answers
1k views

Discrete Mathematics textbooks for undergraduates

For the first time, I will be teaching a course on Discrete Mathematics for electrical and computer undergraduates students. I intend to focus on practical applications. I would be grateful if ...
5
votes
1answer
686 views

Bounding the entropy of a convolution

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...
-1
votes
1answer
312 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: ...
1
vote
1answer
129 views

expanding the sqare of sum

If there any way to expand the following? $$\left(\sum_{i=1}^nx_i\right)^{\frac{1}{2}}$$ and more generally, a way to expand $$\left(\sum_{i=1}^nx_i\right)^{\frac{p}{q}}$$ where $gcd(p,q) = 1$ ...
3
votes
2answers
346 views

anyone help me with this inequality

I'm have some difficulties in bounding the following inequality: I want to find a c as small as possible s.t. $$\sum_{i=1}^nx_i^4\sum_{i=1}^nx_i^2 -\sum_{i=1}^nx_i^6 \leq ...
0
votes
0answers
85 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 ...
1
vote
1answer
324 views

Simple and general relation between continuant polynomials

Continued fraction $[a_0,a_1,...,a_n]$ may be expressed as quotient of two polynomials of $(a_0,a_1,...,a_n)$, named continuants (see http://en.wikipedia.org/wiki/Continuant_%28mathematics%29 ) ...
12
votes
5answers
1k views

Special arithmetic progressions involving perfect squares

Some time ago the following rather easy problem appeared in an online publication called "Problems in Elementary NT" by Hojoo Lee: Prove that there are infinitely many positive integers $a$, $b$, $c$ ...
8
votes
1answer
369 views

Die-rolling Hamiltonian cycles

Let $R$ be a rectangular region of the integer lattice $\mathbb{Z}^2$, each of whose unit squares is labeled with a number in $\lbrace 1, 2, 3, 4, 5, 6 \rbrace$. Say that such a labeled $R$ is ...
1
vote
0answers
210 views

Trigonometric semialgebraic conditions for two floors to be unequal [edited]

EDIT: Since posting my original question I have simplified the problem to finding a sufficient condition for $\lfloor \frac{a}{\phi}\rfloor \neq \lfloor \frac{b}{\phi}\rfloor$ which is trigonometric ...