**0**

votes

**0**answers

35 views

### Derandomizing AP existence in $A\subseteq \{1,\ldots,N\}$ for $\delta(A) \geq 1/k$

In the answer to the mathoverflow question here, it was established that if we let $p$ be the probability of including point $v$ in $A\subseteq \{1,\ldots,N\}$ and this is done independently for all ...

**8**

votes

**1**answer

574 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**1**

vote

**1**answer

75 views

### Convexity of truncated expectation

Let $k, n$ be two positive integers with $k \leq n$, and let $P = \{ (x_1, \dots, x_n) \in [0, 1]^n : \sum_i x_i = k \}$.
Given $x = (x_1, x_2, \dots, x_n) \in P$, let $X_i$ be the random variable ...

**8**

votes

**1**answer

665 views

### A Zero-Multiplicity Problem Related to Foulkes' Conjecture

I'm a combinatorialist that is interested in estimating multiplicities of irreps of $1^{S_{kn}}_{S_k \wr S_n}$ (the action of symmetric group on uniform partitions). I'm aware of the difficulty (or ...

**0**

votes

**0**answers

149 views

### Warren's Theorem

At the end of page 12 in this document Noga Alon mentions Warren's Theorem on sign patterns: tau.ac.il/~nogaa/PDFS/tools1.pdf
Does anyone know of an intuitive explanation of the proof of it ? Also, ...

**-4**

votes

**0**answers

120 views

### Detecting Bijection between two Permutation Set [on hold]

Let, $L$ is a set of $n$ labels / colors (repetition of label/color is possible). Assume, there is a function $f$, that maps labels of $L$ to itself. this mapping is bijective.
Let, $\beta$ is a set ...

**2**

votes

**1**answer

79 views

### Catalogs/numbers/constructions of non-isomorphic conference matrices

I am interested in complete catalogs of non-isomorphic conference matrices, similar to those of Hadamard matrices. Do such catalogs exist? If yes, then where could they be found, and what is an ...

**15**

votes

**11**answers

2k views

### Chromatic number of graphs of tangent closed balls

The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a disk packing whose graph is $G$. What ...

**23**

votes

**2**answers

2k views

### Order of products of elements in symmetric groups

Let $n \in \mathbb{N}$. Is it true that for any $a, b, c \in \mathbb{N}$ satisfying
$1 < a, b, c \leq n-2$ the symmetric group ${\rm S}_n$ has elements of order $a$ and $b$
whose product has order ...

**1**

vote

**1**answer

71 views

### Counting bounded genus non-isomorphic graphs

What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$?
I am most interested in $d\leq3$ and $g=0$.

**3**

votes

**1**answer

87 views

### Neighbourhood of a word and Levenshtein distance

The Levenshtein distance or Edit distance $$ lev(U,V) $$ between two strings $U$ and $V$ over a finite alphabet $\Sigma$ of size $ \left| \Sigma \right| = \sigma ,$ is the minimal number of ...

**4**

votes

**3**answers

175 views

### Relation between diametral path and regularity of a graph

Let $G(V,E)$ be a graph. A path whose length is equal to the diameter of a graph is called a diametral path. In a cycle graph every vertex has $2$ diametral paths. Now I need to prove that this:
...

**1**

vote

**0**answers

91 views

### A probability question related to combinatoric problem

I am trying to solve a combinatoric problem. The problem is the following:
There are A,B,C three types of people. There are totally N people arriving sequentially and make a choice between two boxes X ...

**11**

votes

**1**answer

954 views

### Menger's theorem via matroids

Let $G=(V,E)$ be an oriented graph, $Y\subset V$ be some fixed set of its vertices. Call $A\subset V$ independent if there exist $|A|$ vertex-disjoint paths starting in $A$ and ending in $Y$. It is ...

**1**

vote

**1**answer

280 views

### Rewriting a series $\sum_{n=0}^\infty \frac{1}{n!}(\Delta^\varepsilon)^n a_n$ in the form $\sum_{n=0}^\infty c_n \varepsilon^n$

I would like to rewrite the series $$\sum_{n=0}^\infty \frac{1}{n!}(\Delta^\varepsilon)^n a_n,$$ where $\Delta^\varepsilon=\sum_{k=1}^\infty \varepsilon^k b_k$, as a series in $\varepsilon$ ...

**1**

vote

**1**answer

84 views

### Intersection of members in a separating union-closed family of sets

Tony Huynh gave a nice answer to a question I asked here :
Number of members of a separating union-closed family whose universe has given cardinality
The answer shows in fact that if $\mathcal{F}$ ...

**12**

votes

**3**answers

7k views

### Solving a Rubik's cube via a series of randomly selected (quarter-turn) Singmaster moves

In July of 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge demonstrated (computationally) that a $3\times3\times3$ Rubik's cube, starting in an arbitrary configuration, can ...

**6**

votes

**1**answer

195 views

### Is the exponent $2$ sharp in the Balog-Szemerédi-Gowers Theorem?

The Balog-Szemerédi-Gowers theorem can be stated in the following form: let $A,B$ be subsets of $\mathbb{Z}/n\mathbb{Z}$ (say) with equal cardinality, such that
$$
\|1_A*1_B\|_2 \ge K^{-1} \|1_A\|_1 ...

**2**

votes

**3**answers

189 views

### Existence of special graph

Let $G$ be a $n$-vertices graph and $\lambda_1$ is the largest eigenvalue of this graph. If $\lambda_1$ is an integer value, we can easily find the $\lambda_1$- regular graph with $n$ vertices. Now, ...

**0**

votes

**1**answer

56 views

### Choosing directed subgraph in a triangulation

Consider triangulation $T.$
Is it always possible to choose such a subgraph $H$ of $T$ that has a common edge with every face of $T$ and can be directed in such way that indegrees of all vertices of ...

**3**

votes

**1**answer

63 views

### Generating Uniquely k-Optimal Point Sets

This question is motivated by the observation that finding an optimal tour through a set of points in the Euclidean plane is especially simple, if the points are in convex configuration and, that the ...

**1**

vote

**1**answer

142 views

### Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...

**3**

votes

**1**answer

81 views

### Does the Chen-Chvátal Conjecture on metric spaces hold for maximal lines?

A conjecture by Chen and Chvátal asks for the minimum number of induced "lines" in a metric space, in the same spirit as the De Bruijn–Erdős theorem.
Though the statement of this problem on Douglas ...

**2**

votes

**1**answer

104 views

### Number of members of a separating union-closed family whose universe has given cardinality

If I'm not wrong, it is easy to prove the following statement :
If $n$ is a natural number $\leq 4$, if $\mathcal{F}$ is a union-closed family of nonempty sets, if the universe of $\mathcal{F}$ (i.e. ...

**10**

votes

**3**answers

1k views

### When does $P(a−b)=0$ for $a≠b$ ensure $P(0)=0$? (Continued.)

As a natural (and expectable) extension of my earlier question:
How large must be a set $A\subset F_2^n$ to ensure that if $P$ is a cubic polynomial in $n$ variables over the field $F_2$, ...

**4**

votes

**1**answer

149 views

### What is the minimum number of independent sets for a graph with fixed numbers of vertices and edges?

Fix integers $V$ and $E_{\text{max}}$, and consider graphs $G$ with $V$ vertices and at most $E_{\text{max}}$ edges. What is the best lower bound that one can give on the number of distinct ...

**4**

votes

**1**answer

233 views

### Vector with many non-zero coordinates

Given finite field $\mathbb{F}_q$, positive integers $n$ and $k<n$. Given $k$-dimensional subspace $X$ of $\mathbb{F}_q^n$, for which $m=m(q,k,n)$ may we find for sure a vector in $X$ with at least ...

**2**

votes

**0**answers

57 views

### Number of $(2n-1)$-edge-colorings of the complete graph $K_{2n}$

I just started reading about graph theory and have a question (which might be trivial). How many $(2n-1)$ edge colorings of $K_{2n}$ are there?
A vaguer question: can I write $K_{4n}= K_4 + K_4 ...

**-1**

votes

**0**answers

51 views

### Central limit theorem for perfect matching counts [closed]

This is a modification to one of my questions:
Set $N_G$ the number of copies of graph $G$ in the Erdős–Rényi random graph model $G(n,p)$. We have the law of large number for the number of copies of ...

**4**

votes

**3**answers

2k views

### Proofs of Lower Bounds for Ramsey Numbers?

As a sort of dual question to this question, I am wondering what proofs people know of lower bounds on Ramsey numbers $R(k, k)$. I know of two proofs: there is Erdos's beautiful probabilistic ...

**4**

votes

**2**answers

245 views

### Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?

Let $f(G)$ give the number of perfect matchings of a graph $G$.
Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Consider collection of all $2n$ vertex balanced bipartite graph to be ...

**1**

vote

**1**answer

37 views

### How to generate a Latin square $M'$ in the same main class as $M \in \mathrm{LS}(9)$ which agrees with $L$ in the most cells?

I'm brainstorming an idea for storing a compressed list of main class representatives of Latin squares of order $9$. One way to compress the list would be to store one Latin square $L_1$, and for $i ...

**18**

votes

**1**answer

1k 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}$, ...

**2**

votes

**2**answers

113 views

### Probability of no $k$ 1's in arithmetic progression in binary sequence of length $n$

It is well known [it's on Wolfram Mathworld, for example] that the probability of no runs of $k$ consecutive $1$'s will occur in a $\{0,1\}$-valued sequence of length $n$ is exactly equal to ...

**0**

votes

**0**answers

66 views

### Missing count in number of perfect matchings

Let $f(G)$ give the number of perfect matchings of a graph $G$.
Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Consider collection of all $2n$ vertex balanced bipartite graph to be ...

**3**

votes

**0**answers

31 views

### Does the rank (=height) of a well partial order bound its type (=length, =stature)?

Terminology and context
(This should all be standard, but is recalled because terminology sometimes varies, and also to put the question into perspective.)
A partially ordered set is called ...

**3**

votes

**1**answer

102 views

### Choosing $K$ “centers” from the space of permutations

Let $\Pi$ denote the space of all permutations of $\{1,\dots,n\}$, and let $d(\cdot,\cdot)$ be a metric on $\Pi$. Suppose I am given a large integer $K$ and I have to select $K$ permutations ...

**12**

votes

**1**answer

397 views

### A combinatorial identity involving harmonic numbers

The harmonic numbers are given by $$H_n=\sum_{k=1}^n\frac{1}{k}.$$
Numerical calculation suggests
$$
\sum_{k=1}^{n}(-1)^k{n\choose k}{n+k\choose k}\sum_{i=1}^{k}\frac{1}{n+i}=(-1)^nH_n.
$$
I can not ...

**5**

votes

**1**answer

235 views

### Combinatorics: set partitions of a poset

Let $\pi_n$ be the poset of all set partitions of $\{1,...,n\}$ ordered by refinement, $\sigma = \{B_1,...,B_k\}$ be a set partition with blocks $B_i$, and $\max(B_i)$ be the maximum value in the ...

**15**

votes

**1**answer

313 views

### Combinatorics problem about sum of natural numbers

Following combinatorics problem is claimed to be an open problem in "The Princeton Companion to Mathematics" (pp. 6)
Let $a_1,a_2,a_3,...$ be a sequence of positive integers, and suppose that each ...

**1**

vote

**0**answers

144 views

### A conjecture about orbits in a recursive function motivated by Kolakoski's sequence

We first introduce several functions motivated by Kolakoski's sequence. The conjecture itself can be stated independently of Kolakoski's sequence. You can skip straight to the formulation of the ...

**4**

votes

**1**answer

559 views

### Is there a name for this fast growing functions?

Define $F(n,i)=\prod_{j=1}^nj^{j^i}$.
$F(n,0)=n!$.
$F(n,1)$ is hyperfactorial.
Is there a term for $F(n,i)$? How fast do these grow? Is growth rate $2^{\frac{c_in^{i+1}\log_2n}{i+1}}$ with some ...

**5**

votes

**1**answer

187 views

### Algorithm for Low Discrepancy Sequence of Hamilton Cycles in Complete Graphs

Are there deterministic algorithms that generate a sequence of Hamilton Tours that is superior to a sequence of randomly chosen tours, when applied to the TSP (by applying to the TSP, I understand ...

**2**

votes

**1**answer

224 views

### upper bound on derivatives of a function defined on an arc

This is a simple question I asked in math.SE last month but unfortunately no one gives any comment. So I decided to try some luck here.
You can skip examples below and read from "General setting" at ...

**2**

votes

**1**answer

139 views

### Can we deduce that a finite topology $T$ satisfies Frankl's union-closed set conjecture?

Let $X$ be a finite set and $T$ be a topology on $X$. Then $T$ is both union-closed and intersection-closed. Can we deduce that $T$ satisfies Frankl's union-closed set conjecture?
(We know that a ...

**0**

votes

**0**answers

36 views

### Separation on discrete set

Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ ...

**4**

votes

**1**answer

629 views

### Covering the integers by two kinds of three-element sets (IMO Shortlist 2001 problem C4): extensions and generalizations?

As a straightforward generalization of IMO Shortlist 2001 problem C4, we can show the following fact:
Let $u$ and $v$ be two positive integers. A set of three integers $\left\lbrace ...

**5**

votes

**2**answers

704 views

### Motivation for Frankl's conjecture?

Frankl's conjecture, open since 1979, says that if $F$ is a union-closed family of subsets of $X$, then there is some $x \in X$ such that $x$ appears in at least half the sets in $F$.
What was the ...

**2**

votes

**1**answer

155 views

### The class of $(-1,0,1)$-matrix with all row sums and column sums equalling to $0$

Let $n$ be an even positive integer and $W_n$ be the class of all $n\times n$ matrices with entries from the set $\{-1,0,1\}$ satisfying all row sums and column sums are equal to $0$.
For any $M\in ...

**4**

votes

**1**answer

91 views

### Probability of existence of a base in the span of sparse vectors in GF(2)

For $i=1,2,\dots,l$, let $\mathbf{v}_i =(v_{i1},v_{i2},\dots,v_{in}) \in \mathbb{F}_2^n$ be a sparse vector in GF(2) such that all $v_{ij}$'s are independent for all $1 \le i \le l, 1 \le j \le n$ and ...