# A Guide for Bachelor Students in the Discrete Mathematics Group

## Bachelor work:

- timing: due date is 6 months after the Abgabe form is submitted. You may however start earlier. After the form is submitted, the deadline is hard – it is not possible to move it.

- length: If the result proven is new and very important, the length does not really matter, it just should not be longer than 100 pages. If the thesis contains mostly original research, 30-50 pages are typical. If the thesis contains mostly a survey of known results 50-100 pages are typical.

- language: English or German (English is preferable since most of the literature is in English)

- structure of thesis:

Table of contents | |||

Introduction | 3-4 pages containing only basic definitions, motivation, formulation of the problem, and statements of the main results proven in the thesis. | ||

Body | main material split into sections | ||

Conclusions (optional) | quick summary, less than one page, maybe list of open problems | ||

List of Figures and Tables | Figures are really pictures, like drawings of graphs; a big matrix is not a figure, it could be labeled as equation. | ||

Bibliography | you can use bibtex – cut and paste from mathscinet | ||

Statement of work being done independently | dated and signed – copy from template |

- basic structure of each section:

- Introductory paragraph
- Theorem, proof
- Theorem, proof
- Theorem, proof

Avoid text between theorems |

- typical sections:

- Definitions
- History and known results
- Topic 1 (Ex. Improved bounds on for graphs from class )
- Topic 2 (Ex. Special values of for graphs on at most 4 vertices)
- Topic 3 (Ex. Linear time algorithm to compute for subgraphs of the grid)

- references:

When citing papers list authors name as follows: one or two authors – list all, i.e., J. Smith or J. Smith and P. Johnes , if there are more than two authors, list the first one and et al.: J. Smith et al. . | ||

When you state theorems of other people, clearly mark that: Theorem 5 Smith . | ||

Clearly explain how your work differs from the original. | ||

The number of references for a typical thesis is between 30 and 100. |

## how to work on the thesis:

- Try to have fun with your problem – be curious, ask yourself questions, play with examples.
- Suggest your own questions, special cases, relaxations.
- Schedule meetings with your advisor – biweekly is typical, do not hesitate to ask questions in between, just send an e-mail.
- Start literature search immediately and take notes of all relevant results. Keep track of the papers you have read and which results they contain. We recommend to name the files alphabetically by last name of first author.
- Start writing right away – start putting the bibliography file, as soon as you have a small proof, typeset, explain to advisor, give advisor to check.
- When you get written comments from your advisor – fix them right away (2-3 days) and post in dropbox if you agreed on this with the advisor.
- Do not discard written notes of the advisor – they will be looked at during the work and at the end of the work.
- Send a current version of your write-up at least 2 days before your meeting with the advisor.
- Do not copy paste anything from the web or published papers – respect copyright.
- Do not use lengthy case analysis – try to come up with smarter proofs.
- In writing proofs, check every step – ask yourself critically whether the implication is logical.
- Introduce names for your variables, e.g., “let v be the vertex which …”
- Assume that the reader has attended a lecture on graph theory / combinatorics.
- Make sure that proofs are easy to read – they are not too wordy, not too dry, they have help paragraphs explaining main ideas in case of longer proofs, they can have phrases like “ for this part of the proof we need to …, we are given …”
- Include examples, figures, summaries. You have enough space.

## useful links:

- Mathscinet
- Google Scholar
- Arxiv
- DBLP computer science bibliography
- Thesis template
- LaTeX writing tips (in German)
- tips and guides of the TCS group (in German)
- Grammar according to D. West
- IPE (for drawing figures)
- A tutorial for TikZ (for drawing figures)
- detexify (for finding latex symbols)

## For Staatsexamen preparation:

Students taking this exam in Graph Theory will have 20 minutes to answer questions on the topics covered in class. The exam will not include the material on group-valued flows.

Typically, a student will be asked to present a statement and a proof of one of the classical results: 1) characterization of bipartite graphs, 2) tree equivalence theorem, 3) Hall's matching theorem, 4) Tur\'an theorem, 5) 5-list color theorem, 6) 5-color theorem, 7) ear-decomposition theorem, 8) lower and upper bounds on the Ramsey number R(n), 9) Dirac's theorem, 10) existence of a triangle-free graph of arbitrarily high chromatic number.

In addition, students taking this exam are expected to understand and use notions and results presented in class, know basic ideas of proofs, be able to apply the results to various settings and problems, be able to present a general view on main topics and connections between them. If asked to state a result, it is expected that the student writes down a complete, mathematically sound, and logically consistent statement and states it verbally as well. When asked to present a proof, a complete proof should be written. One could use arrows instead of writing full sentences. If asked to present main ideas of the proof, only key steps of the argument should be presented.