# Tagged Questions

**2**

votes

**0**answers

49 views

### A circulant coin weighing puzzle

We are given $n$ coins, some of which are "real" and weigh $1$ and some of which are "fake" and weigh $0$. We have one "spring scale" which can weigh any subset of the coins. A classic question asks ...

**9**

votes

**3**answers

251 views

### Models for graphs representing real-life networks

I am interested in basic models of graphs (stochastic or deterministic) that are offered for real-life networks (like social networks, the Internet, neuron networks).
I will be thankful for answers ...

**5**

votes

**1**answer

89 views

### Iterated sumset inequalities in semigroups

This question is motivated by the following well-known theorems:
Thm (Plünnecke): If $A$ is a finite nonempty subset of an abelian group, then for every $n$ we have $|A^n| \le ...

**3**

votes

**0**answers

48 views

### Sparsifiers for 3-term arithmetic progressions

Let $G$ be a finite abelian group of odd order, let $D\subseteq G$, and $\epsilon \in (0,1)$.
For $S\subseteq G$ define
$$
\Lambda(S) = \frac{1}{|S||G|} \sum_{s\in S}\sum_{g\in G} ...

**0**

votes

**1**answer

90 views

### Moment maps and flat degenerations of toric varieties

We have a flat family of projective varieties with a torus $T$ action, over $\mathbb{A}^1$.
How do the moment map images of the fibers change when we pass from the generic fiber to the special fiber ...

**5**

votes

**1**answer

338 views

### Repertory of the different sorts of operads

Many different types of operads have emerged in recent years (symmetric, shuffle, cyclic, anticyclic, coloured, etc.).
I would like, for any of these, list the following data:
Description of the ...

**9**

votes

**1**answer

189 views

### One identity in Lie algebras

