Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `subject:(Sidon set)`

.
Showing records 1 – 2 of
2 total matches.

▼ Search Limiters

1. Haanpää, Harri. Constructing Certain Combinatorial Structures by Computational Methods.

Degree: 2004, Helsinki University of Technology

URL: http://lib.tkk.fi/Diss/2004/isbn9512269422/

Combinatorics is a branch of mathematics that generally deals with a finite or at most countably infinite set and collections of its subsets. These collections must then satisfy certain criteria depending on the class of objects and the problem being considered. The most fundamental problem in combinatorics is the problem of existence: Does a combinatorial structure that satisfies the given requirements exist? In general, it is straightforward to verify that a proposed structure satisfies the required criteria, but finding a structure of the required type is difficult. If a structure of the required type exists, any method that constructs one is sufficient to settle the existence question. Two problems closely related to the existence problem are the enumeration problem – how many different combinatorial structures of the required type exist – and the optimization problem – which combinatorial structure of the required type is the best, judged by some criterion. A computer may be very useful in solving problems of the three types mentioned above. If it is suspected that a structure of the required kind exists, one may design a computer program to sample the space of possible structures until one that satisfies the criteria is found. To show the nonexistence of a structure, to enumerate the structures of a given kind, or to determine the best structure of a given kind, it is generally necessary to conduct a case-by-case analysis of all possible structures, which is a task for which a computer is especially suited. It is, however, often a nontrivial task to design an efficient algorithm for such an analysis. In this thesis several ways of applying computational methods to combinatorial problems are described. Tabu search on graphs with cyclic symmetry is used to obtain a lower bound for a Ramsey number, an orderly backtrack search with isomorph rejection is applied to a particular class of codes to classify certain designs and the whist tournaments with up to thirteen players, and another orderly search is used to obtain the optimal sum and difference packings and covers of small Abelian groups.

Research reports / Helsinki University of Technology, Laboratory for Theoretical Computer Science. A, ISSN 1457-7615; 89

Subjects/Keywords: balanced incomplete block design; difference cover; difference packing; isomorph rejection; orderly algorithm; Ramsey number; Sidon set; sum cover; sum packing; whist tournament

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Haanpää, H. (2004). Constructing Certain Combinatorial Structures by Computational Methods. (Thesis). Helsinki University of Technology. Retrieved from http://lib.tkk.fi/Diss/2004/isbn9512269422/

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Haanpää, Harri. “Constructing Certain Combinatorial Structures by Computational Methods.” 2004. Thesis, Helsinki University of Technology. Accessed October 23, 2020. http://lib.tkk.fi/Diss/2004/isbn9512269422/.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Haanpää, Harri. “Constructing Certain Combinatorial Structures by Computational Methods.” 2004. Web. 23 Oct 2020.

Vancouver:

Haanpää H. Constructing Certain Combinatorial Structures by Computational Methods. [Internet] [Thesis]. Helsinki University of Technology; 2004. [cited 2020 Oct 23]. Available from: http://lib.tkk.fi/Diss/2004/isbn9512269422/.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Haanpää H. Constructing Certain Combinatorial Structures by Computational Methods. [Thesis]. Helsinki University of Technology; 2004. Available from: http://lib.tkk.fi/Diss/2004/isbn9512269422/

Not specified: Masters Thesis or Doctoral Dissertation

2. Tait, Michael. Connections between graph theory, additive combinatorics, and finite incidence geometry.

Degree: Mathematics, 2016, University of California – San Diego

URL: http://www.escholarship.org/uc/item/65v3m58c

This thesis studies problems in extremal graph theory, combinatorial number theory, and finite incidence geometry, and the interplay between these three areas. The first topic is the study of the Tur\'an number for C_{4}. Füredi showed that C_{4}-free graphs with {ex}(n, C_{4}) edges are intimately related to polarity graphs of projective planes. We prove a general theorem about dense subgraphs in a wide class of polarity graphs, and as a result give the best-known lower bounds for {ex}(n, C_{4}) for many values of n. We also study the chromatic and independence numbers of polarity graphs, with special emphasis on the graph ER_{q}. Next we study Sidon sets on graphs by considering what sets of integers may look like when certain pairs of them are restricted from having the same product. Other generalizations of Sidon sets are considered as well.We then use C_{4}-free graphs to prove theorems related to solvability of equations. Given an algebraic structure R and a subset A\subset R, define the {\em sum set} and {\em product set} of A to be A+A = {a+b:a,b∈ A} and A∙ A = {a∙ b: a,b∈ A} respectively. Showing under what conditions at least one of |A+A| or |A∙ A| is large has a long history of study that continues to the present day. Using spectral properties of the bipartite incidence graph of a projective plane, we deduce that nontrivial sum-product estimates hold in the setting where R is a finite quasifield. Several related results are obtained.Finally, we consider a classical question in finite incidence geometry: what is the subplane structure of a projective plane? A conjecture widely attributed to Neumann is that all non-Desarguesian projective planes contain a Fano subplane. By studying the structural properties of polarity graphs of a projective plane, we show that any plane of even order n which admits a polarity such that the corresponding polarity graph has exactly n+1 loops must contain a Fano subplane. The number of planes of order up to n which our theorem applies to is not bounded above by any polynomial in n.

Subjects/Keywords: Mathematics; Additive Combinatorics; Extremal Graph Theory; Polarity Graphs; Projective Plane; Sidon Set; Sum-Product Estimate

…graphs. A *Sidon* *set* is a *set* where all pairs
are required to have distinct sums. By introducing… …x28;2013).
Michael Tait and Craig Timmons. *Sidon* sets and graphs without 4-cycles. Journal… …graphs and *Sidon* sets. To
appear in Journal of Graph Theory.
x
ABSTRACT OF THE DISSERTATION… …emphasis on the graph ERq .
Next we study *Sidon* sets on graphs by considering what sets of… …Other generalizations of *Sidon* sets are considered as well.
We then use C4 -free graphs to…

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Tait, M. (2016). Connections between graph theory, additive combinatorics, and finite incidence geometry. (Thesis). University of California – San Diego. Retrieved from http://www.escholarship.org/uc/item/65v3m58c

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Tait, Michael. “Connections between graph theory, additive combinatorics, and finite incidence geometry.” 2016. Thesis, University of California – San Diego. Accessed October 23, 2020. http://www.escholarship.org/uc/item/65v3m58c.

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Tait, Michael. “Connections between graph theory, additive combinatorics, and finite incidence geometry.” 2016. Web. 23 Oct 2020.

Vancouver:

Tait M. Connections between graph theory, additive combinatorics, and finite incidence geometry. [Internet] [Thesis]. University of California – San Diego; 2016. [cited 2020 Oct 23]. Available from: http://www.escholarship.org/uc/item/65v3m58c.

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Tait M. Connections between graph theory, additive combinatorics, and finite incidence geometry. [Thesis]. University of California – San Diego; 2016. Available from: http://www.escholarship.org/uc/item/65v3m58c

Not specified: Masters Thesis or Doctoral Dissertation