**2**

votes

**1**answer

100 views

### enumeration of connected blocks in finite size square

Given a square of size n by m, how many ways could we choose sites, such that all the sites are connected?
By "connected" we mean "connected" by adjacent sites. We will illustrate by example, say, we ...

**1**

vote

**0**answers

108 views

### lower bound for difference between max cut and min cut

Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e.
...

**1**

vote

**1**answer

143 views

### How to understand a rooting of a dessin d'enfant?

As I understand it, rooted maps on surfaces were first introduced in enumerative combinatorics because they are easier to count than unrooted maps, which can have non-trivial symmetries. A map is a ...

**4**

votes

**2**answers

137 views

### open question on intersecting rectangles - reference request

In the now-inactive (and very nice) "Tricki" website that describes various proof techniques, there is an article (written I think by Timothy Gowers) that describes the following Ramsey-type problem:
...

**2**

votes

**0**answers

146 views

### Dissection of a polygon into convex polygons

Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons.
I would be very grateful for any information on this problem.
Remark 1. There ...

**1**

vote

**2**answers

142 views

### Upper bounding number of integer partition by binomial coefficient

Let $n,p \in \mathbb N$ and consider the integer partition of
$$\lfloor \frac{n(p-1)}{2} \rfloor$$
into $p$ or less parts, each of which is less or equal to $n-1$.
Can the number of partitions be ...

**3**

votes

**2**answers

182 views

### Upper bound for different sums having the same value

