Dtjytyk

Why do Australian milk farmers need to protest supermarkets' milk price?

Interplanetary conflict, some disease destroys the ability to understand or appreciate music

How can I track script which gives me "command not found" right after the login?

Sailing the cryptic seas

How Could an Airship Be Repaired Mid-Flight

Is it possible to upcast ritual spells?

How to terminate ping <dest> &

Credit cards used everywhere in Singapore or Malaysia?

What approach do we need to follow for projects without a test environment?

Bach's Toccata and Fugue in D minor breaks the "no parallel octaves" rule?

A Cautionary Suggestion

Python if-else code style for reduced code for rounding floats

What's the meaning of “spike” in the context of “adrenaline spike”?

Existence of subset with given Hausdorff dimension

Why did it take so long to abandon sail after steamships were demonstrated?

How to deal with a cynical class?

What should tie a collection of short-stories together?

Instead of Universal Basic Income, why not Universal Basic NEEDS?

Are ETF trackers fundamentally better than individual stocks?

If I can solve Sudoku can I solve Travelling Salesman Problem(TSP)? If yes, how?

PTIJ: Who should I vote for? (21st Knesset Edition)

Knife as defense against stray dogs

What options are left, if Britain cannot decide?

It's a yearly task, alright

Bipartite graph $G=(A,B)$ with $delta(A)=3n/2$ and no $C_4$ has a matching which saturate each vertex in $A$.

Show that a finite regular bipartite graph has a perfect matchingShowing a bipartite graph has a perfect matching.bipartite graph has perfect matchingEdge and vertex connectivity of bipartite graphMatching in a bipartite graphMatching in bipartite graphProof bipartite graph matchingIf graph G is bipartite with largest vertex degree $Delta$(G) , then $chi'(G)$ = $Delta$(G)Maximum matching for bipartite graphHow would we prove that the following bipartite graph has a perfect matching?

3

2

$begingroup$

Say $G$ is a bipartite graph with bipartition $(A,B)$ and $G$ is $C_4$-free. Prove that if every vertex in $A$ has degree at least $frac32 n$ and $|A|leq n^2$, then $G$ has a matching which uses every vertex in $A$.

---

My proof:

Use the Hall marriage theorem. Take any $Xsubseteq A$ and let $|X|=k$. Also let $Y=N(X)$ and $|Y|=l$. Let us prove that $lgeq k$. Assume that $l<k$.

Let $Y^*$ be a set of all unordered pairs ${y_i,y_j}$, $ine j$ of elements in $Y$, and connect a pair ${y_i,y_j}$ with $xin X$ iff both $y_i$ and $y_j$ are adjacent with $x$ in $G$. Then the degree of each pair in this new bipartite graph $G^*$ (on vertex set $X cup Y^*$) is at most $1$ (since there is no $C_4$ in $G$) and the degree of each $xin X$ is at least $displaystyle{{3nover 2}choose 2}$. So we have $$kcdot {{3nover 2}choose 2}leq {lchoose 2} .$$
Since we assume $l<k$ we have $${{3nover 2}choose 2}< {k-1over 2}$$ so $${3n(3n-2)over 4} < k-1 .$$ Since $kleq n^2$ we have $$3n(3n-2) leq 4n^2-8$$so
$$5n^2leq 6n-8$$ which is obviously not true.

Edit: After Darij's confirmation that the proof is correct, I'm will award any solution with better bound than $delta (G)=nsqrt{2}$ (instead of $3n/2$).

combinatorics discrete-mathematics proof-verification graph-theory

share|cite|improve this question

edited 2 days ago

Maria Mazur

asked May 25 '18 at 15:10

Maria MazurMaria Mazur

47k1260120

$endgroup$

This question has an open bounty worth +100
reputation from Maria Mazur ending in 2 days.

Looking for an answer drawing from credible and/or official sources.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How exactly do you prove this for $n$ instead of $3n/2$ ? I don't get the inequalities to product a contradiction.
  $endgroup$
  – darij grinberg
  Mar 11 at 20:03
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  We are talking now about $delta = 3n/2$ or $n$?
  $endgroup$
  – Maria Mazur
  Mar 11 at 20:10
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am talking about $n$.
  $endgroup$
  – darij grinberg
  Mar 11 at 20:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, I see. My bad. Anyway, is the rest correct?
  $endgroup$
  – Maria Mazur
  Mar 11 at 20:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The rest is correct. You may want to compute the optimal bound for your proof to work; I'm pretty sure it falls closer to $n$ than to $3n/2$.
  $endgroup$
  – darij grinberg
  Mar 11 at 20:30
  

  
  
  
  

 | 
show 2 more comments

3

2

$begingroup$

Say $G$ is a bipartite graph with bipartition $(A,B)$ and $G$ is $C_4$-free. Prove that if every vertex in $A$ has degree at least $frac32 n$ and $|A|leq n^2$, then $G$ has a matching which uses every vertex in $A$.

