Questions tagged [extremal-combinatorics]

This tag is for questions asking for combinatorial structures of maximum or minimum possible size under some constraints. Typical questions ask for bounds or the exact value of the extremal size, or for the structure of extremal configurations.

Filter by
Sorted by
Tagged with
5 votes
0 answers
94 views

Combinatorial problem about finding equidistant words

Assume I have an alphabet $\{A,B,C...\}$ with a total of $K$ symbols. For words of same length, I define the distance $d$ between them as the number of positions in which they have differing symbols (...
mavzolej's user avatar
  • 1,442
1 vote
1 answer
61 views

What is the least number of subsets that you need to separate all the 2-element subsets of a given (finite) set. [closed]

The question more formally can be written as follows, Suppose there is a set $X$ with $|X|=n$. Suppose $S\subseteq \mathcal{P}(X)$ s.t. for any two-element subset $Y\subseteq X$ there is a $Z\in S$ ...
Arun's user avatar
  • 31
0 votes
1 answer
114 views

A generalization of Turan's theorem

The Turan's theorem gives a tight upper bound of the number of edges in a $K_n$-free graph. I didn't manage to find some information about the generalization of this theorem when we're asked to ...
Bertrand Haskell's user avatar
1 vote
1 answer
74 views

How to prove that the following conclusion is true? [closed]

Consider a set $\mathcal{X}$ with $m$ numbers, and take out $a, b, c, d$ numbers respectively. The number of combinations of $a$ number taken from $\mathcal{X}$ is recorded as $C_{m}^{a}$. The number ...
Kristy's user avatar
  • 21
0 votes
2 answers
82 views

Farther and nearest points from an ellipse to the a line segment.

I really need your help in math, I've solved this problem in several ways, but I'm not getting anywhere... Given a straight line $x-3y-9=0$ and an ellipse $x^2/9 +y^2/4 = 1$, find the nearest and ...
Masha's user avatar
  • 1
1 vote
1 answer
66 views

If a graph has exponentially many maximal cliques, what can we say about how many maximal cliques each vertex belongs to?

My question is motivated by the following example: For $n \geq 1$, let $G$ be the complete $n$-partite graph on $2n$ vertices, i.e., every vertex of $G$ is connected to all others except one. Then $G$ ...
pyridoxal_trigeminus's user avatar
4 votes
2 answers
99 views

Distinguishable subsets of the 52-card blackjack deck

I need to find, for $n = 0, 1, . . . , 52$, the number of distinguishable subsets of size n. Blackjack deck has $4$ cards for each value from $1$ to $9$ and $16$ cards of value $10$, color doesn't ...
Monia's user avatar
  • 51
4 votes
0 answers
186 views

Disjoints subsets of a multilabeled set

We are given a set of elements $U$ and $n$ binary functions, i.e. $f_i: U \to \{0,1\}$. Moreover, each function maps exactly $k$ elements of $U$ to 1. The task is to create a collection of $n$ ...
cgss's user avatar
  • 1,098
6 votes
0 answers
344 views

Decrease list difference via swaps

There are four lists, each with $100$ numbers in $[0,1]$. You want to perform as few swaps between pairs of numbers as possible, so that the difference between the sums of numbers in any two lists ...
user57012's user avatar
0 votes
0 answers
10 views

Could someone help me answer the following question using the Markov inequality and Chebyshev's inequality? I appreciate your assistance in advance.

"Denote by $C(G)$ the largest number of vertices in a component of a graph $G$. Show that if $p \ll 1/n$, then $C(G(n,p))\leq log⁡(n)$ with high probability. Demonstrate that for each $\...
Alicia Amorim's user avatar
0 votes
1 answer
57 views

proving an inequality for combinatorial sum

The following inequality comes from the literature: N. Alon, Y. Caro, On the number of subgraphs of prescribed type of planar graphs with a given number of vertices //North-Holland Mathematics ...
licheng's user avatar
  • 2,216
3 votes
1 answer
105 views

Set system containing no chain of length $3$

Let $n$ be even and let $\mathcal{A}\subset\mathcal{P}(n)$ be a set system that contains no chain of length three. Prove that \begin{equation}|\mathcal{A}|\le{n\choose{n/2}}+{n\choose{n/2-1}}.\end{...
user avatar
3 votes
1 answer
250 views

Large family of subsets with small pairwise intersections

Let $\alpha>0$ be a constant (can be sufficiently small if necessary) and $n$ be sufficiently large. What can we say about the cardinality of a family of subsets of $\{1,2,\ldots,n\}$, each of size ...
DesmondMiles's user avatar
  • 2,712
1 vote
1 answer
63 views

An upper bound on the size of antichain

Let $P$ be a collections of subsets of the set {1,2, ..., n} such that $P$ is an anti-chain and cardinality of sets in $P$ is strictly less than $k$, where $1 \leq k \leq n$? Can we get an upper bound ...
Renrael Htam's user avatar
0 votes
1 answer
41 views

Combinatorial Problem based (indirectly) on Generalized Pigeonhole Principle

I was going through my Discrete Mathematics (Discrete Mathematics and Its Applications by Kenneth Rosen) textbook when I came across this problem. Suppose that a computer science laboratory has 15 ...
Sahil Muhammed's user avatar
0 votes
1 answer
70 views

Prove the minimum size of a separating union-closed family of sets is equal to the size of its universe

That's a statement given without proof in the following paper (page 12, ch. 3.5) about Frankl's union-closed sets conjecture. It's labeled as easy to prove, but I'm struggling with it. For non-union-...
Nikita Dezhic's user avatar
0 votes
1 answer
51 views

Dividing a hyper-sphere ( of dimension $n$) into $N$ equal measure of bounded diameter

The following is stated in the Erdös-Bollobás Paper - On a Ramsey-Turán type Problem If $n$ is a sufficiently large number, then $k+1$ dimensional sphere can be divided into $n$ sets, each of equal ...
total dependent random choice's user avatar
1 vote
0 answers
51 views

Set system containing no chain with $k+1$ sets [duplicate]

Let $\mathcal{F}\subset \mathcal{P}[n]$ be a set system such that each chain in it has at most $k$ sets. Prove that \begin{equation}\sum_{i=0}^n\frac{|\mathcal{F}_i|}{{n\choose i}}\leq k,\end{equation}...
user avatar
1 vote
1 answer
67 views

Lower bound for the size of some families of subsets of $[2n+1]$ of size $n$

Let $\mathcal{A}$ be the family of all subsets of $U = [2n+1] = \{1,2,\ldots,2n,2n+1\}$ with size $n$, $n \ge 1$. Let $\mathcal{F} \subseteq \mathcal{A}$ be a subfamily of $\mathcal{A}$ with the ...
Fabius Wiesner's user avatar
0 votes
0 answers
25 views

Lower bound related to couples of disjoint two-element sets

I have already asked this question at MathOverflow, but without answers. I want to give it a try here, maybe somebody can answer or give interesting hints. Let $\mathcal{B}$ be the family of all ...
Fabius Wiesner's user avatar
3 votes
0 answers
121 views

A generalization of the edge isoperimetry problem for the hypercube

For any $n$, and any $1 \leq k \leq 2^n$, and any $1 \leq q \leq n-1$, we want $k$ binary vectors of length $n$, organized in a matrix $M$ with $k$ rows and $n$ columns, that will minimize $p(M,q)$ ...
Jan Arne Telle's user avatar
0 votes
0 answers
58 views

Lower bound for couples of disjoint sets in some partitions of the power set

Now crossposted at Mathoverflow. Consider partitions $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_n} \}$ of the powerset without the empty set element $Q = \mathcal{P}([n]) \setminus \{\emptyset\}$. ...
Fabius Wiesner's user avatar
2 votes
1 answer
95 views