Let $\Lambda :=\{\lambda_1, \dots, \lambda_n\}$ be a set of $n$ distinct real numbers.
For a given $p \in \mathbb N$, consider further the set
$$I_p := \{ \{i_1, i_2, \dots, i_p\} : i_j \in \{1, ...

**7**

votes

**1**answer

135 views

### How many maximal triangulations of a rectangle?

I posted the following question on MathStackExchange, but I didn't any answer. So please let me post it on MathOverflow.
Let $L_{m,n}\subset\mathbb R^2$ be a rectangle given by $[0,m]×[0,n]$ with ...

**5**

votes

**0**answers

63 views

### Independent domination number for grid graphs

Let $G_{n,m}$ be the $n \times m$ grid graph, i.e. $G= P_n \Box P_m$, and $T_{n,m}$ the $n\times m$ torus grid graph, i.e. $G= C_n \Box C_m$, where $P_n$ and $C_n$ indicate the path graph of length ...

**1**

vote

**1**answer

131 views

### maximizing a function involving factorial

Can someone suggest a way to calculate the maximum with respect to $x \ge 1$ of:
$$f(x)=\frac{1}{x!} \frac{1}{1-c^{1/\binom{x+n-1}{n-1}}}.$$
The constants $c$ and $n$ are parameters such that $c \in ...

**5**

votes

**1**answer

166 views

### Is there a bijection of permutations onto mathematical objects that preserve information about descents?

$\omega \in S_n$ is an FPFI (fixed point free involution) (also called a matching) if $\omega^2=1$ and $\omega(i) \neq i$ for all $i$.
For $\omega \in S_n$, a descent occurs at $i$ if $\omega(i+1) ...

**3**

votes

**0**answers

80 views

### Number of cyclic difference sets

A subset $D=\{a_1,\ldots,a_k\}$ of $\mathbb{Z}/v\mathbb{Z}$ is said to be a $(v,k,\lambda)$-cycic difference set if for each nonzero $b\in\mathbb{Z}/v\mathbb{Z}$, there are exactly $\lambda$ ordered ...

**2**

votes

**2**answers

76 views

### quotient of planar groups

If G is an infinite planar group (it means that it has a generating subset C such that Cay (S, C) is a planar graph) and H is a normal subgroup of it, I would be very grateful if somebody helps me and ...

**5**

votes

**0**answers

76 views

### Bound on the number of lattice points in d-dimensional ball

The following paper states that the number of lattice points in a $d$-dimensional ball of radius $R$ is $V_d R^d + O(R^\alpha)$ where $\alpha = d - 2$ and $V_d$ is the volume of the unit ...

**1**

vote

**0**answers

31 views

### Bounds on Product of CDF or Beta function

I have functions of the form
\begin{align}
I_i = \int_0^\infty F_0(x)^aF_1(x)^b(1-F_0(x))^c(1-F_1(x))^ddF_i(x)~~~~i = 0,1
\end{align}
$F_0(x)$ and $F_1(x)$ are CDFs corresponding to the random ...

**3**

votes

**1**answer

205 views

### Existence of partitions

Good morning everybody.
I would like to know if anybody is aware of nontrivial results of the following form : if a family $\mathcal I$ of subsets of $\mathbb N$ satisfies such and such assumption, ...

**2**

votes

**0**answers

109 views

### Anti-arithmetic product of symmetric functions: (why) is it integral?

This is an analogue of MathOverflow question #138148. Indeed it is so analogous that I wrote the following by copypasting said question and making the necessary changes.
For every commutative ring ...

**2**

votes

**0**answers

61 views

### What is the minimal girth of a two-generator cayley graph for Alt(n) in which the girth relator is not a proper power?

First, a definition: a girth relator for a Cayley graph is a word that you get by reading the edge labels along a shortest loop. The girth relator is not usually unique, though it is often unique up ...

**-1**

votes

**1**answer

159 views

### Does the divergence of the sum of reciprocals of a set of integers imply this density statement about the set?

Suppose $A \subseteq \mathbb{N}$ is such that $\displaystyle{\sum_{n \in A} n^{-1}} = \infty$. Suppose $B \subseteq \mathbb{N}$ is infinite.
Is there a set $X \subseteq [1,\infty)$ and a increasing ...

**1**

vote

**0**answers

82 views

### Non-negative, monotone polynomial sequences without combinatorial interpretation

I am wondering what sequences of integers there are, that are known to grow polynomially, are non-negative, monotone but lacks a combinatorial interpretation.
By combinatorial interpretation, they ...

**2**

votes

**0**answers

74 views

### Stricter Notion of Crossing in a Partition

Let $k$ be an integer. Traditionally a partition $\pi=V_1\cup \dots \cup V_n$ of the set $[k]:=\{1,\dots, k\}$ is called crossing when there exist $a,c\in V_i$ and $b,d\in V_j\not= V_i$ such that ...

**2**

votes

**1**answer

88 views

### Is barycentric subdivision of a collapsible, regular CW complex collapsible (non-evasive)?

Let $X$ be a finite, regular CW complex, and let $X'$ be its barycentric subdivision (i.e. the order complex of the face poset of $X$). Assume $X$ is collapsible.
Is $X'$ collapsible?
Is $X'$ ...

**16**

votes

**4**answers

666 views

### List of integers without any arithmetic progression of n terms

Let's consider a positive integer $n$ and the list of the $n^2$ integers from $1$ to $n^2$. What is the minimum number $f(n)$ of integers to be cancelled in this list so that it is impossible to form ...

**3**

votes

**0**answers

130 views

### On a problem of sphere-packing for Reed-Solomon codes

Suppose we have an $[n, k+1, n-k]$ Reed Solomon code $\mathcal C$ over $\mathbb F_q$, where $n-k=d$ is the minimum distance, and suppose that $d=2t+1$. We know that for every $r \in \mathbb F_q^n$ the ...

**6**

votes

**0**answers

73 views

### Why have most maximal cliques of Paley graphs odd size?

I ask this question mainly by curiosity.
See here for definitions and a plot of the clique numbers of the Paley graphs for the primes $p\equiv 1 \pmod 4$ up to $10000$.
Is there an ...

**6**

votes

**0**answers

176 views

### Non-trivial bounds for polynomials at a fixed point

Let $f$ be a polynomial of degree $d$. Of course $|f(z)|\sim C|z|^d$ as $|z|\rightarrow\infty$ but also, since any polynomial is completely determined by its values at any $d+1$ points, we may ask how ...

**10**

votes

**3**answers

433 views

### Square filling self avoiding walk

I want to create an algorithm that fills a square grid with a random Hamiltonian path starting at a particular point. See this example.
One approach is to try a free direction as a next step, and ...

**1**

vote

**0**answers

69 views

### Expanding graphs from iterated zig-zag product

Let $\Gamma \, zz\, G$ denote the zig-zag product of graphs $\Gamma$ and $G$.
Reingold, Vadhan, and Wigderson proved that the second largest eigenvalue of the normalized adjacency matrix of the ...

**7**

votes

**2**answers

118 views

### Trees with a maximal convex hull: are the only optimal solutions Steiner trees?

For given $n\geqslant 3$, I'm looking for a connected set composed of $n$ equal segments in the plane such that the convex hull of it has maximal area $A(n)$. To simplify notation, we'll take ...

**0**

votes

**0**answers

70 views

### Linear extensions and directed, rooted spanning trees

Let $P$ be a poset with a unique bottom element $\perp$ and view its Hasse diagram $H$ as an oriented graph. Can the principle of exclusion-inclusion
be used to calculate the number of linear ...

**2**

votes

**1**answer

77 views

### Existence of neighborhood inclusion for 4-chordal graphs

Let $N(v)$ be the (open) neighbourhood set of a vertex $v$, and let $N[v]$ be the closed neighbourhood set of $v$.
A graph $G$ is called 4-chordal if $G$ has no induced cycle with five or more ...

**2**

votes

**3**answers

511 views

### a colouring / matching problem

While trying to find a bijection which preserves various combinatorial statistics, I was led to the problem below. Very much to my surprise, a closely related question, Coloring summands of given ...

**9**

votes

**0**answers

115 views

### Computing exact or asymptotics for number of strings over an alphabet of size $n$ that have no non-trivial substrings that appear more than once

I ran across a seemingly relatively simple combinatorics problem that appears open. For an alphabet of size $n$, let $A(n)$ be the number of strings over the alphabet that have no substring of length ...

**0**

votes

**1**answer

57 views

### Monotonicity of the gap of permutated sequence

Let $a$ be an arbitrary sequence and denote by $\mbox{gap}_k(a) = a_{(k)} - a_{(k+1)}$, where $a_{(k)}$ is the $k$th largest component of $a$. Of course, $k+1$ should be no larger than the length of ...

**1**

vote

**2**answers

134 views

### Non-DS circulant graphs

Let $p$ be a prime number greater than or equal to 11. Are there any cospectral non-isomorphic graphs with circulant graphs on $p$ vertices.
Which circulant graphs over prime number of vertices ...

**2**

votes

**1**answer

129 views

### Vanishing homology of simplicial complexes with few facets

Let $K$ be a simplicial complex with $n$ vertices and $n-t$ facets, where $t \geq 3$.
Is it true that the $(n-3-j)$th reduced homology (with coefficients in a field) of $K$ vanishes for $0 \leq j ...

**5**

votes

**2**answers

281 views

### Random Vornoi Diagrams (particular measures)

This is my second question about Random Voronoi diagrams, in my first question was given some excellent advice but i was not clear in explaining what i was looking for.
I'm interested to know ...

**8**

votes

**2**answers

617 views

### Random Voronoi Diagrams

I'm interested in what research has already been done with regards to the statistics of random voronoi diagrams. I have had a look on google scholar and results are a little inconclusive. I'm ...

**2**

votes

**1**answer

191 views

### On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections

Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements.
We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we ...

**13**

votes

**2**answers

290 views

### Flag complexes that are shellable but not vertex decomposable

As the title suggests, I was wondering if anyone can point me to any examples in the literature to flag complexes that are shellable but not vertex decomposable.
It is well-known that if a ...

**6**

votes

**1**answer

166 views

### Counting cyclic binary sequences of length $n$ where ones appear in blocks of length at least $k$

How many binary cyclic sequences of length $n$ exist, where ones only appear in blocks of length at least $k$? We do not consider sequences that result from each other by a cyclic shift equivalent.
...

**13**

votes

**1**answer

328 views

### A method for making a graph bipartite

Given any graph $G$, can we find a bipartite subgraph of $G$ with at least $e(G)/2$ edges ($e(G)$ is the number of edges in $G$) by sequentially deleting the edge belonging to the most number of odd ...

**1**

vote

**1**answer

82 views

### Number of points in an intersecting linear hypergraph

I first asked the question below at math.stackexchange.com ( http://math.stackexchange.com/questions/920442/number-of-points-in-an-intersecting-linear-hypergraph ) but somebody suggested I ask it in ...

**3**

votes

**0**answers

76 views

### More 3-connected cubic graphs with all 2-factors of same cycle type?

The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...

**5**

votes

**1**answer

302 views

### Are there number-theoretic graphs that are far from being isomorphic

I say that two graphs $G_1=(V_1,E_1)$, $G_2 = (V_2,E_2)$
with the same number of vertices, edges,
are $\epsilon$-far from being isomorphic, if for any bijection between $V_1$ and $V_2$, the fraction ...

**-3**

votes

**1**answer

138 views

### How many sequences of length n satisfy these constraints? [closed]

I want to count the number of unique sequences of length n with the following constraints.
Each element of the sequence is an integer in $\lbrace 1,2,\dots,n\rbrace$.
Each two adjacent elements of ...

**0**

votes

**1**answer

88 views

### Comparing ideals in posets

Consider a partially ordered set $P$, and two upper sets $U_1$, $U_2$ in this poset.
What are some natural ways to measure how equal these two upper sets are?
This question arise naturally in the ...

**5**

votes

**0**answers

158 views

### (Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples

Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...

**12**

votes

**2**answers

477 views

### The sum of the carries when adding and multiplying two numbers in base p

Let $\sigma_p(m,n)$ (resp. $\pi_p(m,n)$) denote the sum of the carries when adding
(resp. multiplying) the numbers $m=\sum_{k\ge0}m_kp^k$ and $n=\sum_{k\ge0}n_kp^k$ using base-$p$ arithmetic where ...

**19**

votes

**1**answer

814 views

### Recognize this strange expression from linear algebra?

I've come across an odd-looking expression and oh how I wish I had a more elegant description of it. Maybe someone who enjoys symmetric bilinear forms in characteristic two will recognize it? Or ...