# Discrete Mathematics

## New submissions

[ total of 3 entries: 1-3 ]
[ showing up to 2000 entries per page: fewer | more ]

### New submissions for Mon, 19 Oct 20


Title: Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences
Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)

The greedy Prefer-same de Bruijn sequence construction was first presented by Eldert et al.[AIEE Transactions 77 (1958)]. As a greedy algorithm, it has one major downside: it requires an exponential amount of space to store the length $2^n$ de Bruijn sequence. Though de Bruijn sequences have been heavily studied over the last 60 years, finding an efficient construction for the Prefer-same de Bruijn sequence has remained a tantalizing open problem. In this paper, we unveil the underlying structure of the Prefer-same de Bruijn sequence and solve the open problem by presenting an efficient algorithm to construct it using $O(n)$ time per bit and only $O(n)$ space. Following a similar approach, we also present an efficient algorithm to construct the Prefer-opposite de Bruijn sequence.

### Cross-lists for Mon, 19 Oct 20

  arXiv:2010.08266 (cross-list from math.CO) [pdf, ps, other]
Title: Supercards, Sunshines and Caterpillar Graphs
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

The vertex-deleted subgraph G-v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G. The deck of G is the multiset of its unlabelled cards. The number of common cards b(G,H) of G and H is the cardinality of the multiset intersection of the decks of G and H. A supercard G+ of G and H is a graph whose deck contains at least one card isomorphic to G and at least one card isomorphic to H. We show how maximum sets of common cards of G and H correspond to certain sets of permutations of the vertices of a supercard, which we call maximum saturating sets. We apply the theory of supercards and maximum saturating sets to the case when G is a sunshine graph and H is a caterpillar graph. We show that, for large enough n, there exists some maximum saturating set that contains at least b(G,H)-2 automorphisms of G+, and that this subset is always isomorphic to either a cyclic or dihedral group. We prove that b(G,H)<=2(n+1)/5 for large enough n, and that there exists a unique family of pairs of graphs that attain this bound. We further show that, in this case, the corresponding maximum saturating set is isomorphic to the dihedral group.

### Replacements for Mon, 19 Oct 20

  arXiv:2006.04099 (replaced) [pdf, ps, other]
Title: On Hermitian varieties in $\mathrm{PG}(6,q^2)$
{"ft_lang_label":"__label__en","ft_lang_prob":0.8690821,"math_prob":0.916432,"size":577,"snap":"2020-45-2020-50","text_gpt3_token_len":190,"char_repetition_ratio":0.13612565,"word_repetition_ratio":0.21649484,"special_character_ratio":0.36221838,"punctuation_ratio":0.20325203,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98023444,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-10-20T01:05:14Z\",\"WARC-Record-ID\":\"<urn:uuid:b7e70b68-fd0a-4757-98e0-19d380fc730b>\",\"Content-Length\":\"15083\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:be847d7d-ee8f-4828-91c0-61bbac26bb93>\",\"WARC-Concurrent-To\":\"<urn:uuid:6e7c652b-f622-458a-a9e7-990a7536ba8a>\",\"WARC-IP-Address\":\"128.84.21.203\",\"WARC-Target-URI\":\"http://export.arxiv.org/list/cs.DM/new?skip=0&show=2000\",\"WARC-Payload-Digest\":\"sha1:YZ7GCOMFJSHCHPIXJXUHSPWN7GDJ5ADI\",\"WARC-Block-Digest\":\"sha1:SP4YFMN4UCANCCPKQNFIGN6FI3KUIINC\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-45/CC-MAIN-2020-45_segments_1603107867463.6_warc_CC-MAIN-20201019232613-20201020022613-00244.warc.gz\"}"}