Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

2
votes
1answer
238 views

Number of subsets that sum to $0$

Suppose you choose $n$ distinct random numbers from a contiguous subset of cardinality $f({\beta, n})$ with at least $f({\alpha_+, n})$ positive and at least $f({\alpha_-, n})$ negative values from a ...
6
votes
2answers
193 views

Graphs with prescribed numbers of k-cliques

Let $(a_1,a_2,\dots, a_n)$ be a sequence of non-negative integers. Q. When does there exists a simple graph $G$ such that its number of $k$-cliques is $a_k$ (that is $G$ has $a_1$ vertices, $a_2$ ...
2
votes
1answer
86 views

How many distinct sets of n collinear points are there in an evenly-spaced two-dimensional grid of m x m points?

I'm seeking the definition of some function $f(n,m)$ which evaluates to the number of distinct sets of $n$ collinear points which are selected from an evenly-spaced two-dimensional grid of $m \times m$...
2
votes
1answer
127 views

How many lines of exactly n points can be placed in a discrete, square grid of size m x m?

Per the title, I'm seeking the definition of a function $f(n, m)$ which evaluates to the number of lines made from exactly $n$ points which can be placed on a two-dimensional discrete, square grid of ...
5
votes
2answers
134 views

Multiplication in universal enveloping algebra in terms of PBW isomorphism

Let $\mathfrak g$ be a Lie algebra. Consider the multiplication map $m:\mathfrak g\otimes U(\mathfrak g)\to U(\mathfrak g)$ and $i:S(\mathfrak g)\to U(\mathfrak g)$ -- Poincare-Birkhoff-Witt ...
2
votes
0answers
113 views

Nonvanishing of the dual Euler totient on boolean intervals of finite groups

The rank $n$ boolean lattice $B_n$, is the subset lattice of $\{1,2, \dotsm n \}$. Let $[H,G]$ be a boolean interval of finite groups. Its Euler totient is defined by $$\varphi(H,G):=\sum_{K \in ...
3
votes
0answers
60 views

How many unimodular lattices does it take to fill a cube with high probability?

Consider $C_a$ in $\Bbb Z^n$ a cube of height $a$ at origin in positive coordinates with one corner at origin. Consider the set $M_c$ of all unimodular matrices in $\Bbb Z^{n\times n}$ with each ...
0
votes
0answers
74 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 ...
1
vote
0answers
111 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 ...
1
vote
1answer
92 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
1answer
88 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
0answers
160 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, ...
1
vote
3answers
210 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, ...
5
votes
1answer
259 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
0answers
61 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
1answer
106 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
vote
1answer
41 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 \...
1
vote
0answers
69 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
1answer
82 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
0answers
37 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 well-...
6
votes
1answer
213 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
1answer
72 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
1answer
461 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
0answers
145 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
1answer
332 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
2answers
122 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 $$\frac{F^...
5
votes
1answer
248 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
1answer
141 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 ...
1
vote
0answers
39 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
1answer
92 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
1answer
159 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
2answers
112 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 insertions,...
3
votes
2answers
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 $A$...
2
votes
0answers
70 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
0answers
57 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
0answers
48 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
1answer
81 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 $\chi(...
2
votes
1answer
240 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
1answer
205 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
1answer
86 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 $p(z)=\sum\limits_{k=0}...
3
votes
1answer
175 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
0answers
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
1answer
66 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
0answers
71 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
1answer
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
0answers
63 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 i}{...
3
votes
2answers
217 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
0answers
70 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}$, ...
6
votes
1answer
115 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$? ...
3
votes
1answer
106 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 ...