Minimum vertex number that admits linear $d$-regular $k$-uniform hypergraph

$\newcommand\LRU{\mathrm{LRU}}\newcommand\tA{\mathrm{A}}\newcommand\tB{\mathrm{B}}\newcommand\tC{\mathrm{C}}\newcommand\tD{\mathrm{D}}\newcommand\tE{\mathrm{E}}$ For given integers $d>0$, $k>1$ ...
Matija's user avatar
  • 3,251
9 votes
1 answer
340 views

Proving $n$ subsets $A_1, ..., A_n$ of size $\geq 2$ must pairwise intersect.

Let $A_1, ..., A_n \subseteq [n]$ be $n$ subsets of $[n]$ with $|A_i|\geq 2$. Suppose further that for every $B \subseteq [n], |B|=2$, that there exists a unique $i$ with $B\subseteq A_i$. Prove that $...
AspiringMat's user avatar
  • 2,288
6 votes
1 answer
241 views

When can $L$ sets of the form $\{a,b,a+b\}$ partition $\{1,2,\dots, 3L\}$?

Now also posted to MathOverflow. Consider a set of the form $\{a,b,a+b\}$ where $a$ and $b$ are positive integers with $b > a$. I will refer to such a set as a triplet. Consider now the problem of ...
Mohannad Shehadeh's user avatar
0 votes
0 answers
7 views

What's the $p$-th power of a $k$-uniform tight cycle?

