The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
39 views

3D matching modification

Consider all instances of the $3D$ matching problem where all edges that intersect-intersect in "exactly" one vertex (1-edge intersection). Consider all instances of the $3D$ matching problem where ...
3
votes
0answers
98 views

“Standard” notation for symmetric functions?

Here is what I encountered in the paper "The Optimal Lattice Quantizer in Three dimensions" by Barnes and Sloane. Here is the setup: Let $\Lambda$ be a lattice in $\mathbb{R}^3$. Around each ...
3
votes
1answer
104 views

Do random triangulation edge-flips maintain randomness?

Let $S$ be a fixed set of $n$ points in the plane in general position. Let $T$ be a triangulation of $S$, (somehow) selected uniformly at random from all triangulations of $S$. (There are an ...
3
votes
1answer
55 views

Choosing k pairs l distance apart from n numbers

I need to choose $k$ pairs of numbers out of first $n$ natural numbers such that the elements in each pair are $l$ distance apart. For example, if $n = 10, k = 3$ and $l = 2$, $\{(1,3),(4,6),(7,9)\}$ ...
-4
votes
1answer
128 views

What exactly is wrong with this statement (Lucas-Penrose fallacy)? [closed]

Statement "For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method." ...
11
votes
2answers
302 views

The most number of points that realize only $k$ distinct distances

For $k \ge 1$, let $f_d(k)$ be the largest possible number of points $p_i$ in $\mathbb{R}^d$ that determine at most $k$ distinct (Euclidean) distances, $\|p_i-p_j\|$. Example. For points in the plane ...
13
votes
2answers
565 views

Bit String Bijection

I am searching for a bijection between two types of bit strings (strings of 0's and 1's) both of even length (2n). The restriction on the first type of bit string is that they must have the same ...
1
vote
1answer
148 views

Enumerating Lattice points

Let $A \in \mathbb{R}^{d\times d}$ be an invertible matrix. Consider the set $$P_d := A\mathbb{Z}^d = \{A x| x \in \mathbb{Z}^d \} \subset \mathbb{R}^d$$. and $$ Q_d := [-1,1]^d.$$ I am interest in ...
1
vote
0answers
55 views

Presentation of the Rybnikov matroid

In this well celebrated work Gregory Rybnikov exhibit an example of two arrangements with the same underlying matroid, but with fundamental groups which are not isomorphic. This is a key ...
5
votes
2answers
259 views

Minimum of squared sum minus sum of squares

I know that $$ \min_{\|x\|_2=1=\|y\|_2} \left(\sum_{k=1}^nx_ky_k\right)^2-\sum_{k=1}^nx_k^2y_k^2 \geq -1/2 $$ with equality whenever $|x_k|=\frac{1}{\sqrt{2}}=|y_k|$ for two coordinates. I'm ...
1
vote
0answers
27 views

Estimates for derivatives of a positive discrete harmonic function

There is the following estimation (Duffin, Discrete potential theory, Theorem 5): Let $f$ be a discrete harmonic function in a sphere of radius $R$ with the center $p$, all in $\mathbb Z^3$. Then, if ...
2
votes
0answers
39 views

A weaker version of Randell Isotopy Theorem

I am studying a problem in hyperplane arrangement theory related to the homotopy type of the complement manifold of a certain class of hyperplane arrangements. In a well celebrated paper Richard ...
7
votes
1answer
764 views

A Question about Palindromic Numbers and System of Arithmetic Progression

Based from Harminc and Sotak's result, www.fq.math.ca/Scanned/36-3/harminc.pdf We know that under certain condition, an arithmetic progression can contain an infinitely many palindromes. My question ...
1
vote
0answers
30 views

Simplifying closed form for Meta Operator

I was consider the set of linear operators: $$O_{a,k} = \frac{f(ax^k) - f(x)}{ax^k - x} $$' Particularly I am looking for the closed forms of the eigenfunctions of this operator, that is the ...
8
votes
7answers
563 views

Finite-space dynamical systems

This question is quite open-ended, but I will formulate several sub-questions that I'll try to make precise. It is about finite-state dynamical system: start with a finite set $X$, with say $n$ ...
19
votes
5answers
810 views

Three-halves-free words (analogous to square-free)

A square-free word is a string of symbols (a "word") that avoids the pattern $XX$, where $X$ is any consecutive sequence of symbols in the string. For alphabets of two symbols, the longest square-free ...
2
votes
1answer
110 views

On a problem about $GF(2)^n$

For $A\subseteq {\mathbb F}_2^n$ let $$ Q(A)=\{\alpha+\beta\mid \alpha,\beta \in A,\ \alpha\neq\beta \}. $$ I want to prove or disprove that if $|A|=2^k+1$ for some integer $k$, then $$ ...
0
votes
0answers
19 views

On the stability analysis of a discrete difference system with multiplicative noise

If we assume that \begin{equation*} \rho \{\phi \otimes \phi+\psi \otimes \psi\}<1 \end{equation*} where $\rho$ denotes the spectral radius, then can we verify the following inequality holds ...
5
votes
1answer
308 views

A set of integers whose factorial can be written as a product of two factorials

I am trying to collect informations concerning the set $$\mathcal{A}=\left\{n\in\mathbb{N} \mid (\exists k,l\in\{2,3,\dots,n-2\})(n!=k!l!)\right\}.$$ It seems not much is known about the set ...
9
votes
1answer
151 views

Optimal shape for stabbing balls in $\mathbb{R}^3$

I have radius $r < \frac{1}{2}$ congruent balls with centers randomly distributed uniformly within a region, say, within a unit-radius sphere $S$. I shoot a ray/path through $S$, hoping to ...
3
votes
1answer
268 views

Number of semi-standard tableau

What is the number of semi-standard tableau (weakly increasing on rows and strictly increasing on columns) for the partition $2n=n+n$ with entries $\{1,2, \cdots ,n\}$ such that each $i$ appears ...
0
votes
1answer
157 views

Number of squares in a grid under certain conditions

Consider an $(n+1)\times (n+1)$ grid of lattice points in the plane. $A(n):$ # of squares with vertices on the grid. It's relatively well-known that $A(n)=\frac{n(n+1)^2(n+2)}{12}$. Now, $A(n) = ...
2
votes
1answer
88 views

Complex lines arrangements from a given wiring diagram

I'm working on some presentation of the fundamental group of the complement of a complex lines arrangement in $\mathbb{C}^{2}.$ In particular, in Arvola's article "The fundamental group of the ...
3
votes
1answer
138 views

Braid wiring diagrams and matroids

recently I started reading some articles about the presentation of the fundamental group of lines arrangements in $\mathbb{C}^{2}$ via Wiring diagrams. I also found some relation with matroid theory. ...
2
votes
1answer
217 views

Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets: Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...
4
votes
1answer
228 views

Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$ such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...
13
votes
1answer
382 views

Minimal “sumset basis” in the discrete linear space $\mathbb F_2^n$

For a set $C\subseteq \mathbb F_2^n$, let $2C=C+C:=\{\alpha+\beta\colon \alpha,\beta\in C\}$. I want to find $C$ of the smallest possible size such that $2C=\mathbb F_2^n$. Let $m(n)$ be the size of a ...
7
votes
1answer
249 views

Number of median graphs?

What is the number of $n$-vertex median graphs? These graphs generalize hypercubes and trees, and have many applications. It seems unlikely that a closed form expression is known, so I would also be ...
2
votes
1answer
145 views

A perfect $(n,k)$ shuffle function

Suppose you have a deck of $n$ cards; e.g., $n{=}12$: $$ (1,2,3,4,5,6,7,8,9,10,11,12) \;. $$ Cut the deck into $k$ equal-sized pieces, where $k|n$; e.g., for $k{=}4$, the $12$ cards are partitioned ...
6
votes
0answers
90 views

Checking if a multiplication table represents a group [duplicate]

Given an $n \times n$ multiplication table, can one check if it represents a group in $o(n^3)$ time? All properties can be checked by mindless try-all possibilities loops: Whether there is an ...
7
votes
2answers
420 views

A continuous function for defining unique values to a 1024x1024 image with a 24 bit 3 color channel image

I need to generate a color map which I am not sure exist. I have a 1024x1024 image which would contain 2^20 pixels. I have 3 color channels which each have 8 bits which would leave us with 2^24 ...
6
votes
1answer
274 views

A variation on Bulgarian solitare

It appears that a variation on Bulgarian solitare has a fixed point regardless of the starting $n$. For example, let $n=69$, and consider this partition: $$ (8,8,7,7,5,5,5,5,5,4,3,3,2,2) $$ In ...
0
votes
1answer
132 views

Probability of k overlapping subsets in N trials

Ok, here is what I am attempting to find an answer to: I draw M uniformly random subsets of size K from the set of numbers $\Omega=\{1, \dots, N\}$ (where uniformly random means that each unique ...
1
vote
0answers
68 views

Cross-correlation of two functions which are not fixed

I am trying to cross-correlate two functions, but one of which is changing each 'step' of the cross-correlation. I want to cross-correlate T(f) and ...
0
votes
4answers
177 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 ...
17
votes
1answer
497 views

Longest of random worm-like paths in $\mathbb{Z}^2$

Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$, with coordinates $\equiv 2 \bmod 3$, we place, with equal probability, one of these six patterns:       The result ...
34
votes
6answers
3k views

Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
1
vote
0answers
38 views

Find a common expression (parameterized by y = 1/2, 1 and 2) uniting three (rational) polynomials in k [closed]

I am seeking a common "simple" expression (preferably/presumably a sum of products of linear factors, or sum of products of low-degree factors) uniting the three polynomials (parameterized by ...
2
votes
1answer
157 views

Calculate the discrete set of points B which are in the convex hull of the set of points A

This problem is likely best described with the following picture: Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
1
vote
1answer
182 views

A square-squareroot integer race sequence involving primes

I wonder what is the expected behavior of this process? Let $f^2_{\mathrm{next}}(n) =$ the next prime after $n^2$. $g_{\mathrm{sqrt}}(n) = \lfloor \sqrt{n} \rfloor$. Now iterate as ...
11
votes
0answers
302 views

Generating random finite groups

I would like a method to efficiently generate a random finite group of a given order $n$. If there are $g(n)$ non-isomorphic groups of order $n$, ideally each group would occur with probability ...
2
votes
1answer
545 views

Probability generating function zero implies random variable is infinite

Let $V$ be a random variable supported on the nonnegative integers (including $\infty$) and $f(x) = \mathbf E x^V$ be the probability generating function. In our model $V$ is the number of visits to ...
8
votes
1answer
358 views

Is this a new formula? $\Delta^d x^n/d! = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$

$$\frac{\Delta^d x^n}{d!} = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$$ Where $x$, $n$ and $d$ are non-negative integers, $\Delta^d$ is the $d$-th difference with respect to ...
2
votes
1answer
113 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 ...
13
votes
1answer
304 views

Is there an unambiguous CFL whose complement is not context-free?

I'm doing a little bit of research about context-free languages. A question that's popped up is whether or not there exists an unambiguous context-free language whose complement is not a context-free ...
14
votes
1answer
672 views

Is every graph the center of some other graph?

The center of a graph $G$ is the set of vertices that minimize the largest distance to vertices in $G$, e.g., in the graph below, that radius is $4$:           Define the ...
7
votes
2answers
292 views

Iteration of a 2D map involving absolute value: phase transition?

I was looking at this map: $f(x,y) \mapsto (|x-y|,x)$, starting from some point with coordinates $(x,y) \in [0,1]^2$, and iterating: $(x,y),\, f(x,y), \, f^2(x,y), \,f^3(x,y), \ldots$. It displays ...
2
votes
1answer
117 views

Subdividing toward a unit distance graph in the plane

I just want to ask, what is the significance of subdividing a graph toward a unit distance graph? I have seen several studies of it but I cannot find what its importance. I mean, like the study of ...
6
votes
0answers
735 views

How many 2L-bit numbers are the product of two L-bit numbers?

If I multiply two integers $x, y $ in $[0,2^L)$, I get an integer in $[0,2^{2L})$. Clearly, this map from $[0,2^L) \times [0,2^L) \to [0,2^{2L})$ is not bijective. I am interested in the size of ...
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 ...