Let $L$ be a (non-restricted) Lie algebra over a field of prime characteristic $p,$ $UL$ be its universal enveloping algebra and $a_1,\dots, a_p \in L$ (the number of elements is equal to the ...

**9**

votes

**2**answers

306 views

### Sumsets and dilates: does $|A+\lambda A|<|A+A|$ ever hold?

The following problem is somehow hidden in this recently asked question, but I believe that it deserves to be asked explicitly.
Is it true that for any finite set $A$ of real numbers, and any real ...

**10**

votes

**1**answer

113 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

**3**answers

533 views

### Stanley-Reisner ring of a simplicial complex is a functor?

Let $K$ bea field and $[n]=\{1,\ldots,n\}$ and $K[x]=K[x_1,\ldots,x_n]$. For $\sigma=\{i_1,\ldots,i_k\}\subseteq [n]$, denote $x_\sigma=x_{i_1}\cdots x_{i_k}=\prod_{i\in\sigma}x_i\in K[x]$. Let ...

**6**

votes

**3**answers

653 views

### Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle - is there a combinatorial explanation?

This question arose from an answer to my recent question How many traces are there on Temperley-Lieb, Fuss-Catalan, Iwahori-Hecke, Birman-Wenzl-Murakami-Kauffman, ... algebras?
What I need from that ...

**1**

vote

**1**answer

160 views

### Ask the name of a combinatorial theorem

It is a classical theorem. For given integer $n \ge 1$, among ${n\choose{n/2}} = 2^{(1-o(1)n)}$ strings in the cube $\{0, 1\}^n$ with weights $n/2$, i.e., $n/2$ indices are 1, there are at least ...

**7**

votes

**1**answer

98 views

### Does the Tutte polynomial of iterated cone graphs detect isomorphism?

Let $T_G(x,y)$ denote the Tutte polynomial of a graph. Of course we may have $T_G(x,y) = T_H(x,y)$ for $G$ and $H$ non-isomorphic graphs.
Now let $c(G)$ denote the cone graph of $G$, i.e., the graph ...

**13**

votes

**0**answers

284 views

+50

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

**1**

vote

**1**answer

42 views

### Graph classes which are not perfect but the stability number = clique cover numer?

I have a result for graphs whose stability number=clique cover number, which naturally includes the perfect graphs, but I'm curious about if there are other known and well-definable graph classes ...

**0**

votes

**0**answers

42 views

### Finding a “special” non singular submatrix

Given a square integer matrix $A \in M_n(Z)$ and two subsets $I, J \subset \{ 1, \ldots, n\}$, we define $A_{I,J}$ as the sub-matrix of $A$ containing the rows (resp. columns) whose index is in $I$ ...

**24**

votes

**4**answers

2k views

### How does this relationship between the Catalan numbers and SU(2) generalize?

This is a question, or really more like a cloud of questions, I wanted to ask awhile ago based on this SBS post and this post I wrote inspired by it, except that Math Overflow didn't exist then.
As ...

**7**

votes

**1**answer

191 views

### Probability of a graph procedure

We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, ...

**0**

votes

**0**answers

103 views

### Does the equality of product of integers modulo prime p holds in a given interval?

For any given prime $p$, does there exist $a_1,a_2,\dots,a_k,$ (not necessarily distinct) $b_1,b_2,\dots,b_m$ (not necessarily distinct) and $y_1$, $y_2$ such that
...

**11**

votes

**2**answers

287 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$?

**4**

votes

**1**answer

295 views

### The number of monotone full binary trees

Let $\rho$ be an equivalence relation on a semigroup $S$. A subsemigroup $S'$ of $S$ is called a $\rho$-cross-section of $S$, provided that $S'$ contains exactly one representative from each ...

**6**

votes

**1**answer

221 views

### Combinatorial formula for the number of different words

I originally posted this question here:
http://math.stackexchange.com/questions/1296199/combinatorial-formula-for-the-number-of-different-words :
I am interested in the asymptotic behaviour of the ...

**1**

vote

**1**answer

139 views

### Existence of functions on finite sets with specific propertise

Let $\Omega$ be an universal set and $|\Omega|=N$, denote $\mathcal{F}$ to be the family of all subsets $\subset \Omega$ with cardinal $n$. We now define a function $f:\mathcal{F}\rightarrow \Omega$, ...

**10**

votes

**1**answer

347 views

### Number of trivializations of a trivial word in the free group

Let $M$ be the free monoid on $2n$ generators $x_1,X_1,...,x_n,X_n$ and consider the set $T$ of all those elements of $M$ which map to 1 of the free group on $x_1,...,x_n$ under the homomorphism $\pi$ ...

**5**

votes

**2**answers

186 views

### Ordered lattice point enumeration

I initially asked this question over at StackOverflow as it has algorithmic flavor to it, but I haven't been getting much traction so I thought I would probe the mathematics community.
Setup: Let ...

**18**

votes

**2**answers

693 views

### Laws of Iterated Logarithm for Random Matrices and Random Permutation

The law of iterated logarithm asserts that if $x_1,x_2,\dots$ are i.i.d $\cal N(0,1)$ random variables and $S_n=x_1+x_2+\cdots+x_n$, then
$$\limsup_{n \to \infty} S_n/\sqrt {n \log \log n} = \sqrt 2, ...

**5**

votes

**0**answers

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

**11**

votes

**2**answers

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

**6**

votes

**1**answer

465 views

### Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:
Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...

**5**

votes

**1**answer

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

**5**

votes

**0**answers

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

**13**

votes

**2**answers

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

**2**

votes

**0**answers

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

**10**

votes

**2**answers

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

**-2**

votes

**1**answer

69 views

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

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

**13**

votes

**1**answer

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

**8**

votes

**1**answer

192 views

### Determinant of a checkerboard Hankel matrix with Catalan numbers

My goal is to compute
\begin{equation}
I = \det \left(\mathbf{I} + \mathbf{A}\right)
\end{equation}
where $\mathbf{A}$ is a $n \times n$ checkerboard matrix filled with Catalan numbers:
$$
\left\{
...

**10**

votes

**0**answers

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

**0**

votes

**1**answer

79 views

### Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties:
The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it).
$T$ has a ...

**4**

votes

**1**answer

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

**3**

votes

**1**answer

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

**8**

votes

**1**answer

688 views

### When the Lovász theta-function saturates its upper bound

The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, ...

**5**

votes

**3**answers

431 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, ...

**1**

vote

**1**answer

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

**7**

votes

**1**answer

1k views

### Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants

Zeta functions abound in mathematics. Audrey Terras describes in Zeta Functions and Chaos three zeta functions--the zeta fct. of a projective non-singular algebraic variety; the Artin-Mazur zeta ...

**2**

votes

**0**answers

61 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

138 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

**1**answer

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

**5**

votes

**1**answer

144 views

### A generalization of Erdős–Newman–Mirsky?

Given a sequence $S$ of natural numbers, write ${\bf Gap}(S)$ for the set of differences between consecutive terms. (So $|{\bf Gap}(S)|=1$ precisely for arithmetic progressions, hence the connection ...

**10**

votes

**0**answers

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