---

My proof:

Use the Hall marriage theorem. Take any $Xsubseteq A$ and let $|X|=k$. Also let $Y=N(X)$ and $|Y|=l$. Let us prove that $lgeq k$. Assume that $l<k$.

Let $Y^*$ be a set of all unordered pairs ${y_i,y_j}$, $ine j$ of elements in $Y$, and connect a pair ${y_i,y_j}$ with $xin X$ iff both $y_i$ and $y_j$ are adjacent with $x$ in $G$. Then the degree of each pair in this new bipartite graph $G^*$ (on vertex set $X cup Y^*$) is at most $1$ (since there is no $C_4$ in $G$) and the degree of each $xin X$ is at least $displaystyle{{3nover 2}choose 2}$. So we have $$kcdot {{3nover 2}choose 2}leq {lchoose 2} .$$
Since we assume $l<k$ we have $${{3nover 2}choose 2}< {k-1over 2}$$ so $${3n(3n-2)over 4} < k-1 .$$ Since $kleq n^2$ we have $$3n(3n-2) leq 4n^2-8$$so
$$5n^2leq 6n-8$$ which is obviously not true.

Edit: After Darij's confirmation that the proof is correct, I'm will award any solution with better bound than $delta (G)=nsqrt{2}$ (instead of $3n/2$).

combinatorics discrete-mathematics proof-verification graph-theory

share|cite|improve this question

edited 2 days ago

Maria Mazur

asked May 25 '18 at 15:10

Maria MazurMaria Mazur

47k1260120

$endgroup$

This question has an open bounty worth +100
reputation from Maria Mazur ending in 2 days.

Looking for an answer drawing from credible and/or official sources.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How exactly do you prove this for $n$ instead of $3n/2$ ? I don't get the inequalities to product a contradiction.
  $endgroup$
  – darij grinberg
  Mar 11 at 20:03
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  We are talking now about $delta = 3n/2$ or $n$?
  $endgroup$
  – Maria Mazur
  Mar 11 at 20:10
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am talking about $n$.
  $endgroup$
  – darij grinberg
  Mar 11 at 20:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, I see. My bad. Anyway, is the rest correct?
  $endgroup$
  – Maria Mazur
  Mar 11 at 20:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The rest is correct. You may want to compute the optimal bound for your proof to work; I'm pretty sure it falls closer to $n$ than to $3n/2$.
  $endgroup$
  – darij grinberg
  Mar 11 at 20:30
  

  
  
  
  

 | 
show 2 more comments

$begingroup$

Say $G$ is a bipartite graph with bipartition $(A,B)$ and $G$ is $C_4$-free. Prove that if every vertex in $A$ has degree at least $frac32 n$ and $|A|leq n^2$, then $G$ has a matching which uses every vertex in $A$.

---

My proof:

Use the Hall marriage theorem. Take any $Xsubseteq A$ and let $|X|=k$. Also let $Y=N(X)$ and $|Y|=l$. Let us prove that $lgeq k$. Assume that $l<k$.

Let $Y^*$ be a set of all unordered pairs ${y_i,y_j}$, $ine j$ of elements in $Y$, and connect a pair ${y_i,y_j}$ with $xin X$ iff both $y_i$ and $y_j$ are adjacent with $x$ in $G$. Then the degree of each pair in this new bipartite graph $G^*$ (on vertex set $X cup Y^*$) is at most $1$ (since there is no $C_4$ in $G$) and the degree of each $xin X$ is at least $displaystyle{{3nover 2}choose 2}$. So we have $$kcdot {{3nover 2}choose 2}leq {lchoose 2} .$$
Since we assume $l<k$ we have $${{3nover 2}choose 2}< {k-1over 2}$$ so $${3n(3n-2)over 4} < k-1 .$$ Since $kleq n^2$ we have $$3n(3n-2) leq 4n^2-8$$so
$$5n^2leq 6n-8$$ which is obviously not true.

Edit: After Darij's confirmation that the proof is correct, I'm will award any solution with better bound than $delta (G)=nsqrt{2}$ (instead of $3n/2$).

combinatorics discrete-mathematics proof-verification graph-theory

share|cite|improve this question

edited 2 days ago

Maria Mazur

asked May 25 '18 at 15:10

Maria MazurMaria Mazur

47k1260120

$endgroup$

share|cite|improve this question

edited 2 days ago

Maria Mazur

asked May 25 '18 at 15:10

Maria MazurMaria Mazur

47k1260120

share|cite|improve this question

edited 2 days ago

Maria Mazur

asked May 25 '18 at 15:10

Maria MazurMaria Mazur

47k1260120

asked May 25 '18 at 15:10

Maria MazurMaria Mazur

47k1260120

asked May 25 '18 at 15:10

Maria MazurMaria Mazur

47k1260120