**1**

vote

**0**answers

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

**-4**

votes

**0**answers

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

**1**

vote

**1**answer

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

**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}$ ...

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

**2**

votes

**3**answers

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

**4**

votes

**1**answer

232 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

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

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

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

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

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

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

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

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

**0**

votes

**1**answer

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

**12**

votes

**1**answer

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

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

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

**2**

votes

**2**answers

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

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

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

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

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

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

**3**

votes

**2**answers

133 views

### Characterizing graphs whose Incidence Matrix has the all ones vector in its row span

Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to known when the row span of ...

**2**

votes

**0**answers

68 views

### Given a vector of positive integers, count the number of combinations which have a sum that produces a different value

I have a list (vector) of positive integer numbers, including repetitions. For example,
$L = [1, 1, 4, 1, 3]$;
I want to calculate the number of different sums obtained by using the elements of $L$, ...

**1**

vote

**0**answers

55 views

### bounded degree graph colouring.

I was wondering if anyone could provide references on the following:
Is determining the chromatic number of a bounded degree graph APX-complete?
2.I've seen the result that states it is NP-hard ...

**2**

votes

**0**answers

45 views

### Hypergraph edge colouring

I'm interested in knowing if finding the edge-chromatic number of a $k$-uniform $k$-partite hypergraph is NP-hard for $k\geq 3$ Could anyone provide a reference for the result? By edge-chromatic ...

**4**

votes

**1**answer

80 views

### Choice number of embedded graphs

For given $g$, consider the family of graphs which may be embedded to the compact orientable surface of genus $g$. For this family, consider maximal clique $\alpha(g)$, maximal chromatic number ...

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

**5**

votes

**1**answer

203 views

### Can we cover a set by a particular family of sets?

Let $A_1,A_2,\ldots,A_m,B_1,B_2,\ldots, B_m$ be (not necessarily distinct) subsets of $[n]=\{1,2,\ldots,n\}$. Suppose that each $i\in [n]$ appears in at least $k$ of these $2m$ sets.
I want to ...

**1**

vote

**1**answer

85 views

### Weighted counting of circular codes

Given a circular code $X$ (for example: $X=\{ w,b \}$) with generating function $u(z)=\sum\limits_{k=0}^{\infty}{u_k z^k}$ (in this example : $u(z)=2z$), the generating function ...

**3**

votes

**1**answer

173 views

### A spectral graph theory problem

Let $S$ be a zero-free subset of the group ${\bf Z}_2^n$ and $\Gamma={\rm Cay}({\bf Z}_2^n,S)$ be a bipartite Cayley graph. For some choices of $S$, the graph $\Gamma$ has $4$ distinct eigenvalues, ...

**2**

votes

**0**answers

57 views

### Terminology and technique for repeated pairwise removal of elements of posets: “Collapsibility” of a “face poset”

Let $P$ be a poset, or partially ordered set. Let $\le$ denote the reflexive order on $P$, and $<$ the corresponding irreflexive order. Let the phrase "a maximal pair" in $P$ refer to an
ordered ...

**4**

votes

**1**answer

65 views

### Separate a special poset by function

Assume $A = \prod_{i=1}^n\{0,1\}$, i.e. element $(a_1,\cdots,a_n)=a\in A$ is n-tuples like $(1,0,1,\cdots)$.
There is an obvious partial order on the $A$: say $a < b$ for $a,b\in A$ if and only ...

**2**

votes

**0**answers

63 views

### Relating face polytopes of permutohedra to integer partitions

The OEIS entries A019538, A049019, and A133314, relate a refinement of the face polynomials of the permutohedra (A049019) to partition polynomials (A133314) defined by multiplicative inversion of an ...

**6**

votes

**1**answer

122 views

### Union-closed family generated by n 2-sets

I asked this question on Stackexchange, but I got no answer, so I ask it here.
Let us define a $2$-set as a set with exactly $2$ elements. For a natural number $n$, let $l(n)$ denote the least ...

**1**

vote

**0**answers

62 views

### Lower bound the ratio of the combinatorial quantities

Suppose $p < q$, $s = p^{d}$ for some fixed $d \in (0,1)$, let $p$ goes to infinity, define the following quantity,
\begin{aligned}
\quad f(j) = \sum_{i = 0}^{\min(j,s)}{s \choose i}{p-s \choose ...

**2**

votes

**1**answer

157 views

### sum over all integer partitions, of the product of the factorials of the terms

I'm looking for something making tractable the sum, over all partitions into k terms of an integer n, of the product of the factorials of all the terms.
Thanks,

**1**

vote

**0**answers

69 views

### connectedness of semi algebraic sets

We know the inequalities $x_ix_j >\theta_{ij}$ or $x_ix_j<\theta_{ij}$ for some $\theta_{ij}$>0, some $i,j\in\{1,\cdots,n\}$, $i\neq j$ defines the easiest semi algebraic set in $R^n_{\geq 0}$, ...

**5**

votes

**1**answer

106 views

### Average minimum number of random k-sparse vectors in GF(2) to span the whole space?

What is the average minimum required number of independent $k$-sparse (having at most $k$ non-zero elements) random vectors belonging to $\mathbb{F}_2^n$ to span the whole space of $\mathbb{F}_2^n$? ...

**2**

votes

**1**answer

99 views

### What is the densest bipartite graph with unique Hamiltonian cycle?

In a prior post regarding perfect matching, it was stated that the densest graph with a unique perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices.
Analogously, what is the ...

**5**

votes

**1**answer

132 views

### Upper Bound for the Difference of Even Probability and Odd Probability in Hypergeometric Distribution

Let $X$ be a random variable following the hypergeometric distribution with parameters $N,K,n$, where
\begin{equation}
Pr(X=k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}.
\end{equation}
To ...

**3**

votes

**0**answers

175 views

### First to note/document the relation between permutohedra and multiplicative inversion

The relation between the refined face numbers of the permutohedra and the formal series expansion of the reciprocal of a function (exponential generating function, formal Taylor series) is given in ...

**1**

vote

**1**answer

131 views

### Number of eigenvalues of a Cayley graph

Let $G=Z_2^n$ and $S\subset G$. Is there any relation for number of distinct eigenvalues of $\Gamma=Cayley(G,S)$ graph depending on $n$ and $|S|$, or at least diameter of $\Gamma$? If you have any ...

**4**

votes

**1**answer

130 views

### “Small” simplicial complex with torsion trees

I am giving an expository talk soon about Duval-Klivans-Martin's paper Simplicial Matrix Tree Theorems, and I've been struggling to find a good example to do at the board. An important aspect of the ...

**3**

votes

**1**answer

113 views

### Alternative parallel paths

There are $n$ non-intersecting strings (with ends $x_1,\dots, x_n$ and $y_1,\dots, y_n$). An additional string intersects the first $n$ strings somehow. All the intersections are simple (vertices of ...

**7**

votes

**1**answer

283 views

### Choosing two-colorable subgraph in a triangulation

Consider a planar graph $G$ which is a triangulation.
Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$?
It is known that it is not always ...