# Tagged Questions

**2**

votes

**0**answers

42 views

### Euclidean minimum spanning trees intersecting each unit square

The recent question "Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell" can be restated in terms of "minimum spanning trees intersecting each (closed) lattice square of an ...

**-2**

votes

**1**answer

55 views

### How does deletion-contraction affect chromatic number? Can it increase chromatic number? [on hold]

Question: In graph theory, contracting an edge or deleting an edge are basic operations in many topics such as graph minors or Wagner's theorem on planar graphs. And I'm interested in how these ...

**5**

votes

**0**answers

104 views

### Representing one diagonal of Pascal's triangle using special sums coming from a different diagonal

Let $m, n$ be any fixed natural numbers. Is it true that infinitely many elements of the sequence $\binom{m+k}{m}_{k=1,2,3,...}$ ( as well as of the sequence ...

**10**

votes

**0**answers

145 views

### How long can a cycle of antichains in a finite partial order be?

Suppose that $X$ is a finite partially ordered set. Then a subset $A\subseteq X$ is said to be an antichain if there do not exist elements $a,b\in A$ with $a<b$. Let $\mathcal{A}_{X}$ be the set of ...

**10**

votes

**1**answer

234 views

### Graph $G$ with $\omega(G) = 2$ but $\chi(G) \geq \aleph_0$

Given an infinite cardinal $\kappa$, is there a graph $G$ that has no clique consisting of more than 2 points, but $\chi(G) = \kappa$?

**5**

votes

**3**answers

408 views

### Permutations with all cycles odd length and permutations with all cycles even length

If $n$ is even, then the number of permutations of $n$ in which all cycles have odd length equals the number of permutations of $n$ in which all cycles have even length. This fact is easily proved, ...

**0**

votes

**0**answers

51 views

### Sum of weighted permutations over natural numbers [on hold]

If we consider the sum $\sum\limits_{i=1}^n i\sigma(i)$ where $\sigma$ is a permutation of the first $n$ natural numbers, then this sum has a few interesting properties for various values of $n$. My ...

**10**

votes

**0**answers

150 views

### Two conjectures about zero inner products and dissociated sets

The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...

**0**

votes

**0**answers

17 views

### Binary strings and one-to-one correspondence [on hold]

Assume T be the set of binary strings of length 30 with 10 1’s and 20 0’s. Let X be the set of the first 30 positive integers {1,2,3,…,30}. Let Y be the set of all subsets of X containing 10 numbers. ...

**2**

votes

**0**answers

58 views

### A basic minimization problem over finite fields

Let $p$ be a prime, and suppose we are given $n$ values mod $p$: $a_1,...,a_n\in Z_p$. Is there a fast algorithm for finding $\alpha\in Z_p$ which minimizes the value $\max_i (\alpha\cdot a_i$ mod ...

**1**

vote

**1**answer

67 views

### Coxeter Isometry groups whose center has torsion

I'm looking for examples of Riemannian manifolds M of dimension $\geq 2$ such that the isometry group $Isom(M)$ contains as subgroup a finite Coxeter group $G$ such that $Tor(Z(G))$, the torsion group ...

**12**

votes

**2**answers

512 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 ...

**0**

votes

**0**answers

66 views

### Counting ways to Arrange Variable Sized Objects into Fixed Number of Spaces [on hold]

I scoured the web for a generalized notion of balls and bin that encompasses the needs of my questions. Essentially, I'm looking for a way count the number of ways to fit i different types of objects, ...

**9**

votes

**0**answers

131 views

### No limit shape for random Young diagrams under z-measure?

In their paper Random partitions and the Gamma kernel (Advances in Mathematics 194 (2005) 141–202), Borodin and Olshanski state that:
An important difference between the Plancherel measures and ...

**3**

votes

**1**answer

307 views

### Is this version of van der Waerden's Theorem consistent with ZFC?

One way to phrase van der Waerden's Theorem is:
For every finite coloring of $\mathbb N$ and every finite $F \subseteq \mathbb N$, there exist $a,b \in \mathbb N$ such that $a + b \cdot F$ is ...

**10**

votes

**2**answers

492 views

### Does van der Waerden's Theorem hold for $\omega_1$?

One way to phrase van der Waerden's Theorem is:
For every finite coloring of $\mathbb N$ and every finite $F \subseteq \mathbb N$, there exist $a,b \in \mathbb N$ such that $a + b \cdot F$ is ...

**1**

vote

**1**answer

136 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

**0**answers

47 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

**0**answers

86 views

### Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell

Given an $n \times n$ grid with unit grid cells, and one point from the interior
of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound ...

**0**

votes

**0**answers

31 views

### the number of $n\times n$ matrices of 0's and 1's such that every row and column has three 1's [migrated]

In the Example 1.1.3 of Stanley's book Enumerative Combinatorics Vol 1 (2nd edition), an explicit formula for the number of $n\times n$ matrices of 0's and 1's such that every row and column has three ...

**4**

votes

**1**answer

218 views

### Strings with no long runs from proper subalphabets

Let $R_{n,k,b}$ be the number of $b$-ary strings of length $n$ that contain some run of length at least $k$ from some $(b-1)$-ary subalphabet. Let $N_{n,k,b}=b^n-R_{n,k,b}$ be the size of the ...

**5**

votes

**1**answer

80 views

### Sum identities with immanants

For $\chi$ being an irreducible character of the symmetric group $S_n$ and being $M$ a complex $n\times n$-matrix, I would like to show
$$
\sum_{\sigma, \rho \in S_n} \overline{\chi(\sigma)} ...

**2**

votes

**0**answers

34 views

### Uniform generation of Symmetric Plane Partitons

In the conclusion of An Involution Principle-Free Proof of Stanley's Hook-Content Formula Krattenthaler notes that the techniques of the paper might be useful for finding bijective proofs of the ...

**1**

vote

**1**answer

193 views

### A Bernstein-like Combinatorial Sum

Do sums of the "convoluted Bernstein" form
$$
\sum_{j=1}^m {m\choose j} q^j (1-q)^{m-j} {n \choose k} \left(\frac j m\right)^k \left(1- \frac j m\right)^{n-k}
$$
admit closed forms? My attempts to ...

**6**

votes

**0**answers

251 views

### What can I further assume about the speeds of runners of Lonely Runner Conjecture WLOG?

Lonely Runner Conjecture is the following problem, and the conjecture was proven to be true for $k\leq 7$:
Let $V$ be the set of $k$ distinct positive integers with $v_1<v_2<...<v_k$ ...

**5**

votes

**1**answer

318 views

### How many random matrices does it take to generate a matrix algebra?

Let $\mathbb{F}$ be a finite field.
Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra.
Is there a good bound on the number $k$ of random elements $a_1,\dots,a_k\in A$
that one needs to take ...

**1**

vote

**0**answers

35 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 ...

**22**

votes

**1**answer

1k views

### Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946

I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph ...

**5**

votes

**1**answer

237 views

### A claim from “Graph minors - a survey” by Robertson and Seymour

Can someone give me a proof sketch for this:
Let $\mathscr{P}_n$ be the set of all graphs which do not contain a path on $n$ vertices as a subgraph. Define the type of a graph inductively as: the type ...

**31**

votes

**2**answers

862 views

### Random sequence of integers in $\{1, 2, \dots, n \}$ which is “everywhere probably increasing” - how long can it be?

Let $D=(d_1,d_2,\dots,d_k)$ be a sequence of correlated random variables. $D$ is "everywhere $r$-probably increasing" if the event $d_j > d_i$ has probability $\geq r$ for all $j > i$.
Fix $r ...

**4**

votes

**5**answers

271 views

### Table of planar connected graphs

For the other day I need to use the table of planar connected graph with few vertex. In the wolfram's mathworld , they listed only the graph with $4$ vertex.
Does anyone knows webpages or pdf on the ...

**1**

vote

**1**answer

166 views

### Singular homology of the zero loci of polynomials

I am very sorry but apparently I am really weak in cohomology flavored questions. I try to reformulate my problem in a very simple and hopefully clear way. This question is related with a problem in ...

**1**

vote

**0**answers

80 views

### Are back edges mandatory in Ford Fulkerson algorithm?

Consider the algorithm of Ford Fulkerson where, for each iteration, you add flow along a path equal to the maximum residual capacity along this path.
Does it exist, for every network, a choice of ...

**9**

votes

**0**answers

80 views

### Complexity of planar scissor congruence

Two (not necessarily convex) poygons of equal area are scissor-congruent, i.e. both can be cut along a finite number of straight lines or segments into isometric pieces.
What can be said about the ...

**2**

votes

**1**answer

135 views

### Linear independence of +/- 1 strings/vectors II

Let $V=\left\{-1,1\right\}^{n}$. Consider three vectors $v_1,v_2,v_3\in V$. I would like to know whether these vectors are linearly independent over $\mathbb{Z}$. To be more precise - I need a ...

**3**

votes

**2**answers

221 views

### Isoperimetric inequality on the Hamming cube

Suppose $X \subseteq \lbrace 0 , 1 \rbrace ^{m}$ such that $|X| \geq 2^{0.8m}$, and $m \geq 2$, then prove that there exists $x,y \in X$ with $||x - y||_{1} \geq m/2$.
My approach to prove this was ...

**7**

votes

**1**answer

699 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

**1**answer

117 views

### Linear independence of +/- 1 strings/vectors

Let $V=\left\{-1,1\right\}^{n}$. Consider three vectors $v_1,v_2,v_3\in V$. I would like to know whether these vectors are linearly independent over $\mathbb{Z}$. To be more precise - I need a ...

**3**

votes

**1**answer

120 views

### Simultaneous approximation by rationals with relatively prime numerators

The following seems hard to me (or perhaps just not true), but perhaps I am mistaken. It is known that given irrational numbers $x_1$ and $x_2$, there are infinitely many simultaneous rational ...

**1**

vote

**1**answer

88 views

### Combinatorial polynomials from general diagram fillings?

There is a plethora of polynomials defined on partition shaped Young diagrams, (Schur, Jack, Grothendieck,...), and skew Young diagrams.
There are also composition shaped diagrams that are responsible ...

**1**

vote

**1**answer

80 views

### Does every connected vertex transitive graph on $n$ vertices (except for $C_n$) have minimum feedback vertex set of size $\Omega(n)$?

Feedback vertex set is a set of vertices whose removal leaves an acyclic graph.
It is known that every vertex transitive graph on $n$ vertices has minimum vertex cover of size $\Omega(n)$. It is also ...

**1**

vote

**4**answers

583 views

### Distribution of composite numbers

I have moved this question to math.stackexchange.com. People who are interested in this question can discuss at :http://math.stackexchange.com/questions/1272431/distribution-of-composite-numbers
...

**5**

votes

**1**answer

209 views

### Dimension of the span of all partial derivatives of a given symmetric polynomial $f$ and the polynomial $E(f)$

I need some help on the problem below.
Let $d\geq 4$ and $f$ a symmetric polynomial, homogeneous of degree $d$, in $n$ variables $x_1,\dots,x_n$, with real coefficients. We set
$$ ...

**3**

votes

**0**answers

264 views

### How is $ \sum_{x \in X(\mathbb{F}_q)} \dots $ a generalization of cardinality?

This quarter Maxim Kontsevich is offering a course on exponential integral. There is not much in the way of notes, but is one page with mysterious comments.
Let $X$ be an algebraic variety over ...

**0**

votes

**0**answers

39 views

### Uncountability of the set of subsets of $\mathbb N$ [migrated]

Denote by $\mathbb{N}$ the set of natural numbers and by $2^{\mathbb N}$ the set of all subsets of $\mathbb N$. Let $E$ be some subset of $2^{\mathbb N}$ such that for every pair of elements in $E$, ...

**3**

votes

**0**answers

88 views

### scalar multiple of Young symmetrizer

The following is a lemma from Fulton and Harris' book -Representation theory,a first course (page 53):
Lemma: For all $x\in \mathbb{C}\mathfrak{S}_r$, $c_{\lambda}\cdot x\cdot c_{\lambda}= scalar ...

**4**

votes

**2**answers

165 views

### Vertex expansion of the Hamming graph

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$. The vertex expansion of $G$ is
$$ \min_{S\subseteq V, |S|\le |V|/2} \left\{ \frac{|N(S)|}{|S|} ...

**10**

votes

**1**answer

303 views

### Equation with $q$-binomial coefficients

Let $d\ge2$, and let $q$ be a power of a prime. As usual, define $N(d,q)=\sum_{k=0}^d{d\choose k}_q$.
I wonder if there are $d$ and $q$ as above such that $1+N(d,q)=q^{d+1}$.
(If the answer is ...

**1**

vote

**1**answer

164 views

### Random graphs with boundary in a game (Tsuro)

Suppose we have an $n \times n$ board and we have $n^2 - 1$ square tiles. These tiles consist of a 8 vertices, two on each edge, and every vertex is connected to precisely one other vertex. These ...

**2**

votes

**0**answers

133 views

### Largest Fourier coefficient of sparse boolean function

Consider a Boolean function $f: GF(2)^n \rightarrow \{0, 1 \}$. I would like to show that if $f$ is sparse, i.e. $\sum f(i) \leq t$, then $f$ must have a large Fourier coefficient. (A Fourier ...