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)

0
votes
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
11answers
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
2answers
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
1answer
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
1answer
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
3answers
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
0answers
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
1answer
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
1answer
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
1answer
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
3answers
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
1answer
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
3answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
3answers
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
1answer
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
1answer
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
0answers
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
0answers
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
3answers
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
2answers
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
1answer
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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 ...