I understand that in a graph when there's a cycle, the $p$-th power of the cycle is when all vertices at a distance of at most $p$ from each other (on the base cycle) are joined with edges. A $k$-...
kleinbottle's user avatar
7 votes
2 answers
308 views

Between us my sister and I know everything -- how many sisters do I have?

My name is Aaron. I used to think my twin brother Bernard and I were pretty smart. You see between us, we know everything. That was until we met the triplets Charlotte, Denise, and Esther. Between any ...
Daron's user avatar
  • 10.3k
11 votes
1 answer
245 views

Maximal non-decreasing subsequence

Let $n\in \mathbb{N}$. A sequence $(y_i)$ with $0\le i\le 2^n-1$ is called beautiful of rank $n$ if for all $0\le i\le 2^n-1$, $0\le y_i\le i$. For a beautiful sequence $(y_i)$ of rank $n$ let $A((...
ZNatox's user avatar
  • 229
1 vote
0 answers
26 views

Upper bound for certain submatrices of binary matrices

I would like to get an upper bound $b(n,m)=b(m,n)$ for the number of $2 \times 2$ submatrices with one element equal to $1$ an the other three equal to $0$, over all possible $n \times m$ binary ...
Fabius Wiesner's user avatar
25 votes
6 answers
768 views

Fibonacci-esque sequences modulo $1$: what is the largest possible infimum?

Let an infinite sequence $S$ be a "Fibonacci-esque sequence" if, for all $n \geq 3, S(n) = S(n-1) + S(n-2).$ We can reduce $S$ modulo $1$ to get a "reduced Fibonacci sequence." ...
mathlander's user avatar
  • 3,967
0 votes
0 answers
67 views

A question on the proof of Erdős, Kleitman and Rothschild

I'am currently working my way through the proof of Erdős, Kleitman and Rothschild on the Asymptotic Enumeration of $K_n$-free Graphs (see https://users.renyi.hu/~p_erdos/1976-03.pdf). In particular I ...
Jonas's user avatar
  • 75
3 votes
1 answer
206 views

Expectation of r.v. in the proof of crossing number inequality

I was reading the proof of crossing number inequality and there was one step in the proof which I cannot prove rigorously. Firstly, let me remind the definition of the crossing number and then I ...
RFZ's user avatar
  • 16.7k
3 votes
1 answer
113 views

Combinatorics problem about subset

Probem: Let $n \ge 2$ be an integer. Then there always exists a family of $2^{n-1}$ subsets of {$1,2,...,n$} such that for every 3 distinct, non-empty members of that family, none of them is the union ...
Neman Vidic's user avatar
0 votes
0 answers
10 views

Counting $K_{2, 2, ...,2}$ in a $k$-partite $k$-uniform hypergraph

Let $G$ be a $k$-partite $k$-uniform hypergraph with at least $dn^k$ many edges. I want a lower bound on the number of $K_{2, 2, ...,2}$ in $G$, preferably something like $\gamma n^{2k}$ for some ...
kleinbottle's user avatar
2 votes
1 answer
363 views

Proof clarification: if $G$ is a simple graph with $2n$ vertices, $n^2$ edges and no triangles, then $G$ is the complete bipartite graph $K_{n, n}$

Let $G$ be a simple graph with $2n$ vertices and $n^2$ edges. If $G$ has no triangles, then $G$ is the complete bipartite graph $K_{n,n}$. I stumbled upon this proof for the result above, and I've ...
Nebzat's user avatar
  • 135
0 votes
0 answers
9 views

Getting a partite minimum co-degree in a $k$-partite $k$-uniform hypergraph

I have a $k$-partite $k$-uniform hypergraph $H$ with $V(G) = V_1 \cup...\cup V_k$ (each $|V_i|=n$ for $i \in [k]$), such that the minimum vertex degree $\delta(H) \ge Cn^{k-1}$ for a constant $C$. I ...
kleinbottle's user avatar
2 votes
1 answer
32 views

Bounding the size of set systems if the parity of intersection sizes are fixed.

I have been stuck on the following for a while. Earlier parts of the question proved a few results that I think may be applicable. Earlier Proven Results: Suppose $A_1, A_2 , ... , A_k $ and $B_1 , ...
oskar szarowicz's user avatar
1 vote
1 answer
80 views

Number of subsets with no pairwise intersection of cardinality 2?

Consider $[n] = \{1,2,\dots,n\}$ and let $\mathcal{F}$ be a family of subsets of $[n]$ , each subset having cardinality $k$, such that $\forall x,y \in \mathcal{F}, |x \cap y | \not = \frac{k}{2}.$ Is ...
Stefan S's user avatar
2 votes
0 answers
42 views

Collection of hyperplanes covering $\{ 0,1,2 \}^d$

Let $H$ be a finite collection of hyperplanes in $\mathbb{R}^d$ that covers all the points in $\{ 0,1,2 \}^d$ other than the origin $(0,0,\dots, 0)$ which is not covered. Show that $H$ is at least ...
Piglet's user avatar
  • 335
1 vote
1 answer
77 views

Existence of a Hadamard-like matrix

Question: For all $n$ large enough, there exists a matrix $A \in [-1,1]^{n \times n}$ such that $A\cdot A$ is a diagonal matrix with each diagonal entry at least $\frac{n}{100}$. Discussion: When ...
Mathews Boban's user avatar
4 votes
1 answer
442 views

Find the maximum number of elements in the set $M$ such that no two elements have a difference of $5$ or $8$

$\textbf{Question :}$ Let $M$ be a set of positive integers less than or equal to $2000$ with the property that no two elements can have a difference of either $5$ or $8$ then what is the maximum ...
sparrow_2764's user avatar
1 vote
1 answer
83 views

A family of subsets each of size $r$ must witness decent size of intersection for some two members.

$\newcommand{\lrp}[1]{\left(#1\right)}$ $\newcommand{\R}{\mathbf R}$ $\newcommand{\lrb}[1]{\left[#1\right]}$ Problem (Iberoamerican Olympiad 2001). Let $n, r, k$ be positive integers and assume $k\...
caffeinemachine's user avatar
0 votes
0 answers
24 views

Prove: Every collection of r subsets each with atleast $|X|(1-\frac{1}{r})$ points of X has a non empty intersection.

I am unable to show this "trivial" fact: Let $X$ be a finite set. Then every family of subsets of $X$ of size $r \ge 2$, where each subset contains atleast $|X|(1-\frac{1}{r})$ points of $X$ ...
Anon's user avatar
  • 2,460
0 votes
0 answers
61 views

Lower bound for the maximal complete subgraphs with all edges of the same color, for a complete graph

Consider the complete graph on $n$ vertices, and all possible graphs that can be obtained from it by coloring its edges with exactly $n$ colors. Given one of these colored graphs, we can determine the ...
Fabius Wiesner's user avatar
0 votes
0 answers
40 views

Proving existence of $d$-regular subgraph

Show that for every $\epsilon > 0$, there exists a $\delta = \delta(\epsilon) \geq 0$ and $n_0 = n_0(\epsilon)$ such that every graph $G = (V,E)$ with $n > n_0$ vertices and at least $\epsilon n^...
Piglet's user avatar
  • 335
1 vote
0 answers
59 views

Triangle-free graphs on a set $V$ of $n$ labeled vertices

Prove that the number of triangle-free graphs on a set $V$ of $n$ labeled vertices is $2^{(\frac{1}{4} + o(1))n^2}$ where the $o(1)$ term tends to $0$ as $n \to \infty$. I have a few ideas, but not ...
Piglet's user avatar
  • 335
4 votes
2 answers
90 views

Building a puzzle game - how to calculate total of combination sets once "invalid" results are excluded?

Please bear with me on terminology; I am learning! Also, please correct me if I've gotten anything wrong so far. Context: I am creating a single-player tile-based puzzle game where: Once tiles (200 ...
peepster's user avatar
0 votes
0 answers
22 views

poset covering question

Given a poset $P$ with n maximal elements $M$ such that each other element is covered by exactly two elements, ( recall $x$ covers $y$ if $x>y$ and there is no element $z\neq x,y$ for which $x>...
Hao S's user avatar
  • 288
1 vote
1 answer
52 views

Prove that $A_i$ has at least $1$ member that is not colored.

Let $A_1, A_2, \dots , A_n$ be subsets of $\{1, 2,\dots , n\}$ of size $3$. Prove that $\lfloor \frac{n}{3}\rfloor$ members of $\{1, 2,\dots , n\}$ can be colored such that each $A_i$ has at least $1$ ...
Raheel's user avatar
  • 1,587
2 votes
0 answers
256 views

Let $S_1, S_2, \dots , S_m$ be distinct subsets of $\{1, 2, \dots , n\}$ such that $|S_i \cap S_j | = 1$ for all $i \ne j$. Prove that $m \le n$.

Let $S_1, S_2, \dots , S_m$ be distinct subsets of $\{1, 2, \dots , n\}$ such that $|S_i \cap S_j | = 1$ for all $i \ne j$. Prove that $m \le n$. I got this problem from the double counting handout ( ...
Sunaina Pati's user avatar
  • 4,105

1
2 3 4 5
16