$\newcommand{\wt}{\widetilde}$
$\newcommand{\nnn}{\mathbb N}$
$\newcommand{\zzz}{\mathbb Z}$
$\newcommand{\qqq}{\mathbb Q}$
$\newcommand{\rrr}{\mathbb R}$
$\newcommand{\ccc}{\mathbb C}$
$\newcommand{\fff}{\mathbb F}$
$\newcommand{\bbb}{\mathbb B}$
$\newcommand{\eee}{\mathrm e}$
$\newcommand{\calA}{\mathcal A}$
$\newcommand{\calB}{\mathcal B}$
$\newcommand{\calC}{\mathcal C}$
$\newcommand{\calD}{\mathcal D}$
$\newcommand{\calE}{\mathcal E}$
$\newcommand{\calF}{\mathcal F}$
$\newcommand{\calG}{\mathcal G}$
$\newcommand{\calH}{\mathcal H}$
$\newcommand{\calJ}{\mathcal J}$
$\newcommand{\calK}{\mathcal K}$
$\newcommand{\calL}{\mathcal L}$
$\newcommand{\calM}{\mathcal M}$
$\newcommand{\calP}{\mathcal P}$
$\newcommand{\calS}{\mathcal S}$
$\newcommand{\bfj}{\mathbf j}$
$\newcommand{\bfv}{\mathbf v}$
$\newcommand{\bfx}{\mathbf x}$
$\newcommand{\bfy}{\mathbf y}$
$\newcommand{\bfG}{\mathbf G}$
$\newcommand{\bzo}{\mathbf 0}$
$\newcommand{\boe}{\mathbf 1}$
$\newcommand{\bth}{\mathbf 3}$
$\newcommand{\bsx}{\mathbf 6}$
$\newcommand{\ftw}{\mathbf{42}}$
$\newcommand{\hxe}{\mathbf{168}}$
$\newcommand{\OPT}{\mathsf{OPT}}$
$\DeclareMathOperator{\RE}{\mathcal{RE}}$
$\DeclareMathOperator{\RRR}{\mathcal{R}}$
$\DeclareMathOperator{\orb}{\mathrm{orb}}$
$\DeclareMathOperator{\per}{\mathrm{per}}$
$\DeclareMathOperator{\fix}{\mathrm{fix}}$
$\DeclareMathOperator{\aff}{\mathrm{aff}}$
$\DeclareMathOperator{\even}{\mathrm{Even}}$
$\DeclareMathOperator{\odd}{\mathrm{Odd}}$
$\DeclareMathOperator{\hom}{\mathrm{Hom}}$
$\DeclareMathOperator{\avg}{\mathrm{avg}}$
$\DeclareMathOperator{\SET}{SET}$
$\DeclareMathOperator{\FFE}{FFE}$
$\DeclareMathOperator{\FFO}{FFO}$
$\DeclareMathOperator{\FF}{FF}$
$\DeclareMathOperator{\SUB}{SUB}$
$\DeclareMathOperator{\supp}{supp}$
$\DeclareMathOperator{\diag}{diag}$
$\DeclareMathOperator{\dist}{dist}$
$\DeclareMathOperator{\girth}{girth}$
$\DeclareMathOperator{\oddgirth}{oddgirth}$
$\DeclareMathOperator{\disc}{disc}$
$\DeclareMathOperator{\tower}{tower}$
$\DeclareMathOperator{\aut}{Aut}$
$\DeclareMathOperator{\sym}{Sym}$
$\DeclareMathOperator{\hypergrid}{hypergrid}$
$\DeclareMathOperator{\AG}{AG}$
$\DeclareMathOperator{\PG}{PG}$
$\DeclareMathOperator{\cent}{Cent}$
$\newcommand{\bbar}{\overline{b}}$
$\newcommand{\vbar}{\overline{v}}$
$\newcommand{\xbar}{\overline{x}}$
$\newcommand{\ybar}{\overline{y}}$
$\newcommand{\zbar}{\overline{z}}$
$\newcommand{\Abar}{\overline{A}}$
$\newcommand{\Bbar}{\overline{B}}$
$\newcommand{\Cbar}{\overline{C}}$
$\newcommand{\Gbar}{\overline{G}}$
$\newcommand{\Kbar}{\overline{K}}$
$\newcommand{\Lbar}{\overline{L}}$
$\newcommand{\Xbar}{\overline{X}}$
$\newcommand{\Ybar}{\overline{Y}}$
$\newcommand{\vf}{\varphi}$
$\newcommand{\vt}{\vartheta}$
$\DeclareMathOperator{\Div}{\mathrm Div}$
$\DeclareMathOperator{\lcm}{\mathrm lcm}$
$\DeclareMathOperator{\var}{\mathrm Var}$
$\DeclareMathOperator{\cov}{\mathrm Cov}$
$\DeclareMathOperator{\period}{\mathrm per}$
$\DeclareMathOperator{\rank}{\mathrm rk}$
$\DeclareMathOperator{\trace}{\mathrm Tr}$
$\DeclareMathOperator{\span}{\mathrm Span}$
$\DeclareMathOperator{\sgn}{\mathrm sgn}$
$\DeclareMathOperator{\inv}{\mathrm Inv}$
$\DeclareMathOperator{\diam}{\mathrm diam}$
$\DeclareMathOperator{\Adj}{\mathrm Adj}$
$\DeclareMathOperator{\val}{\mathrm val}$
$\DeclareMathOperator{\3col}{\mathrm 3-COL}$
$\DeclareMathOperator{\per}{\mathrm per}$
$\DeclareMathOperator{\PPP}{\mathrm P}$
$\DeclareMathOperator{\PPP}{\mathrm P}$
$\DeclareMathOperator{\NP}{\mathrm{NP}}$
$\DeclareMathOperator{\NPC}{\mathrm NPC}$
$\DeclareMathOperator{\coNP}{\mathrm coNP}$
$\DeclareMathOperator{\SAT}{\mathrm SAT}$
$\DeclareMathOperator{\COL}{\mathrm COL}$
László Babai's Summer 2023 Math REU page
Apprentice program, second phase: Graph Theory
(July 3 - July 14, weeks 4 - 5)
This page will be under construction throughout the course.
REFRESH your browser to get the current version.
What's new
| Course info
| Questionnaire
| Course description
| Problem sets by prof. Rudenko
| Online sources
| exercises
| prior REU courses by instructor
This page is under construction.
The problem sessions moved from the Barn to JCL 298
(John Crerar Library, 5730 S Ellis Avenue, Department of Computer Science),
see below.
Please answer the Questionnaire by Tuesday, July 4, 5pm.
Please review the online notes "ASYMP" and "PROB" (click the link "Online sources" on the banner)
Instructor: László Babai (please ignore the accents)
Offices: Ry 164, JCL 242 (John Crerar Library, 5730 S Ellis Ave)
Email: lbabai [at] jmail (oh, typo and incomplete domain!) and
laci [at] uwaukeegan.edu
(Oops! wrong town - to be eligible, you must guess the right one.
Oh, you are just a poor little bot? I am sooo sorry.)
Please use both of my email addresses in correspondence; each has its
advantages and disadvantages.
Please begin the Subject of your message with "REU23" and add some relevant information,
like "typo in Problem 3.21"
Email is my preferred way of communication (rather than text messages or social media).
I try to respond within 24 hours, and often within hours. Please send me a reminder
if I did not respond within 24 hours.
Please WARN ME by email as soon as possible if you find an error (or a potential error) on these pages.
Errors are likely, both typos and mathematical errors.
TAs with login names at the uwaukeegan.edu domain (wrong, again!)
Elizaveta Shuvaeva elizshuvaeva
Cameron Chang changca
Zana Tran zana.tran
Will Stroupe willstroupe
Marc de Fontnouvelle defont
Iqra Altaf iqra
Schedule: Class: every day 9:30 - 11:30, Ry-251, except July 4 and weekends.
Problem session: MWF 12:30-3:00pm in JCL 298
(John Crerar Library, 5730 S Ellis Avenue, Department of Computer Science).
The problem sessions are an integral part of the course. Come prepared,
contribute your thoughts.
Zoom chat. All classes are IN-PERSON. Nevertheless,
I will be running a zoom session during each class, with the sole
purpose to allow you to answer my questions in a private
"chat" message. Your answers will give me important instant feedback.
Make sure your messages are private. This ensures that you run no
risk of embarrassing yourself before your peers, and also that everybody
can give answers, no just the fastest few.
Please bring a device you can use to connect to this zoom session.
I will put the zoom link and password on the blackboard at the begining of
the class.
Please send email to the instructor with answers to these questions,
even if you are not officially attending the REU Apprentice program:
if you are atteding these class, I want to hear from you.
The purpose of these questions is twofold: if you are atteding
this course, I'd like to know a little about you; and
your answers to these questions will help me better to plan the course.
IMPORTANT. Please use both of my email addresses (above).
Please make the Subject of your message
Subject: REU23 data
If you don't use this Subject, I may miss your message (or misclassify it)
among the deluge of messages I am receiving.
- Your name. If your name has more than two parts, please specify between a pair of asterisks, which parts count as your family name. (Example: Wenceslas *Fernandez de la Vega*.)
- Your gender (male/female/other/prefer not to say).
- Optional: a link to a photo of yourself. (This may help me identify you in class.)
- Your home school. If not UChicago, please name the state, province, or foreign country and town.
- Your status at your home school (e.g., rising second year). If you are not an undergraduate, please explain.
(It is ok, I'd just like to know about you.)
- Name the four most advanced math courses you have taken (title of course, instructor).
- Have you been exposed to creative problem solving?
If so, tell me in what course(s) or program(s), at what institution(s).
- In what courses, if any, have you studied (a) linear algebra
(b) probability theory (c) discrete mathematics? [Note: Linear algebra is
a prerequisite for this course; probability and Discrete Math are not]
- Anything else you may want to tell me about yourself or about this course.
Go to top
The topic will be Graph Theory, with a focus on non-constructive proofs of existence vs.
explicit constructions. The mathematics used ranges from the elementary counting and
elements of discrete probability to linear algebra to deep results in algebra and number theory.
Prerequisites: linear algebra over the real and complex numbers. We shall rely on what
you have learned in this course about groups, complex roots of unity, and quadratic residues
modulo $p$. No prior knowledge of probability theory will be assumed.
pset1.pdf
pset2.pdf
pset3.pdf
pset4.pdf
pset5.pdf
pset6.pdf
A problem assigned on the blackboard on Friday, June 30:
Problem 06-30
Let $p$ be an odd prime number. Compute the following sums:
$$(a) \qquad \sum_{a=0}^{p-1} \left(\frac{a(a-1)}{p}\right) \qquad\qquad\qquad
(b) \qquad \sum_{a=0}^{p-1} \left(\frac{a^2+1}{p}\right)$$
where $\left(\frac{a}{p}\right)$ denotes the Legendre symbol.
Back to top