47 papers
Dit paper introduceert HYGENE, een pionierende methode die gebruikmaakt van een op diffusie gebaseerd proces en een bipartiete representatie om realistische en diverse hypergrafen te genereren door een globale structuur geleidelijk uit te breiden en lokale details te verfijnen.
Dit artikel introduceert een nieuw rigideheidskader voor polytopen waarbij vlakken coplanair moeten blijven maar hun vorm mag veranderen, bewijst dat convexe polytopen generiek rigide zijn in dimensie drie, en toont aan dat flexibiliteit in dit model een uitzonderlijke eigenschap is.
Dit artikel presenteert een toegankelijker bewijs, gebaseerd op een vergeten artikel uit 1971 van Ralph Seifert, dat aantoont dat er geen priemfunctionele digraphen bestaan.
Dit paper stelt dat klassieke benchmarkinstanties voor het Traveling Salesman Problem met tijdvensters niet langer representatief zijn voor evaluatie, omdat een nieuwe exacte methode deze binnen enkele seconden oplost en hun structuur dusdanig exploiteerbaar is dat resultaten misleidend goed lijken.
In dit artikel wordt de langdurige open vraag van de Erdős-afstemmingsconjectuur opgelost door te bewijzen dat de maximale grootte van een familie van -elementige deelverzamelingen van die geen onderling disjuncte verzamelingen bevat, inderdaad wordt begrensd door het maximum van de twee canonieke extremale gevallen.
Dit artikel bewijst dat asymptotisch bijna alle vectoriële functies over eindige velden triviale extended-affiene stabilisatoren hebben, wat impliceert dat het aantal equivalentieklassen overeenkomt met de ruwe schatting en dat het toevalsgewijs selecteren van cryptografische primitieven een veilige strategie is.
Dit artikel presenteert een column-generatiebenadering voor het oplossen van het convex multi-commodity flow-probleem in telecommunicatienetwerken, waarbij zowel de splittable als de unsplittable varianten efficiënt worden behandeld om de totale linkkosten te minimaliseren.
Deze paper bepaalt systematisch de circulaire chromatische index van kleine grafen en multigrafen met een maximale graad tot 6, construeert oneindige families met specifieke indexwaarden en weerlegt varianten van de "Upper Gap Conjecture" over de niet-bestaande grafen met een index net onder .
Dit artikel onderzoekt het domineringspolynoom van co-maximale grafen van de ring van gehele getallen modulo , waarbij expliciete formules worden afgeleid voor specifieke gevallen, structurele relaties voor het algemene geval worden gepresenteerd, en eigenschappen zoals unimodaliteit, log-concaviteit en grenzen voor de moduli van de domineringswortels worden vastgesteld.
Dit artikel onderzoekt een familie van Max-Cut-instanties met geometrisch afnemende randgewichten, waarbij de auteurs een scherpe fasendiagram afleiden voor geïsoleerde sneden en concluderen dat deze voor vermoedelijk globaal optimaal zijn.
Dit artikel presenteert het gespectrume van gewogen burenmatrices voor complete multipartiete grafen, corrigeert eerdere resultaten over de invloed van randverwijdering op spectrale grootheden zoals energie en straal, en lost een open probleem op met betrekking tot de ISI-energie van multipartiete grafen.
Dit artikel introduceert en karakteriseert drie polynomiale grafklassen waarvoor een acyclische oriëntatie met pariteitsbeperkingen bestaat, levert constructieve bewijzen voor de solvabiliteit binnen deze klassen en bestudeert de hiërarchie en specifieke gevallen zoals cartesisch producten van paden en cycli.
Dit artikel bewijst dat voor hypergrafen gedefinieerd door kruisvrije deelgrafieken van een gastheergraf met begrensd genus, er een ondersteunende graf met eveneens begrensd genus bestaat, wat leidt tot een verenigde analyse voor verpakkings- en dekkingproblemen en toepassingen in hypergraafkleuring.
Dit artikel onderzoekt de maximale dichtheid van kanten in grafen die een tekening toelaten zonder een specifieke celtype, waarbij voor bijna alle combinaties van tekenstijl, graftype en celtype wordt aangetoond dat de dichtheid lineair of superlineair is in het aantal hoekpunten, en bovendien een volledige karakterisering wordt gegeven van de eenvoudige grafen die een tekening zonder celincidenties met kruisingen toelaten.
Dit artikel introduceert het localisatiekader om bestaande bovengrenzen voor extremale grafproblemen te verbeteren en structurele karakteriseringen te geven van de extremale grafen die deze grenzen bereiken.
Dit artikel toont aan dat voor een verzameling van fylogenetische bomen met weinig gemeenschappelijke structuur, het benodigde aantal reticulaties in een netwerk dat deze bomen weergeeft, vrijwel maximaal is en slechts marginaal lager ligt dan de triviale bovengrens, zelfs wanneer groeit tot een orde van .
Dit artikel onderzoekt de toestandcomplexiteit van lineaire deelrijen en basisoperaties op -automatische rijen, legt een verband met de subwoordcomplexiteit en beantwoordt een recente vraag van Zantema en Bosma over het meest-significant-digit-first-formaat.
In dit artikel wordt een volledig bewijs geleverd voor de eerder voorgestelde maar onvolledig bewezen bovengrens van het dubbel-dominatiegetal in maximale buitenplanaire grafen.
Dit artikel levert expliciete formules voor general position-polynomen van complete multipartiete grafen, toont aan dat log-concaviteit en unimodaliteit voor kleine deeltgrootte gelden maar voor grotere waarden falen, en bewijst dat unimodaliteit behouden blijft bij coronaproducten voor diverse natuurlijke grafklassen.
Dit artikel bewijst dat het verschil tussen de minimale grootte van een Boolese schakeling en een formule in de AIG-basis altijd 0 of 1 is, en dat delen van subexpressies alleen nodig is wanneer het aantal essentiële variabelen een bepaalde drempel overschrijdt.