Skip to main content

All Questions

Filter by
Sorted by
Tagged with
1 vote
0 answers
99 views

Szemeredi Regularity Lemma - Reasonable Bounds

Recently, I came across the wonderful Szemeredi regularity lemma and I was wondering. Are these "natural/reasonable/standard" examples of random graphs families, for which the number of $\...
3 votes
0 answers
328 views

Behrend's construction vs. Triangle removal lemma

I was reading Zhao's book "Graph theory and additive combinatorics" and on page 71 I came across Remark 2.5.4 which I'd like to understand. Theorem 2.3.1 (Triangle removal lemma) For all $\...
1 vote
0 answers
147 views

Counting Hamiltonian cycles in graph and finding a coefficient of polynomial

Exact result is #P-Hard, so we are looking for bounds. Let $G$ be simple graph or simple digraph and $A$ its adjacency matrix. $A$ is $n \times n$ with entries only zeros or ones. Let $K=\mathbb{Z}[...
7 votes
1 answer
509 views

A permutation problem

Here I ask a question on permutations of $n$ distinct real numbers. QUESTION: Let $a_1,a_2,\ldots,a_n\ (n>1)$ be (pairwise) distinct real numbers. Is there a permutation $b_1,\ldots,b_n$ of $a_1,\...
7 votes
1 answer
760 views

Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...